# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
447695 |
2021-07-27T10:54:10 Z |
blue |
Keys (IOI21_keys) |
C++17 |
|
1670 ms |
144312 KB |
#include "keys.h"
#include <set>
#include <iostream>
using namespace std;
const int maxN = 300'000;
int N;
int M;
struct edge
{
int v;
int c;
};
bool operator < (edge A, edge B)
{
return A.c < B.c;
}
set<int> good_edge[maxN]; //over SCCs, does not use labels
multiset<edge> bad_edge[maxN];
set<int> keys[maxN];
vector<int> scc_label(maxN);
vector<int> scc_list[maxN];
vector<int> wcc_label(maxN);
vector<int> wcc_list[maxN];
vector<int> func_parent(maxN); //itself if this is a root. //access only by label.
void scc_join(int u, int v)
{
u = scc_label[u];
v = scc_label[v];
if(u == v) return;
if(scc_list[u].size() < scc_list[v].size()) swap(u, v);
int new_func_parent;
if(scc_label[ func_parent[u] ] == v)
new_func_parent = scc_label[ func_parent[v] ];
else
new_func_parent = scc_label[ func_parent[u] ];
//also handle good edges, bad edges, keys
for(int k: keys[v])
{
while(1)
{
multiset<edge>::iterator it = bad_edge[u].find(edge{-1, k});
if(it == bad_edge[u].end()) break;
good_edge[u].insert(it->v);
bad_edge[u].erase(it);
}
keys[u].insert(k);
}
keys[v].clear();
for(int g: good_edge[v])
{
good_edge[u].insert(g);
}
good_edge[v].clear();
for(edge b: bad_edge[v])
{
if(keys[u].find(b.c) == keys[u].end())
bad_edge[u].insert(b);
else
good_edge[u].insert(b.v);
}
bad_edge[v].clear();
for(int x: scc_list[v])
{
scc_label[x] = u;
scc_list[u].push_back(x);
}
scc_list[v].clear();
func_parent[u] = new_func_parent;
// cerr << "after joining " << v << " and " << u << '\n';
// for(int i = 0; i < N; i++)
// cerr << i << ' ' << scc_label[i] << ' ' << wcc_label[i] << ' ' << func_parent[ scc_label[i] ] << '\n';
// cerr << "\n\n\n";
}
void wcc_join(int u, int v)
{
u = wcc_label[u];
v = wcc_label[v];
if(u == v) return;
if(wcc_list[u].size() < wcc_list[v].size()) swap(u, v);
for(int x: wcc_list[v])
{
wcc_label[x] = u;
wcc_list[u].push_back(x);
}
wcc_list[v].clear();
}
bool in_wcc(int v, int u) //return whether v is in the WCC rooted at u (u and v are both scc labels)
{
// cerr << "in wcc " << v << ' ' << u << ' ' << ((wcc_label[v] == wcc_label[u]) && (scc_label[func_parent[scc_label[u]]] == scc_label[u])) << '\n';
// cerr << wcc_label[v] << ' ' << wcc_label[u] << '\n';
return (wcc_label[v] == wcc_label[u]) && (scc_label[func_parent[u]] == u);
}
void compress(int v) //compress the chain from v to the root (v is a scc label)
{
// cerr << "compress " << v << '\n';
v = scc_label[v];
// cerr << "compressing " << v << '\n';
if(scc_label[ func_parent[v] ] == v) return;
while(1)
{
// cerr << "? " << v << ' ' << scc_label[ func_parent[v] ] << '\n';
if(scc_label[ func_parent[v] ] == v) return;
else
{
scc_join(v, scc_label[ func_parent[v] ]);
v = scc_label[v];
}
}
}
void addChild(int u, int v) //add v as a functional graph child of u
{
u = scc_label[u];
v = scc_label[v];
func_parent[v] = u;
wcc_join(u, v);
// cerr << "after adding " << v << " as child of " << u << '\n';
// for(int i = 0; i < N; i++)
// cerr << i << ' ' << scc_label[i] << ' ' << wcc_label[i] << ' ' << func_parent[ scc_label[i] ] << '\n';
// cerr << "\n\n\n";
}
vector<int> find_reachable(vector<int> r1, vector<int> u1, vector<int> v1, vector<int> c1)
{
N = r1.size();
M = u1.size();
for(int i = 0; i < N; i++)
{
keys[i].insert(r1[i]);
scc_label[i] = i;
scc_list[i].push_back(i);
wcc_label[i] = i;
wcc_list[i].push_back(i);
func_parent[i] = i;
}
for(int j = 0; j < M; j++)
{
if(keys[ u1[j] ].find( c1[j] ) == keys[ u1[j] ].end())
{
bad_edge[ u1[j] ].insert( edge{v1[j], c1[j]} );
}
else
{
good_edge[ u1[j] ].insert( v1[j] );
}
if(keys[ v1[j] ].find( c1[j] ) == keys[ v1[j] ].end())
{
bad_edge[ v1[j] ].insert( edge{u1[j], c1[j]} );
}
else
{
good_edge[ v1[j] ].insert( u1[j] );
}
}
// cerr << "\n\n\n";
// cerr << "initial state: \n";
// for(int i = 0; i < N; i++)
// cerr << i << ' ' << scc_label[i] << ' ' << wcc_label[i] << ' ' << func_parent[ scc_label[i] ] << '\n';
// cerr << "\n\n\n";
for(int u_temp = 0; u_temp < N; u_temp++)
{
int u = u_temp;
if(scc_label[u] != u) continue; //u is a scc label
if(scc_label[ func_parent[u] ] != u) continue; //u is a functional graph root.
// cerr << "\n\n\n\n\n\n\n";
// cerr << "new value of u = " << u << '\n';
while(!good_edge[u].empty())
{
int v = *good_edge[u].begin();
good_edge[u].erase(v);
v = scc_label[v];
if(v == u) continue;
if(in_wcc(v, u))
compress(v);
else
{
addChild(v, u);
// cerr << "breaking\n";
break;
}
u = scc_label[u]; //IMPORTANT!
}
}
vector<int> res_list;
int min_reach = N;
for(int i = 0; i < N; i++)
{
if(scc_label[ func_parent[ scc_label[i] ] ] != scc_label[i]) continue;
if(scc_list[ scc_label[i] ].size() < min_reach)
{
min_reach = scc_list[ scc_label[i] ].size();
res_list.clear();
res_list.push_back(i);
}
else if(scc_list[ scc_label[i] ].size() == min_reach)
{
res_list.push_back(i);
}
}
vector<int> res(N, 0);
for(int R: res_list)
res[R] = 1;
return res;
}
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:263:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
263 | if(scc_list[ scc_label[i] ].size() < min_reach)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
keys.cpp:269:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
269 | else if(scc_list[ scc_label[i] ].size() == min_reach)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
60100 KB |
Output is correct |
2 |
Correct |
32 ms |
60172 KB |
Output is correct |
3 |
Correct |
31 ms |
60172 KB |
Output is correct |
4 |
Correct |
34 ms |
60204 KB |
Output is correct |
5 |
Correct |
34 ms |
60128 KB |
Output is correct |
6 |
Correct |
33 ms |
60076 KB |
Output is correct |
7 |
Correct |
32 ms |
60172 KB |
Output is correct |
8 |
Correct |
34 ms |
60156 KB |
Output is correct |
9 |
Correct |
32 ms |
60224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
60100 KB |
Output is correct |
2 |
Correct |
32 ms |
60172 KB |
Output is correct |
3 |
Correct |
31 ms |
60172 KB |
Output is correct |
4 |
Correct |
34 ms |
60204 KB |
Output is correct |
5 |
Correct |
34 ms |
60128 KB |
Output is correct |
6 |
Correct |
33 ms |
60076 KB |
Output is correct |
7 |
Correct |
32 ms |
60172 KB |
Output is correct |
8 |
Correct |
34 ms |
60156 KB |
Output is correct |
9 |
Correct |
32 ms |
60224 KB |
Output is correct |
10 |
Correct |
33 ms |
60172 KB |
Output is correct |
11 |
Correct |
32 ms |
60164 KB |
Output is correct |
12 |
Correct |
31 ms |
60108 KB |
Output is correct |
13 |
Correct |
34 ms |
60056 KB |
Output is correct |
14 |
Correct |
33 ms |
60064 KB |
Output is correct |
15 |
Correct |
32 ms |
60176 KB |
Output is correct |
16 |
Correct |
33 ms |
60068 KB |
Output is correct |
17 |
Correct |
33 ms |
60196 KB |
Output is correct |
18 |
Correct |
32 ms |
60108 KB |
Output is correct |
19 |
Correct |
34 ms |
60084 KB |
Output is correct |
20 |
Correct |
33 ms |
60192 KB |
Output is correct |
21 |
Correct |
33 ms |
60164 KB |
Output is correct |
22 |
Correct |
32 ms |
60256 KB |
Output is correct |
23 |
Correct |
33 ms |
60224 KB |
Output is correct |
24 |
Correct |
32 ms |
60180 KB |
Output is correct |
25 |
Correct |
33 ms |
60160 KB |
Output is correct |
26 |
Correct |
33 ms |
60164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
60100 KB |
Output is correct |
2 |
Correct |
32 ms |
60172 KB |
Output is correct |
3 |
Correct |
31 ms |
60172 KB |
Output is correct |
4 |
Correct |
34 ms |
60204 KB |
Output is correct |
5 |
Correct |
34 ms |
60128 KB |
Output is correct |
6 |
Correct |
33 ms |
60076 KB |
Output is correct |
7 |
Correct |
32 ms |
60172 KB |
Output is correct |
8 |
Correct |
34 ms |
60156 KB |
Output is correct |
9 |
Correct |
32 ms |
60224 KB |
Output is correct |
10 |
Correct |
33 ms |
60172 KB |
Output is correct |
11 |
Correct |
32 ms |
60164 KB |
Output is correct |
12 |
Correct |
31 ms |
60108 KB |
Output is correct |
13 |
Correct |
34 ms |
60056 KB |
Output is correct |
14 |
Correct |
33 ms |
60064 KB |
Output is correct |
15 |
Correct |
32 ms |
60176 KB |
Output is correct |
16 |
Correct |
33 ms |
60068 KB |
Output is correct |
17 |
Correct |
33 ms |
60196 KB |
Output is correct |
18 |
Correct |
32 ms |
60108 KB |
Output is correct |
19 |
Correct |
34 ms |
60084 KB |
Output is correct |
20 |
Correct |
33 ms |
60192 KB |
Output is correct |
21 |
Correct |
33 ms |
60164 KB |
Output is correct |
22 |
Correct |
32 ms |
60256 KB |
Output is correct |
23 |
Correct |
33 ms |
60224 KB |
Output is correct |
24 |
Correct |
32 ms |
60180 KB |
Output is correct |
25 |
Correct |
33 ms |
60160 KB |
Output is correct |
26 |
Correct |
33 ms |
60164 KB |
Output is correct |
27 |
Correct |
34 ms |
60648 KB |
Output is correct |
28 |
Correct |
33 ms |
60620 KB |
Output is correct |
29 |
Correct |
34 ms |
60644 KB |
Output is correct |
30 |
Correct |
34 ms |
60328 KB |
Output is correct |
31 |
Correct |
36 ms |
60328 KB |
Output is correct |
32 |
Correct |
32 ms |
60228 KB |
Output is correct |
33 |
Correct |
33 ms |
60312 KB |
Output is correct |
34 |
Correct |
33 ms |
60388 KB |
Output is correct |
35 |
Correct |
33 ms |
60348 KB |
Output is correct |
36 |
Correct |
36 ms |
60584 KB |
Output is correct |
37 |
Correct |
36 ms |
60628 KB |
Output is correct |
38 |
Correct |
36 ms |
60712 KB |
Output is correct |
39 |
Correct |
36 ms |
60656 KB |
Output is correct |
40 |
Correct |
34 ms |
60356 KB |
Output is correct |
41 |
Correct |
37 ms |
60464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
60100 KB |
Output is correct |
2 |
Correct |
32 ms |
60172 KB |
Output is correct |
3 |
Correct |
31 ms |
60172 KB |
Output is correct |
4 |
Correct |
34 ms |
60204 KB |
Output is correct |
5 |
Correct |
34 ms |
60128 KB |
Output is correct |
6 |
Correct |
33 ms |
60076 KB |
Output is correct |
7 |
Correct |
32 ms |
60172 KB |
Output is correct |
8 |
Correct |
34 ms |
60156 KB |
Output is correct |
9 |
Correct |
32 ms |
60224 KB |
Output is correct |
10 |
Correct |
672 ms |
114712 KB |
Output is correct |
11 |
Correct |
794 ms |
140544 KB |
Output is correct |
12 |
Correct |
147 ms |
74436 KB |
Output is correct |
13 |
Correct |
703 ms |
131928 KB |
Output is correct |
14 |
Correct |
336 ms |
140540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
60100 KB |
Output is correct |
2 |
Correct |
32 ms |
60172 KB |
Output is correct |
3 |
Correct |
31 ms |
60172 KB |
Output is correct |
4 |
Correct |
34 ms |
60204 KB |
Output is correct |
5 |
Correct |
34 ms |
60128 KB |
Output is correct |
6 |
Correct |
33 ms |
60076 KB |
Output is correct |
7 |
Correct |
32 ms |
60172 KB |
Output is correct |
8 |
Correct |
34 ms |
60156 KB |
Output is correct |
9 |
Correct |
32 ms |
60224 KB |
Output is correct |
10 |
Correct |
33 ms |
60172 KB |
Output is correct |
11 |
Correct |
32 ms |
60164 KB |
Output is correct |
12 |
Correct |
31 ms |
60108 KB |
Output is correct |
13 |
Correct |
34 ms |
60056 KB |
Output is correct |
14 |
Correct |
33 ms |
60064 KB |
Output is correct |
15 |
Correct |
32 ms |
60176 KB |
Output is correct |
16 |
Correct |
33 ms |
60068 KB |
Output is correct |
17 |
Correct |
33 ms |
60196 KB |
Output is correct |
18 |
Correct |
32 ms |
60108 KB |
Output is correct |
19 |
Correct |
34 ms |
60084 KB |
Output is correct |
20 |
Correct |
33 ms |
60192 KB |
Output is correct |
21 |
Correct |
33 ms |
60164 KB |
Output is correct |
22 |
Correct |
32 ms |
60256 KB |
Output is correct |
23 |
Correct |
33 ms |
60224 KB |
Output is correct |
24 |
Correct |
32 ms |
60180 KB |
Output is correct |
25 |
Correct |
33 ms |
60160 KB |
Output is correct |
26 |
Correct |
33 ms |
60164 KB |
Output is correct |
27 |
Correct |
34 ms |
60648 KB |
Output is correct |
28 |
Correct |
33 ms |
60620 KB |
Output is correct |
29 |
Correct |
34 ms |
60644 KB |
Output is correct |
30 |
Correct |
34 ms |
60328 KB |
Output is correct |
31 |
Correct |
36 ms |
60328 KB |
Output is correct |
32 |
Correct |
32 ms |
60228 KB |
Output is correct |
33 |
Correct |
33 ms |
60312 KB |
Output is correct |
34 |
Correct |
33 ms |
60388 KB |
Output is correct |
35 |
Correct |
33 ms |
60348 KB |
Output is correct |
36 |
Correct |
36 ms |
60584 KB |
Output is correct |
37 |
Correct |
36 ms |
60628 KB |
Output is correct |
38 |
Correct |
36 ms |
60712 KB |
Output is correct |
39 |
Correct |
36 ms |
60656 KB |
Output is correct |
40 |
Correct |
34 ms |
60356 KB |
Output is correct |
41 |
Correct |
37 ms |
60464 KB |
Output is correct |
42 |
Correct |
672 ms |
114712 KB |
Output is correct |
43 |
Correct |
794 ms |
140544 KB |
Output is correct |
44 |
Correct |
147 ms |
74436 KB |
Output is correct |
45 |
Correct |
703 ms |
131928 KB |
Output is correct |
46 |
Correct |
336 ms |
140540 KB |
Output is correct |
47 |
Correct |
32 ms |
60116 KB |
Output is correct |
48 |
Correct |
32 ms |
60052 KB |
Output is correct |
49 |
Correct |
33 ms |
60156 KB |
Output is correct |
50 |
Correct |
362 ms |
140364 KB |
Output is correct |
51 |
Correct |
398 ms |
143552 KB |
Output is correct |
52 |
Correct |
425 ms |
113476 KB |
Output is correct |
53 |
Correct |
431 ms |
113464 KB |
Output is correct |
54 |
Correct |
430 ms |
113480 KB |
Output is correct |
55 |
Correct |
827 ms |
115820 KB |
Output is correct |
56 |
Correct |
681 ms |
144312 KB |
Output is correct |
57 |
Correct |
628 ms |
141016 KB |
Output is correct |
58 |
Correct |
661 ms |
140908 KB |
Output is correct |
59 |
Correct |
1670 ms |
133924 KB |
Output is correct |
60 |
Correct |
1316 ms |
133672 KB |
Output is correct |
61 |
Correct |
1411 ms |
133916 KB |
Output is correct |
62 |
Correct |
1459 ms |
123188 KB |
Output is correct |
63 |
Correct |
338 ms |
123072 KB |
Output is correct |
64 |
Correct |
38 ms |
61524 KB |
Output is correct |
65 |
Correct |
38 ms |
61508 KB |
Output is correct |
66 |
Correct |
1482 ms |
123724 KB |
Output is correct |
67 |
Correct |
61 ms |
68164 KB |
Output is correct |
68 |
Correct |
79 ms |
73648 KB |
Output is correct |
69 |
Correct |
1551 ms |
134636 KB |
Output is correct |
70 |
Correct |
130 ms |
87272 KB |
Output is correct |
71 |
Correct |
330 ms |
142040 KB |
Output is correct |
72 |
Correct |
1579 ms |
134280 KB |
Output is correct |
73 |
Correct |
1452 ms |
123676 KB |
Output is correct |