oj.uz

Submission #785963

# Submission time Handle Problem Language Result Execution time Memory
785963 2023-07-17T20:34:44 Z AdamGS Keys (IOI21_keys) C++17
100 / 100
 1159 ms 177972 KB 
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=3e5+7;
int sp[LIM], cy[LIM], ile[LIM], T[LIM], nxt[LIM], n;
set<int>S[LIM], K[LIM];
set<pair<int,int>>P[LIM];
int fnds(int x) {
	if(sp[x]==x) return x;
	return sp[x]=fnds(sp[x]);
}
int fndc(int x) {
	if(cy[x]==x) return x;
	return cy[x]=fndc(cy[x]);
}
void unis(int a, int b) {
	if(fnds(a)==fnds(b)) return;
	sp[fnds(b)]=fnds(a);
}
void unic(int a, int b) {
	a=fndc(a); b=fndc(b);
	if(ile[a]<ile[b]) swap(a, b);
	ile[a]+=ile[b];
	for(auto i : S[b]) S[a].insert(i);
	for(auto i : K[b]) {
		if(K[a].find(i)==K[a].end()) {
			K[a].insert(i);
			auto it=P[a].lower_bound({i, -1});
			while(it!=P[a].end()) {
				auto p=*it;
				if(p.st!=i) break;
				S[a].insert(p.nd);
				P[a].erase(it);
				it=P[a].lower_bound({i, -1});
			}
		}
	}
	for(auto i : P[b]) if(K[a].find(i.st)!=K[a].end()) S[a].insert(i.nd); else P[a].insert(i);
	cy[b]=a;
}
vector<int>find_reachable(vector<int>r, vector<int>u, vector<int>v, vector<int>c) {
	n=r.size();
	rep(i, n) {
		T[i]=r[i];
		K[i].insert(T[i]);
		sp[i]=i;
		cy[i]=i;
		nxt[i]=-1;
		ile[i]=1;
	}
	rep(i, u.size()) {
		if(c[i]==T[u[i]]) S[u[i]].insert(v[i]);
		else P[u[i]].insert({c[i], v[i]});
		if(c[i]==T[v[i]]) S[v[i]].insert(u[i]);
		else P[v[i]].insert({c[i], u[i]});
	}
	queue<int>q;
	rep(i, n) if(S[i].size()) q.push(i);
	while(!q.empty()) {
		int p=fndc(q.front()); q.pop();
		nxt[p]=fndc(*S[p].begin());
		S[p].erase(S[p].begin());
		if(fnds(p)!=fnds(nxt[p])) {
			unis(p, nxt[p]);
			continue;
		}
		vector<int>L;
		L.pb(p);
		int x=nxt[p];
		while(fndc(x)!=fndc(p)) {
			L.pb(x);
			x=nxt[x];
		}
		rep(i, (int)L.size()-1) unic(L[i], L[i+1]);
		p=fndc(p);
		nxt[p]=-1;
		while(!S[p].empty() && fndc(*S[p].begin())==p) S[p].erase(S[p].begin());
		if(!S[p].empty()) q.push(p);
	}
	vector<int>ans(n);
	int mi=n;
	rep(i, n) if(nxt[fndc(i)]==-1) mi=min(mi, ile[fndc(i)]);
	rep(i, n) if(nxt[fndc(i)]==-1 && ile[fndc(i)]==mi) ans[i]=1;
	return ans;
}

