oj.uz

Submission #435016

# Submission time Handle Problem Language Result Execution time Memory
435016 2021-06-22T19:35:43 Z grt Keys (IOI21_keys) C++17
67 / 100
 2500 ms 203368 KB 
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 300 * 1000 + 10, INF = 1e9;
int n, m, nr;
map<int, vi>V[nax];
bool vis[2 * nax];
vi seen;
vi G[2 * nax];
vi Grev[2 * nax];
int topo[2 * nax];
int SCC[2 * nax];
bool ok[2 * nax];
int color;
int cc[nax];
int cnt[2 * nax], rep[2 * nax];
bool visited[nax];
bool done[nax];
vi verToAC[nax];
vector<pi>V2[nax];

void dfs(int x, int col) {
	vis[x] = true;
	seen.PB(x);
	for(auto ed : V[col][x]) if(!vis[ed]) {
		dfs(ed, col);
	}
}

void dfs2(int x) {
	vis[x] = true;
	for(int nbh : G[x]) {
		if(!vis[nbh]) {
			dfs2(nbh);
		}
	}
	topo[nr++] = x;
}

void dfs3(int x) {
	vis[x] = true;
	SCC[x] = color;
	if(x < n) rep[color] = x;
	if(x < n) cnt[color]++;
	for(int nbh : Grev[x]) if(!vis[nbh]) {
		dfs3(nbh);
	}
}

queue<int>Q;
vi saw, sawC;

void dfss(int x) {
	visited[x] = true;
	saw.PB(x);
	//cout << "VER: " << x << "\n";
	Q.push(cc[x]);
	for(auto nbh : V2[x]) if(!visited[nbh.ST]) {
		if(done[nbh.ND]) {
			dfss(nbh.ST);
		} else {
			verToAC[nbh.ND].PB(nbh.ST);
			sawC.PB(nbh.ND);
		}
	}
}

vi alg(int x) {
	saw = {};
	sawC = {};
	//for(int i = 0; i < n; ++i) {
		//done[i] = visited[i] = false;
	//}
	visited[x] = true;
	Q.push(cc[x]);
	saw.PB(x);
	for(auto nbh : V2[x]) {
		verToAC[nbh.ND].PB(nbh.ST);
		sawC.PB(nbh.ND);
	}
	vi rem = {};
	while(!Q.empty()) {
		x = Q.front();
		Q.pop();
		//cout << "COL: " << x << "\n";
		if(done[x]) continue;
		rem.PB(x);
		done[x] = true;
		for(auto y : verToAC[x]) {
			if(!visited[y]) dfss(y);
		}
	}
	for(int xx : rem) {
		done[xx] = false;
	}
	for(int xx : saw) {
		visited[xx] = false;
	}
	for(int xx : sawC) {
		verToAC[xx].clear();
	}
	return saw;
}

vi find_reachable(vi r, vi u, vi v, vi c) {
	n = (int)r.size();
	m = (int)u.size();
	for(int i = 0; i < m; ++i) {
		V[c[i]][u[i]].PB(v[i]);
		V[c[i]][v[i]].PB(u[i]);
		V2[u[i]].emplace_back(v[i], c[i]);
		V2[v[i]].emplace_back(u[i], c[i]);
		
	}
	for(int i = 0; i < n; ++i) {
		cc[i] = r[i];
	}
	int ver = n-1;
	for(int i = 0; i < n; ++i) {
		for(auto it : V[i]) {
			if(!vis[it.ST]) {
				seen.clear();
				dfs(it.ST, i);
				bool any = false;
				for(auto x : seen) {
					if(r[x] == i) any = true;
				}
				if(!any) continue;
				ver++;
				for(auto x : seen) {
					G[ver].PB(x);
					Grev[x].PB(ver);
					if(r[x] == i) {
						G[x].PB(ver);
						Grev[ver].PB(x);
					}
				}
			}
		}
		for(auto it : V[i]) vis[it.ST] = false;
	}
	for(int i = 0; i <= ver; ++i) {
		if(!vis[i]) {
			dfs2(i);
		}
	}
	for(int i = 0; i <= ver; ++i) {
		vis[i] = false;
	}
	for(int i = ver; i >= 0; --i) {
		if(!vis[topo[i]]) {
			color++;
			dfs3(topo[i]);
		}
	}
	for(int i = 0; i <= ver; ++i) ok[i] = false;
	for(int i = 0; i < n; ++i) ok[SCC[i]] = true;
	for(int i = 0; i <= ver; ++i) {
		for(int nbh : G[i]) {
			if(SCC[nbh] != SCC[i]) {
				ok[SCC[i]] = false;
			}
		}
	}
	vector<vi>com;
	int mi = INF;
	for(int i = 1; i <= color; ++i) {
		if(!ok[i]) continue;
		com.PB(alg(rep[i]));
		//cout << rep[i] << "\n";
		//for(int x : com.back()) {
			//cout << x << " ";
		//}
		//cout << "\n";
		mi = min(mi, (int)com.back().size());
	}
	//cout << "\n";
	vector<int>ans(n);
	for(int i = 0; i < n; ++i) ans[i] = false;
	for(auto vc : com) {
		if((int)vc.size() == mi) {
			for(int x : vc) {
				ans[x] = true;
			}
		}
	}
	//for(int i = 0; i < n; ++i) {
		//if(ok[SCC[i]] && cnt[SCC[i]] == mi) {
			//ans[i] = true;
		//} else {
			//ans[i] = false;
		//}
	//}
	return ans;
}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//int N, M;
	//cin >> N >> M;
	//vi r(N), u(M), v(M), c(M);
	//for(int i = 0; i < N; ++i) {
		//cin >> r[i];
	//}
	//for(int i = 0; i < M; ++i) {
		//cin >> u[i] >> v[i] >> c[i];
	//}
	//vi w = find_reachable(r,u,v,c);
	//vi w = find_reachable({0, 1, 1, 2},{0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
	//vi w = find_reachable({0, 1, 1, 2, 2, 1, 2},{0, 0, 1, 1, 2, 3, 3, 4, 4, 5},
