# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
435883 |
2021-06-23T21:14:15 Z |
Enkognit |
Keys (IOI21_keys) |
C++17 |
|
1769 ms |
74144 KB |
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define y1 Enkognit
using namespace std;
ll n, m, k, col[300001];
vector<pll> c[300001];
struct dsu
{
ll d[300001];
void make_sets(int h)
{
for (int i = 0; i < h; i++)
d[i]=i;
}
ll find_set(int h)
{
if (h==d[h]) return h; else return d[h]=find_set(d[h]);
}
bool unite_sets(int x,int y)
{
x=find_set(x);
y=find_set(y);
d[x]=y;
return x!=y;
}
} g;
vector<ll> vv[300001];
queue<ll> q;
bool QQ[300001];
vector<ll> lst1, lst2, lst3;
bool tt[300001], tl[300001], tu[300001];
void chk(int h)
{
//cout << " chk " << h << " " << vv[h].size() << "\n";
tl[h]=1;
lst2.pb(h);
while (vv[h].size())
{
if (!tt[vv[h].back()])
{
tt[vv[h].back()]=1;
q.push(vv[h].back());
}
vv[h].pop_back();
}
}
ll TT;
void add(int h)
{
//q.push(h);
//cout << " add\n";
chk(col[h]);
//cout << " end chk\n";
lst1.pb(h);
tt[h]=1;
if (g.find_set(TT)!=g.find_set(h)) return;
for (int i = 0; i < c[h].size(); i++)
if (!tt[c[h][i].fi])
{
//cout << "? " << c[h][i].fi << "\n";
if (tl[c[h][i].se])
{
q.push(c[h][i].fi);
tt[c[h][i].fi]=1;
}else
{
if (!tu[c[h][i].se])
{
tu[c[h][i].se]=1;
lst3.pb(c[h][i].se);
}
vv[c[h][i].se].pb(c[h][i].fi);
}
}
}
ll T=0;
void bfs(int h,vector<ll>& ee)
{
TT=h;
q.push(h);
tt[h]=1;
//cout << " bfs\n";
while (!q.empty())
{
ll x=q.front();
//cout << x << "\n";
q.pop();
ee.pb(x);
//cout << x << "\n";
if (g.find_set(x)!=g.find_set(h))
{
T=x;
}
//cout << x << "\n";
add(x);
//cout << " " << x << " " << q.size() << "\n";
}
while (lst1.size())
{
tt[lst1.back()]=0;
lst1.pop_back();
}
while (lst2.size())
{
tl[lst2.back()]=0;
lst2.pop_back();
}
while (lst3.size())
{
tu[lst3.back()]=0;
vv[lst3.back()].clear();
lst3.pop_back();
}
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> cc) {
n=r.size();
for (int i = 0; i < n; i++)
col[i]=r[i];
m=u.size();
g.make_sets(n);
for (int i = 0; i < m; i++)
{
c[u[i]].pb(mp(v[i], cc[i]));
c[v[i]].pb(mp(u[i], cc[i]));
}
vector<pll> merg;
vector<vector<ll> > comp;
ll lst=n*2;
do{
//cerr << "----\n";
ll kol=0;
merg.clear();
for (int i = 0; i < n; i++)
if (g.find_set(i)==i && !QQ[i])
{
kol++;
//cout << " " << i << " :\n";
T=-1;
vector<ll> zz;
bfs(i, zz);
//cout << "-\n";
if (T==-1)
{
//cout << "- " << i << "\n";
QQ[i]=1;
comp.pb(zz);
}else
{
merg.pb(mp(i, T));
}
//cout << "--\n";
}
assert(kol*2<=lst);
lst=kol;
//cout << "!\n";
for (int j = 0; j < merg.size(); j++)
{
g.unite_sets(merg[j].fi, merg[j].se);
//cout << merg[j].fi << " -> " << merg[j].se << "\n";
}
//system("pause");
}while (merg.size()>0);
//cout << "----\n";
ll mn=1e18;
for (int i = 0; i < comp.size(); i++)
mn=min(mn, (ll)comp[i].size());
vector<int> ans;
ans.resize(n, 0);
for (int i = 0; i < comp.size(); i++)
if (mn==comp[i].size())
{
for (int j = 0; j < comp[i].size(); j++)
ans[comp[i][j]]=1;
}
return ans;
}
Compilation message
keys.cpp: In function 'void add(int)':
keys.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int i = 0; i < c[h].size(); i++)
| ~~^~~~~~~~~~~~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:194:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | for (int j = 0; j < merg.size(); j++)
| ~~^~~~~~~~~~~~~
keys.cpp:206:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
206 | for (int i = 0; i < comp.size(); i++)
| ~~^~~~~~~~~~~~~
keys.cpp:212:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
212 | for (int i = 0; i < comp.size(); i++)
| ~~^~~~~~~~~~~~~
keys.cpp:213:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
213 | if (mn==comp[i].size())
| ~~^~~~~~~~~~~~~~~~
keys.cpp:215:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
215 | for (int j = 0; j < comp[i].size(); j++)
| ~~^~~~~~~~~~~~~~~~
keys.cpp:212:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
212 | for (int i = 0; i < comp.size(); i++)
| ^~~
keys.cpp:219:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
219 | return ans;
| ^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
14412 KB |
Output is correct |
2 |
Correct |
9 ms |
14416 KB |
Output is correct |
3 |
Correct |
10 ms |
14412 KB |
Output is correct |
4 |
Correct |
10 ms |
14412 KB |
Output is correct |
5 |
Correct |
10 ms |
14412 KB |
Output is correct |
6 |
Correct |
10 ms |
14324 KB |
Output is correct |
7 |
Correct |
10 ms |
14412 KB |
Output is correct |
8 |
Correct |
10 ms |
14412 KB |
Output is correct |
9 |
Correct |
10 ms |
14320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
14412 KB |
Output is correct |
2 |
Correct |
9 ms |
14416 KB |
Output is correct |
3 |
Correct |
10 ms |
14412 KB |
Output is correct |
4 |
Correct |
10 ms |
14412 KB |
Output is correct |
5 |
Correct |
10 ms |
14412 KB |
Output is correct |
6 |
Correct |
10 ms |
14324 KB |
Output is correct |
7 |
Correct |
10 ms |
14412 KB |
Output is correct |
8 |
Correct |
10 ms |
14412 KB |
Output is correct |
9 |
Correct |
10 ms |
14320 KB |
Output is correct |
10 |
Correct |
11 ms |
14340 KB |
Output is correct |
11 |
Correct |
10 ms |
14428 KB |
Output is correct |
12 |
Correct |
11 ms |
14460 KB |
Output is correct |
13 |
Correct |
10 ms |
14412 KB |
Output is correct |
14 |
Correct |
10 ms |
14412 KB |
Output is correct |
15 |
Correct |
10 ms |
14412 KB |
Output is correct |
16 |
Correct |
10 ms |
14328 KB |
Output is correct |
17 |
Correct |
11 ms |
14412 KB |
Output is correct |
18 |
Correct |
11 ms |
14412 KB |
Output is correct |
19 |
Correct |
10 ms |
14412 KB |
Output is correct |
20 |
Correct |
10 ms |
14420 KB |
Output is correct |
21 |
Correct |
10 ms |
14412 KB |
Output is correct |
22 |
Correct |
10 ms |
14412 KB |
Output is correct |
23 |
Correct |
10 ms |
14408 KB |
Output is correct |
24 |
Correct |
10 ms |
14412 KB |
Output is correct |
25 |
Correct |
10 ms |
14412 KB |
Output is correct |
26 |
Correct |
10 ms |
14388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
14412 KB |
Output is correct |
2 |
Correct |
9 ms |
14416 KB |
Output is correct |
3 |
Correct |
10 ms |
14412 KB |
Output is correct |
4 |
Correct |
10 ms |
14412 KB |
Output is correct |
5 |
Correct |
10 ms |
14412 KB |
Output is correct |
6 |
Correct |
10 ms |
14324 KB |
Output is correct |
7 |
Correct |
10 ms |
14412 KB |
Output is correct |
8 |
Correct |
10 ms |
14412 KB |
Output is correct |
9 |
Correct |
10 ms |
14320 KB |
Output is correct |
10 |
Correct |
11 ms |
14340 KB |
Output is correct |
11 |
Correct |
10 ms |
14428 KB |
Output is correct |
12 |
Correct |
11 ms |
14460 KB |
Output is correct |
13 |
Correct |
10 ms |
14412 KB |
Output is correct |
14 |
Correct |
10 ms |
14412 KB |
Output is correct |
15 |
Correct |
10 ms |
14412 KB |
Output is correct |
16 |
Correct |
10 ms |
14328 KB |
Output is correct |
17 |
Correct |
11 ms |
14412 KB |
Output is correct |
18 |
Correct |
11 ms |
14412 KB |
Output is correct |
19 |
Correct |
10 ms |
14412 KB |
Output is correct |
20 |
Correct |
10 ms |
14420 KB |
Output is correct |
21 |
Correct |
10 ms |
14412 KB |
Output is correct |
22 |
Correct |
10 ms |
14412 KB |
Output is correct |
23 |
Correct |
10 ms |
14408 KB |
Output is correct |
24 |
Correct |
10 ms |
14412 KB |
Output is correct |
25 |
Correct |
10 ms |
14412 KB |
Output is correct |
26 |
Correct |
10 ms |
14388 KB |
Output is correct |
27 |
Correct |
11 ms |
14668 KB |
Output is correct |
28 |
Correct |
12 ms |
14668 KB |
Output is correct |
29 |
Correct |
12 ms |
14772 KB |
Output is correct |
30 |
Correct |
11 ms |
14540 KB |
Output is correct |
31 |
Correct |
10 ms |
14580 KB |
Output is correct |
32 |
Correct |
11 ms |
14412 KB |
Output is correct |
33 |
Correct |
13 ms |
14540 KB |
Output is correct |
34 |
Correct |
11 ms |
14596 KB |
Output is correct |
35 |
Correct |
11 ms |
14540 KB |
Output is correct |
36 |
Correct |
12 ms |
14668 KB |
Output is correct |
37 |
Correct |
12 ms |
14668 KB |
Output is correct |
38 |
Correct |
12 ms |
14660 KB |
Output is correct |
39 |
Correct |
12 ms |
14668 KB |
Output is correct |
40 |
Correct |
11 ms |
14540 KB |
Output is correct |
41 |
Correct |
11 ms |
14648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
14412 KB |
Output is correct |
2 |
Correct |
9 ms |
14416 KB |
Output is correct |
3 |
Correct |
10 ms |
14412 KB |
Output is correct |
4 |
Correct |
10 ms |
14412 KB |
Output is correct |
5 |
Correct |
10 ms |
14412 KB |
Output is correct |
6 |
Correct |
10 ms |
14324 KB |
Output is correct |
7 |
Correct |
10 ms |
14412 KB |
Output is correct |
8 |
Correct |
10 ms |
14412 KB |
Output is correct |
9 |
Correct |
10 ms |
14320 KB |
Output is correct |
10 |
Correct |
370 ms |
45104 KB |
Output is correct |
11 |
Correct |
354 ms |
59892 KB |
Output is correct |
12 |
Correct |
74 ms |
21944 KB |
Output is correct |
13 |
Correct |
507 ms |
52468 KB |
Output is correct |
14 |
Correct |
263 ms |
64380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
14412 KB |
Output is correct |
2 |
Correct |
9 ms |
14416 KB |
Output is correct |
3 |
Correct |
10 ms |
14412 KB |
Output is correct |
4 |
Correct |
10 ms |
14412 KB |
Output is correct |
5 |
Correct |
10 ms |
14412 KB |
Output is correct |
6 |
Correct |
10 ms |
14324 KB |
Output is correct |
7 |
Correct |
10 ms |
14412 KB |
Output is correct |
8 |
Correct |
10 ms |
14412 KB |
Output is correct |
9 |
Correct |
10 ms |
14320 KB |
Output is correct |
10 |
Correct |
11 ms |
14340 KB |
Output is correct |
11 |
Correct |
10 ms |
14428 KB |
Output is correct |
12 |
Correct |
11 ms |
14460 KB |
Output is correct |
13 |
Correct |
10 ms |
14412 KB |
Output is correct |
14 |
Correct |
10 ms |
14412 KB |
Output is correct |
15 |
Correct |
10 ms |
14412 KB |
Output is correct |
16 |
Correct |
10 ms |
14328 KB |
Output is correct |
17 |
Correct |
11 ms |
14412 KB |
Output is correct |
18 |
Correct |
11 ms |
14412 KB |
Output is correct |
19 |
Correct |
10 ms |
14412 KB |
Output is correct |
20 |
Correct |
10 ms |
14420 KB |
Output is correct |
21 |
Correct |
10 ms |
14412 KB |
Output is correct |
22 |
Correct |
10 ms |
14412 KB |
Output is correct |
23 |
Correct |
10 ms |
14408 KB |
Output is correct |
24 |
Correct |
10 ms |
14412 KB |
Output is correct |
25 |
Correct |
10 ms |
14412 KB |
Output is correct |
26 |
Correct |
10 ms |
14388 KB |
Output is correct |
27 |
Correct |
11 ms |
14668 KB |
Output is correct |
28 |
Correct |
12 ms |
14668 KB |
Output is correct |
29 |
Correct |
12 ms |
14772 KB |
Output is correct |
30 |
Correct |
11 ms |
14540 KB |
Output is correct |
31 |
Correct |
10 ms |
14580 KB |
Output is correct |
32 |
Correct |
11 ms |
14412 KB |
Output is correct |
33 |
Correct |
13 ms |
14540 KB |
Output is correct |
34 |
Correct |
11 ms |
14596 KB |
Output is correct |
35 |
Correct |
11 ms |
14540 KB |
Output is correct |
36 |
Correct |
12 ms |
14668 KB |
Output is correct |
37 |
Correct |
12 ms |
14668 KB |
Output is correct |
38 |
Correct |
12 ms |
14660 KB |
Output is correct |
39 |
Correct |
12 ms |
14668 KB |
Output is correct |
40 |
Correct |
11 ms |
14540 KB |
Output is correct |
41 |
Correct |
11 ms |
14648 KB |
Output is correct |
42 |
Correct |
370 ms |
45104 KB |
Output is correct |
43 |
Correct |
354 ms |
59892 KB |
Output is correct |
44 |
Correct |
74 ms |
21944 KB |
Output is correct |
45 |
Correct |
507 ms |
52468 KB |
Output is correct |
46 |
Correct |
263 ms |
64380 KB |
Output is correct |
47 |
Correct |
11 ms |
14412 KB |
Output is correct |
48 |
Correct |
9 ms |
14352 KB |
Output is correct |
49 |
Correct |
10 ms |
14368 KB |
Output is correct |
50 |
Correct |
251 ms |
63576 KB |
Output is correct |
51 |
Correct |
338 ms |
64012 KB |
Output is correct |
52 |
Correct |
415 ms |
50224 KB |
Output is correct |
53 |
Correct |
420 ms |
50212 KB |
Output is correct |
54 |
Correct |
431 ms |
50084 KB |
Output is correct |
55 |
Correct |
403 ms |
47172 KB |
Output is correct |
56 |
Correct |
589 ms |
61604 KB |
Output is correct |
57 |
Correct |
419 ms |
74144 KB |
Output is correct |
58 |
Correct |
424 ms |
61844 KB |
Output is correct |
59 |
Correct |
680 ms |
58216 KB |
Output is correct |
60 |
Correct |
484 ms |
51552 KB |
Output is correct |
61 |
Correct |
577 ms |
60536 KB |
Output is correct |
62 |
Correct |
1769 ms |
50036 KB |
Output is correct |
63 |
Correct |
248 ms |
48556 KB |
Output is correct |
64 |
Correct |
14 ms |
15296 KB |
Output is correct |
65 |
Correct |
16 ms |
15296 KB |
Output is correct |
66 |
Correct |
1678 ms |
50080 KB |
Output is correct |
67 |
Correct |
35 ms |
19004 KB |
Output is correct |
68 |
Correct |
52 ms |
22348 KB |
Output is correct |
69 |
Correct |
648 ms |
58288 KB |
Output is correct |
70 |
Correct |
94 ms |
30396 KB |
Output is correct |
71 |
Correct |
266 ms |
64512 KB |
Output is correct |
72 |
Correct |
684 ms |
58292 KB |
Output is correct |
73 |
Correct |
1645 ms |
51064 KB |
Output is correct |