oj.uz

답안 #113550

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
113550 2019-05-26T08:34:27 Z E869120 Simurgh (IOI17_simurgh) C++14
0 / 100
 94 ms 4728 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

class UnionFind {
	public:
	vector<int> par;
	
	void init(int sz) {
		par.resize(sz, -1);
	}
	int root(int pos) {
		if (par[pos] == -1) return pos;
		par[pos] = root(par[pos]);
		return par[pos];
	}
	void unite(int u, int v) {
		u = root(u); v = root(v); if (u == v) return;
		par[u] = v;
	}
	bool same(int u, int v) {
		if (root(u) == root(v)) return true;
		return false;
	}
};

int N, M, A[1 << 18], B[1 << 18], id[509][509]; vector<pair<int, int>> X[509];
vector<int> ans, G[509], F; bool used[509], forced[509];

vector<int> anti_spanning_tree(int pos) {
	vector<int>E; UnionFind UF; UF.init(N);
	for (int i = 0; i < M; i++) {
		if (A[i] == pos || B[i] == pos) continue;
		if (UF.same(A[i], B[i]) == false) {
			E.push_back(i);
			UF.unite(A[i], B[i]);
		}
	}
	return E;
}

void hantei(vector<int> vec, vector<int> r) {
	vector<int> L; int maxn = 0;
	for (int pos : r) {
		vector<int> vec2 = vec; vec2.push_back(pos);
		assert(vec2.size() == N - 1);
		int E = count_common_roads(vec2);
		maxn = max(maxn, E); L.push_back(E);
	}
	for (int j = 0; j < r.size(); j++) {
		if (L[j] == maxn) ans.push_back(r[j]);
	}
}

void dfs(int pos) {
	if (used[pos] == true) return;
	used[pos] = true; if (forced[pos] == true) F.push_back(pos);
	for (int i = 0; i < G[pos].size(); i++) {
		dfs(G[pos][i]);
	}
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	N = n; M = u.size();
	for (int i = 0; i < M; i++) {
		A[i] = u[i]; B[i] = v[i];
		X[A[i]].push_back(make_pair(B[i], i));
		X[B[i]].push_back(make_pair(A[i], i));
		id[A[i]][B[i]] = i;
		id[B[i]][A[i]] = i;
	}
	
	for (int i = 0; i < N; i++) {
		vector<int> vec = anti_spanning_tree(i); 
		for (int j = 0; j < N; j++) { used[j] = false; forced[j] = false; G[j].clear(); }
		for (int pos : vec) {
			G[A[pos]].push_back(B[pos]);
			G[B[pos]].push_back(A[pos]);
		}
		for (pair<int, int> pos : X[i]) forced[pos.first] = true;
		
		vector<vector<int>> U;
		for (int j = 0; j < N; j++) {
			if (j == i || used[j] == true) continue;
			F.clear(); dfs(j);
			vector<int>FF; for (int pos : F) FF.push_back(id[i][pos]);
			F = FF; U.push_back(F);
		}
		
		for (int j = 0; j < U.size(); j++) {
			vector<int> F = U[j];
			vector<int> vec3 = vec;
			for (int k = 0; k < U.size(); k++) {
				if (j == k) continue;
				vec3.push_back(id[i][U[k][0]]);
			}
			
			hantei(vec3, F);
		}
	}
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	
	//for (int i = 0; i < ans.size(); i++) cout << ans[i] << ", "; cout << endl;
	return ans;
}

Compilation message

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp: In function 'void hantei(std::vector<int>, std::vector<int>)':
simurgh.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(vec2.size() == N - 1);
          ~~~~~~~~~~~~^~~~~~~~
simurgh.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < r.size(); j++) {
                  ~~^~~~~~~~~~
simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < U.size(); j++) {
                   ~~^~~~~~~~~~
simurgh.cpp:93:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < U.size(); k++) {
                    ~~^~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 384 KB correct
4 Correct 2 ms 384 KB correct
5 Correct 2 ms 384 KB correct
6 Correct 2 ms 384 KB correct
7 Correct 2 ms 384 KB correct
8 Correct 1 ms 384 KB correct
9 Incorrect 2 ms 384 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 384 KB correct
4 Correct 2 ms 384 KB correct
5 Correct 2 ms 384 KB correct
6 Correct 2 ms 384 KB correct
7 Correct 2 ms 384 KB correct
8 Correct 1 ms 384 KB correct
9 Incorrect 2 ms 384 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 384 KB correct
4 Correct 2 ms 384 KB correct
5 Correct 2 ms 384 KB correct
6 Correct 2 ms 384 KB correct
7 Correct 2 ms 384 KB correct
8 Correct 1 ms 384 KB correct
9 Incorrect 2 ms 384 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Incorrect 94 ms 4728 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Correct 2 ms 384 KB correct
4 Correct 2 ms 384 KB correct
5 Correct 2 ms 384 KB correct
6 Correct 2 ms 384 KB correct
7 Correct 2 ms 384 KB correct
8 Correct 1 ms 384 KB correct
9 Incorrect 2 ms 384 KB WA in grader: NO
10 Halted 0 ms 0 KB -