oj.uz

Submission #113554

# Submission time Handle Problem Language Result Execution time Memory
113554 2019-05-26T08:58:30 Z E869120 Simurgh (IOI17_simurgh) C++14
30 / 100
 124 ms 3072 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); par[u] = v; }
};

int N, M, A[1 << 18], B[1 << 18], id[509][509], col[509], represent[509], cnts;
vector<int>G[509], ans;
vector<pair<int, int>> R[509];

void dfs(int root, int pos) {
	if (col[pos] >= 1) return;
	col[pos] = cnts; if (id[root][pos] >= 0) represent[cnts] = pos;
	for (int t : G[pos]) dfs(root, t);
}

void solve(int pos) {
	UnionFind UF; UF.init(N); vector<int>v;
	for (int i = 0; i < N; i++) { G[i].clear(); R[i].clear(); col[i] = 0; represent[i] = 0; cnts = 0; }
	for (int i = 0; i < M; i++) {
		if (A[i] == pos || B[i] == pos) continue;
		if (UF.root(A[i]) == UF.root(B[i])) continue;
		UF.unite(A[i], B[i]); v.push_back(i);
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	for (int i = 0; i < N; i++) {
		if (i == pos || col[i] >= 1) continue;
		cnts++; dfs(pos, i);
	}
	for (int i = 0; i < N; i++) {
		if (id[pos][i] == -1) continue;
		
		vector<int>vec = v;
		for (int j = 1; j <= cnts; j++) { if (j == col[i]) continue; vec.push_back(id[pos][represent[j]]); }
		vec.push_back(id[pos][i]);
		int E = count_common_roads(vec);
		R[col[i]].push_back(make_pair(E, i));
	}
	for (int i = 1; i <= cnts; i++) {
		sort(R[i].begin(), R[i].end());
		reverse(R[i].begin(), R[i].end());
		for (int j = 0; j < R[i].size(); j++) { if (R[i][j].first == R[i][0].first) ans.push_back(id[pos][R[i][j].second]); }
	}
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	N = n; M = u.size();
	for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) id[i][j] = -1; }
	for (int i = 0; i < M; i++) { id[u[i]][v[i]] = i; id[v[i]][u[i]] = i; A[i] = u[i]; B[i] = v[i]; }
	for (int i = 0; i < N; i++) solve(i);
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	//cout << "#answer = "; for (int i = 0; i < ans.size(); i++) cout << ans[i] << ", "; cout << endl;
	return ans;
}

Compilation message

simurgh.cpp: In function 'void solve(int)':
simurgh.cpp:53:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < R[i].size(); j++) { if (R[i][j].first == R[i][0].first) ans.push_back(id[pos][R[i][j].second]); }
                   ~~^~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory 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 2 ms 384 KB correct
9 Correct 2 ms 384 KB correct
10 Correct 2 ms 384 KB correct
11 Correct 2 ms 384 KB correct
12 Correct 2 ms 384 KB correct
13 Correct 2 ms 384 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory 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 2 ms 384 KB correct
9 Correct 2 ms 384 KB correct
10 Correct 2 ms 384 KB correct
11 Correct 2 ms 384 KB correct
12 Correct 2 ms 384 KB correct
13 Correct 2 ms 384 KB correct
14 Correct 4 ms 512 KB correct
15 Correct 5 ms 512 KB correct
16 Correct 5 ms 512 KB correct
17 Correct 4 ms 512 KB correct
18 Correct 3 ms 512 KB correct
19 Correct 5 ms 512 KB correct
20 Correct 5 ms 512 KB correct
21 Correct 5 ms 512 KB correct
22 Correct 5 ms 512 KB correct
23 Correct 4 ms 512 KB correct
24 Correct 4 ms 484 KB correct
25 Correct 2 ms 512 KB correct
26 Correct 4 ms 512 KB correct
27 Correct 4 ms 512 KB correct
28 Correct 3 ms 512 KB correct
29 Correct 3 ms 512 KB correct
30 Correct 3 ms 512 KB correct
31 Correct 5 ms 512 KB correct
32 Correct 3 ms 512 KB correct
33 Correct 3 ms 512 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory 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 2 ms 384 KB correct
9 Correct 2 ms 384 KB correct
10 Correct 2 ms 384 KB correct
11 Correct 2 ms 384 KB correct
12 Correct 2 ms 384 KB correct
13 Correct 2 ms 384 KB correct
14 Correct 4 ms 512 KB correct
15 Correct 5 ms 512 KB correct
16 Correct 5 ms 512 KB correct
17 Correct 4 ms 512 KB correct
18 Correct 3 ms 512 KB correct
19 Correct 5 ms 512 KB correct
20 Correct 5 ms 512 KB correct
21 Correct 5 ms 512 KB correct
22 Correct 5 ms 512 KB correct
23 Correct 4 ms 512 KB correct
24 Correct 4 ms 484 KB correct
25 Correct 2 ms 512 KB correct
26 Correct 4 ms 512 KB correct
27 Correct 4 ms 512 KB correct
28 Correct 3 ms 512 KB correct
29 Correct 3 ms 512 KB correct
30 Correct 3 ms 512 KB correct
31 Correct 5 ms 512 KB correct
32 Correct 3 ms 512 KB correct
33 Correct 3 ms 512 KB correct
34 Incorrect 124 ms 1792 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB correct
2 Correct 2 ms 384 KB correct
3 Incorrect 94 ms 3072 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory 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 2 ms 384 KB correct
9 Correct 2 ms 384 KB correct
10 Correct 2 ms 384 KB correct
11 Correct 2 ms 384 KB correct
12 Correct 2 ms 384 KB correct
13 Correct 2 ms 384 KB correct
14 Correct 4 ms 512 KB correct
15 Correct 5 ms 512 KB correct
16 Correct 5 ms 512 KB correct
17 Correct 4 ms 512 KB correct
18 Correct 3 ms 512 KB correct
19 Correct 5 ms 512 KB correct
20 Correct 5 ms 512 KB correct
21 Correct 5 ms 512 KB correct
22 Correct 5 ms 512 KB correct
23 Correct 4 ms 512 KB correct
24 Correct 4 ms 484 KB correct
25 Correct 2 ms 512 KB correct
26 Correct 4 ms 512 KB correct
27 Correct 4 ms 512 KB correct
28 Correct 3 ms 512 KB correct
29 Correct 3 ms 512 KB correct
30 Correct 3 ms 512 KB correct
31 Correct 5 ms 512 KB correct
32 Correct 3 ms 512 KB correct
33 Correct 3 ms 512 KB correct
34 Incorrect 124 ms 1792 KB WA in grader: NO
35 Halted 0 ms 0 KB -