Compilation message

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
keys.cpp:55:2: note: in expansion of macro 'rep'
   55 |  rep(i, u.size()) {
      |  ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 42580 KB Output is correct
2 Correct 20 ms 42572 KB Output is correct
3 Correct 20 ms 42484 KB Output is correct
4 Correct 20 ms 42556 KB Output is correct
5 Correct 20 ms 42584 KB Output is correct
6 Correct 20 ms 42580 KB Output is correct
7 Correct 20 ms 42488 KB Output is correct
8 Correct 24 ms 42576 KB Output is correct
9 Correct 21 ms 42580 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 42580 KB Output is correct
2 Correct 20 ms 42572 KB Output is correct
3 Correct 20 ms 42484 KB Output is correct
4 Correct 20 ms 42556 KB Output is correct
5 Correct 20 ms 42584 KB Output is correct
6 Correct 20 ms 42580 KB Output is correct
7 Correct 20 ms 42488 KB Output is correct
8 Correct 24 ms 42576 KB Output is correct
9 Correct 21 ms 42580 KB Output is correct
10 Correct 21 ms 42576 KB Output is correct
11 Correct 20 ms 42576 KB Output is correct
12 Correct 22 ms 42620 KB Output is correct
13 Correct 19 ms 42508 KB Output is correct
14 Correct 21 ms 42600 KB Output is correct
15 Correct 20 ms 42568 KB Output is correct
16 Correct 20 ms 42496 KB Output is correct
17 Correct 20 ms 42580 KB Output is correct
18 Correct 25 ms 42556 KB Output is correct
19 Correct 20 ms 42532 KB Output is correct
20 Correct 20 ms 42580 KB Output is correct
21 Correct 20 ms 42580 KB Output is correct
22 Correct 19 ms 42612 KB Output is correct
23 Correct 20 ms 42576 KB Output is correct
24 Correct 20 ms 42552 KB Output is correct
25 Correct 19 ms 42608 KB Output is correct
26 Correct 23 ms 42580 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 42580 KB Output is correct
2 Correct 20 ms 42572 KB Output is correct
3 Correct 20 ms 42484 KB Output is correct
4 Correct 20 ms 42556 KB Output is correct
5 Correct 20 ms 42584 KB Output is correct
6 Correct 20 ms 42580 KB Output is correct
7 Correct 20 ms 42488 KB Output is correct
8 Correct 24 ms 42576 KB Output is correct
9 Correct 21 ms 42580 KB Output is correct
10 Correct 21 ms 42576 KB Output is correct
11 Correct 20 ms 42576 KB Output is correct
12 Correct 22 ms 42620 KB Output is correct
13 Correct 19 ms 42508 KB Output is correct
14 Correct 21 ms 42600 KB Output is correct
15 Correct 20 ms 42568 KB Output is correct
16 Correct 20 ms 42496 KB Output is correct
17 Correct 20 ms 42580 KB Output is correct
18 Correct 25 ms 42556 KB Output is correct
19 Correct 20 ms 42532 KB Output is correct
20 Correct 20 ms 42580 KB Output is correct
21 Correct 20 ms 42580 KB Output is correct
22 Correct 19 ms 42612 KB Output is correct
23 Correct 20 ms 42576 KB Output is correct
24 Correct 20 ms 42552 KB Output is correct
25 Correct 19 ms 42608 KB Output is correct
26 Correct 23 ms 42580 KB Output is correct
27 Correct 20 ms 42960 KB Output is correct
28 Correct 20 ms 42904 KB Output is correct
29 Correct 20 ms 42976 KB Output is correct
30 Correct 21 ms 42748 KB Output is correct
31 Correct 21 ms 42752 KB Output is correct
32 Correct 21 ms 42584 KB Output is correct
33 Correct 20 ms 42708 KB Output is correct
34 Correct 21 ms 42724 KB Output is correct
35 Correct 25 ms 42836 KB Output is correct
36 Correct 22 ms 42976 KB Output is correct
37 Correct 26 ms 43012 KB Output is correct
38 Correct 21 ms 43108 KB Output is correct
39 Correct 22 ms 43072 KB Output is correct
40 Correct 19 ms 42836 KB Output is correct
41 Correct 21 ms 42964 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 42580 KB Output is correct
2 Correct 20 ms 42572 KB Output is correct
3 Correct 20 ms 42484 KB Output is correct
4 Correct 20 ms 42556 KB Output is correct
5 Correct 20 ms 42584 KB Output is correct
6 Correct 20 ms 42580 KB Output is correct
7 Correct 20 ms 42488 KB Output is correct
8 Correct 24 ms 42576 KB Output is correct
9 Correct 21 ms 42580 KB Output is correct
10 Correct 476 ms 91520 KB Output is correct
11 Correct 715 ms 110440 KB Output is correct
12 Correct 73 ms 54604 KB Output is correct
13 Correct 409 ms 102720 KB Output is correct
14 Correct 227 ms 107980 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 42580 KB Output is correct
2 Correct 20 ms 42572 KB Output is correct
3 Correct 20 ms 42484 KB Output is correct
4 Correct 20 ms 42556 KB Output is correct
5 Correct 20 ms 42584 KB Output is correct
6 Correct 20 ms 42580 KB Output is correct
7 Correct 20 ms 42488 KB Output is correct
8 Correct 24 ms 42576 KB Output is correct
9 Correct 21 ms 42580 KB Output is correct
10 Correct 21 ms 42576 KB Output is correct
11 Correct 20 ms 42576 KB Output is correct
12 Correct 22 ms 42620 KB Output is correct
13 Correct 19 ms 42508 KB Output is correct
14 Correct 21 ms 42600 KB Output is correct
15 Correct 20 ms 42568 KB Output is correct
16 Correct 20 ms 42496 KB Output is correct
17 Correct 20 ms 42580 KB Output is correct
18 Correct 25 ms 42556 KB Output is correct
19 Correct 20 ms 42532 KB Output is correct
20 Correct 20 ms 42580 KB Output is correct
21 Correct 20 ms 42580 KB Output is correct
22 Correct 19 ms 42612 KB Output is correct
23 Correct 20 ms 42576 KB Output is correct
24 Correct 20 ms 42552 KB Output is correct
25 Correct 19 ms 42608 KB Output is correct
26 Correct 23 ms 42580 KB Output is correct
27 Correct 20 ms 42960 KB Output is correct
28 Correct 20 ms 42904 KB Output is correct
29 Correct 20 ms 42976 KB Output is correct
30 Correct 21 ms 42748 KB Output is correct
31 Correct 21 ms 42752 KB Output is correct
32 Correct 21 ms 42584 KB Output is correct
33 Correct 20 ms 42708 KB Output is correct
34 Correct 21 ms 42724 KB Output is correct
35 Correct 25 ms 42836 KB Output is correct
36 Correct 22 ms 42976 KB Output is correct
37 Correct 26 ms 43012 KB Output is correct
38 Correct 21 ms 43108 KB Output is correct
39 Correct 22 ms 43072 KB Output is correct
40 Correct 19 ms 42836 KB Output is correct
41 Correct 21 ms 42964 KB Output is correct
42 Correct 476 ms 91520 KB Output is correct
43 Correct 715 ms 110440 KB Output is correct
44 Correct 73 ms 54604 KB Output is correct
45 Correct 409 ms 102720 KB Output is correct
46 Correct 227 ms 107980 KB Output is correct
47 Correct 21 ms 42580 KB Output is correct
48 Correct 22 ms 42596 KB Output is correct
49 Correct 20 ms 42580 KB Output is correct
50 Correct 235 ms 114664 KB Output is correct
51 Correct 272 ms 114444 KB Output is correct
52 Correct 205 ms 87172 KB Output is correct
53 Correct 210 ms 87180 KB Output is correct
54 Correct 218 ms 87180 KB Output is correct
55 Correct 535 ms 95596 KB Output is correct
56 Correct 349 ms 109436 KB Output is correct
57 Correct 386 ms 109264 KB Output is correct
58 Correct 419 ms 110388 KB Output is correct
59 Correct 1159 ms 109724 KB Output is correct
60 Correct 1065 ms 115504 KB Output is correct
61 Correct 1076 ms 115836 KB Output is correct
62 Correct 980 ms 177972 KB Output is correct
63 Correct 252 ms 99808 KB Output is correct
64 Correct 28 ms 43636 KB Output is correct
65 Correct 24 ms 43624 KB Output is correct
66 Correct 894 ms 177300 KB Output is correct
67 Correct 41 ms 49128 KB Output is correct
68 Correct 50 ms 53500 KB Output is correct
69 Correct 1075 ms 109852 KB Output is correct
70 Correct 93 ms 64340 KB Output is correct
71 Correct 261 ms 108272 KB Output is correct
72 Correct 1113 ms 109716 KB Output is correct
73 Correct 864 ms 177816 KB Output is correct