//{1, 2, 2, 3, 3, 4, 5, 5, 6, 6},
//{0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
	//vi w = find_reachable({0, 0, 0}, {0}, {1}, {0});
	//for(int x : w) {
		//cout << x << " ";
	//}
//}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56728 KB Output is correct
2 Correct 37 ms 56704 KB Output is correct
3 Correct 37 ms 56696 KB Output is correct
4 Correct 36 ms 56652 KB Output is correct
5 Correct 36 ms 56652 KB Output is correct
6 Correct 36 ms 56708 KB Output is correct
7 Correct 36 ms 56672 KB Output is correct
8 Correct 39 ms 56740 KB Output is correct
9 Correct 37 ms 56652 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56728 KB Output is correct
2 Correct 37 ms 56704 KB Output is correct
3 Correct 37 ms 56696 KB Output is correct
4 Correct 36 ms 56652 KB Output is correct
5 Correct 36 ms 56652 KB Output is correct
6 Correct 36 ms 56708 KB Output is correct
7 Correct 36 ms 56672 KB Output is correct
8 Correct 39 ms 56740 KB Output is correct
9 Correct 37 ms 56652 KB Output is correct
10 Correct 41 ms 56788 KB Output is correct
11 Correct 36 ms 56732 KB Output is correct
12 Correct 37 ms 56812 KB Output is correct
13 Correct 35 ms 56652 KB Output is correct
14 Correct 35 ms 56620 KB Output is correct
15 Correct 36 ms 56688 KB Output is correct
16 Correct 37 ms 56652 KB Output is correct
17 Correct 35 ms 56704 KB Output is correct
18 Correct 34 ms 56756 KB Output is correct
19 Correct 35 ms 56704 KB Output is correct
20 Correct 37 ms 56652 KB Output is correct
21 Correct 36 ms 56780 KB Output is correct
22 Correct 36 ms 56656 KB Output is correct
23 Correct 36 ms 56732 KB Output is correct
24 Correct 41 ms 56816 KB Output is correct
25 Correct 36 ms 56752 KB Output is correct
26 Correct 41 ms 56724 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56728 KB Output is correct
2 Correct 37 ms 56704 KB Output is correct
3 Correct 37 ms 56696 KB Output is correct
4 Correct 36 ms 56652 KB Output is correct
5 Correct 36 ms 56652 KB Output is correct
6 Correct 36 ms 56708 KB Output is correct
7 Correct 36 ms 56672 KB Output is correct
8 Correct 39 ms 56740 KB Output is correct
9 Correct 37 ms 56652 KB Output is correct
10 Correct 41 ms 56788 KB Output is correct
11 Correct 36 ms 56732 KB Output is correct
12 Correct 37 ms 56812 KB Output is correct
13 Correct 35 ms 56652 KB Output is correct
14 Correct 35 ms 56620 KB Output is correct
15 Correct 36 ms 56688 KB Output is correct
16 Correct 37 ms 56652 KB Output is correct
17 Correct 35 ms 56704 KB Output is correct
18 Correct 34 ms 56756 KB Output is correct
19 Correct 35 ms 56704 KB Output is correct
20 Correct 37 ms 56652 KB Output is correct
21 Correct 36 ms 56780 KB Output is correct
22 Correct 36 ms 56656 KB Output is correct
23 Correct 36 ms 56732 KB Output is correct
24 Correct 41 ms 56816 KB Output is correct
25 Correct 36 ms 56752 KB Output is correct
26 Correct 41 ms 56724 KB Output is correct
27 Correct 40 ms 57588 KB Output is correct
28 Correct 39 ms 57596 KB Output is correct
29 Correct 40 ms 57504 KB Output is correct
30 Correct 38 ms 57184 KB Output is correct
31 Correct 39 ms 57104 KB Output is correct
32 Correct 36 ms 56764 KB Output is correct
33 Correct 38 ms 57004 KB Output is correct
34 Correct 36 ms 57032 KB Output is correct
35 Correct 38 ms 57148 KB Output is correct
36 Correct 39 ms 57576 KB Output is correct
37 Correct 39 ms 57596 KB Output is correct
38 Correct 40 ms 57692 KB Output is correct
39 Correct 45 ms 57816 KB Output is correct
40 Correct 39 ms 57156 KB Output is correct
41 Correct 44 ms 57540 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56728 KB Output is correct
2 Correct 37 ms 56704 KB Output is correct
3 Correct 37 ms 56696 KB Output is correct
4 Correct 36 ms 56652 KB Output is correct
5 Correct 36 ms 56652 KB Output is correct
6 Correct 36 ms 56708 KB Output is correct
7 Correct 36 ms 56672 KB Output is correct
8 Correct 39 ms 56740 KB Output is correct
9 Correct 37 ms 56652 KB Output is correct
10 Correct 1801 ms 145012 KB Output is correct
11 Correct 1449 ms 145456 KB Output is correct
12 Correct 417 ms 86672 KB Output is correct
13 Correct 2135 ms 180732 KB Output is correct
14 Correct 502 ms 139936 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56728 KB Output is correct
2 Correct 37 ms 56704 KB Output is correct
3 Correct 37 ms 56696 KB Output is correct
4 Correct 36 ms 56652 KB Output is correct
5 Correct 36 ms 56652 KB Output is correct
6 Correct 36 ms 56708 KB Output is correct
7 Correct 36 ms 56672 KB Output is correct
8 Correct 39 ms 56740 KB Output is correct
9 Correct 37 ms 56652 KB Output is correct
10 Correct 41 ms 56788 KB Output is correct
11 Correct 36 ms 56732 KB Output is correct
12 Correct 37 ms 56812 KB Output is correct
13 Correct 35 ms 56652 KB Output is correct
14 Correct 35 ms 56620 KB Output is correct
15 Correct 36 ms 56688 KB Output is correct
16 Correct 37 ms 56652 KB Output is correct
17 Correct 35 ms 56704 KB Output is correct
18 Correct 34 ms 56756 KB Output is correct
19 Correct 35 ms 56704 KB Output is correct
20 Correct 37 ms 56652 KB Output is correct
21 Correct 36 ms 56780 KB Output is correct
22 Correct 36 ms 56656 KB Output is correct
23 Correct 36 ms 56732 KB Output is correct
24 Correct 41 ms 56816 KB Output is correct
25 Correct 36 ms 56752 KB Output is correct
26 Correct 41 ms 56724 KB Output is correct
27 Correct 40 ms 57588 KB Output is correct
28 Correct 39 ms 57596 KB Output is correct
29 Correct 40 ms 57504 KB Output is correct
30 Correct 38 ms 57184 KB Output is correct
31 Correct 39 ms 57104 KB Output is correct
32 Correct 36 ms 56764 KB Output is correct
33 Correct 38 ms 57004 KB Output is correct
34 Correct 36 ms 57032 KB Output is correct
35 Correct 38 ms 57148 KB Output is correct
36 Correct 39 ms 57576 KB Output is correct
37 Correct 39 ms 57596 KB Output is correct
38 Correct 40 ms 57692 KB Output is correct
39 Correct 45 ms 57816 KB Output is correct
40 Correct 39 ms 57156 KB Output is correct
41 Correct 44 ms 57540 KB Output is correct
42 Correct 1801 ms 145012 KB Output is correct
43 Correct 1449 ms 145456 KB Output is correct
44 Correct 417 ms 86672 KB Output is correct
45 Correct 2135 ms 180732 KB Output is correct
46 Correct 502 ms 139936 KB Output is correct
47 Correct 36 ms 56604 KB Output is correct
48 Correct 37 ms 56724 KB Output is correct
49 Correct 43 ms 56688 KB Output is correct
50 Correct 490 ms 157732 KB Output is correct
51 Correct 511 ms 156864 KB Output is correct
52 Correct 820 ms 145324 KB Output is correct
53 Correct 803 ms 145328 KB Output is correct
54 Correct 874 ms 145244 KB Output is correct
55 Correct 1255 ms 154168 KB Output is correct
56 Correct 1357 ms 168372 KB Output is correct
57 Correct 1450 ms 151168 KB Output is correct
58 Correct 1252 ms 203368 KB Output is correct
59 Correct 1366 ms 189360 KB Output is correct
60 Correct 1612 ms 181032 KB Output is correct
61 Correct 1845 ms 191740 KB Output is correct
62 Execution timed out 2603 ms 168140 KB Time limit exceeded
63 Halted 0 ms 0 KB -