oj.uz

Submission #478892

# Submission time Handle Problem Language Result Execution time Memory
478892 2021-10-09T02:08:37 Z couplefire Keys (IOI21_keys) C++17
100 / 100
 2790 ms 167180 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 300005;

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int n, m, r[N], u[N], v[N], c[N], fa1[N], fa2[N], siz[N], nxt[N];
set<int> good_keys[N];
map<int, vector<int>> bad_edges[N];
vector<int> good_edges[N];

int find1(int v){return v==fa1[v]?v:fa1[v]=find1(fa1[v]);}

int find2(int v){return v==fa2[v]?v:fa2[v]=find2(fa2[v]);}

void unite1(int u, int v){
    u = find1(u), v = find1(v);
    if(u==v) return;
    fa1[u] = v;
}

void unite2(int u, int v){
    u = find2(u), v = find2(v);
    if(u==v) return;
    fa2[u] = v; siz[v] += siz[u];
    good_edges[v].insert(good_edges[v].end(), good_edges[u].begin(), good_edges[u].end());
    for(auto x : good_keys[u]){
        good_keys[v].insert(x);
        if(bad_edges[v].count(x)){
            good_edges[v].insert(good_edges[v].end(), bad_edges[v][x].begin(), bad_edges[v][x].end());
            bad_edges[v].erase(x);
        }
    }
    for(auto [x, y] : bad_edges[u])
        if(good_keys[v].count(x))
            good_edges[v].insert(good_edges[v].end(), y.begin(), y.end());
        else
            bad_edges[v][x].insert(bad_edges[v][x].begin(), y.begin(), y.end()); 
}

vector<int> find_reachable(vector<int> _r, vector<int> _u, vector<int> _v, vector<int> _c){
    n = _r.size(), m = _u.size();
    for(int i = 0; i<n; ++i)
        r[i] = _r[i];
    for(int i = 0; i<m; ++i)
        u[i] = _u[i], v[i] = _v[i], c[i] = _c[i];
    vector<int> res(n, 0);
    vector<int> todo(n);
    iota(fa1, fa1+n, 0);
    iota(fa2, fa2+n, 0);
    iota(todo.begin(), todo.end(), 0);
    memset(nxt, -1, sizeof nxt);
    fill(siz, siz+n, 1);
    for(int i = 0; i<n; ++i)
        good_keys[i].insert(r[i]);
    for(int i = 0; i<m; ++i){
        if(c[i]!=r[u[i]]) bad_edges[u[i]][c[i]].push_back(v[i]);
        else good_edges[u[i]].push_back(v[i]);
        if(c[i]!=r[v[i]]) bad_edges[v[i]][c[i]].push_back(u[i]);
        else good_edges[v[i]].push_back(u[i]);
    }
    shuffle(todo.begin(), todo.end(), rng);
    while(!todo.empty()){
        int cur = todo.back(); todo.pop_back();
        cur = find2(cur);
        if(good_edges[cur].empty() || nxt[cur]>=0) continue;
        int to = good_edges[cur].back(); to = find2(to);
        good_edges[cur].pop_back();
        if(cur==to){
            todo.push_back(cur);
            continue;
        }
        if(find1(cur)!=find1(to)){
            nxt[cur] = to;
            unite1(cur, to);
            continue;
        }
        while(to!=cur){
            unite2(to, cur);
            to = find2(nxt[to]);
        } nxt[cur] = -1;
        todo.push_back(cur);
    }
    int ans = 1e9;
    for(int i = 0; i<n; ++i)
        if(find2(i)==i && nxt[i]==-1)
            ans = min(ans, siz[i]);
    for(int i = 0; i<n; ++i){
        int x = find2(i);
        res[i] = (nxt[x]==-1 && siz[x]==ans)?1:0;
    }
    return res;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 36664 KB Output is correct
2 Correct 20 ms 36720 KB Output is correct
3 Correct 22 ms 36616 KB Output is correct
4 Correct 19 ms 36684 KB Output is correct
5 Correct 19 ms 36620 KB Output is correct
6 Correct 19 ms 36684 KB Output is correct
7 Correct 19 ms 36732 KB Output is correct
8 Correct 21 ms 36684 KB Output is correct
9 Correct 19 ms 36736 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 36664 KB Output is correct
2 Correct 20 ms 36720 KB Output is correct
3 Correct 22 ms 36616 KB Output is correct
4 Correct 19 ms 36684 KB Output is correct
5 Correct 19 ms 36620 KB Output is correct
6 Correct 19 ms 36684 KB Output is correct
7 Correct 19 ms 36732 KB Output is correct
8 Correct 21 ms 36684 KB Output is correct
9 Correct 19 ms 36736 KB Output is correct
10 Correct 19 ms 36684 KB Output is correct
11 Correct 19 ms 36724 KB Output is correct
12 Correct 21 ms 36684 KB Output is correct
13 Correct 19 ms 36704 KB Output is correct
14 Correct 20 ms 36676 KB Output is correct
15 Correct 20 ms 36728 KB Output is correct
16 Correct 18 ms 36712 KB Output is correct
17 Correct 20 ms 36684 KB Output is correct
18 Correct 19 ms 36668 KB Output is correct
19 Correct 19 ms 36656 KB Output is correct
20 Correct 20 ms 36684 KB Output is correct
21 Correct 19 ms 36660 KB Output is correct
22 Correct 19 ms 36732 KB Output is correct
23 Correct 19 ms 36772 KB Output is correct
24 Correct 19 ms 36688 KB Output is correct
25 Correct 21 ms 36684 KB Output is correct
26 Correct 22 ms 36688 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 36664 KB Output is correct
2 Correct 20 ms 36720 KB Output is correct
3 Correct 22 ms 36616 KB Output is correct
4 Correct 19 ms 36684 KB Output is correct
5 Correct 19 ms 36620 KB Output is correct
6 Correct 19 ms 36684 KB Output is correct
7 Correct 19 ms 36732 KB Output is correct
8 Correct 21 ms 36684 KB Output is correct
9 Correct 19 ms 36736 KB Output is correct
10 Correct 19 ms 36684 KB Output is correct
11 Correct 19 ms 36724 KB Output is correct
12 Correct 21 ms 36684 KB Output is correct
13 Correct 19 ms 36704 KB Output is correct
14 Correct 20 ms 36676 KB Output is correct
15 Correct 20 ms 36728 KB Output is correct
16 Correct 18 ms 36712 KB Output is correct
17 Correct 20 ms 36684 KB Output is correct
18 Correct 19 ms 36668 KB Output is correct
19 Correct 19 ms 36656 KB Output is correct
20 Correct 20 ms 36684 KB Output is correct
21 Correct 19 ms 36660 KB Output is correct
22 Correct 19 ms 36732 KB Output is correct
23 Correct 19 ms 36772 KB Output is correct
24 Correct 19 ms 36688 KB Output is correct
25 Correct 21 ms 36684 KB Output is correct
26 Correct 22 ms 36688 KB Output is correct
27 Correct 21 ms 37324 KB Output is correct
28 Correct 21 ms 37320 KB Output is correct
29 Correct 21 ms 37320 KB Output is correct
30 Correct 21 ms 36996 KB Output is correct
31 Correct 20 ms 36916 KB Output is correct
32 Correct 19 ms 36812 KB Output is correct
33 Correct 22 ms 36932 KB Output is correct
34 Correct 21 ms 36952 KB Output is correct
35 Correct 20 ms 36940 KB Output is correct
36 Correct 23 ms 37292 KB Output is correct
37 Correct 21 ms 37276 KB Output is correct
38 Correct 22 ms 37324 KB Output is correct
39 Correct 23 ms 37352 KB Output is correct
40 Correct 21 ms 37068 KB Output is correct
41 Correct 20 ms 37316 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 36664 KB Output is correct
2 Correct 20 ms 36720 KB Output is correct
3 Correct 22 ms 36616 KB Output is correct
4 Correct 19 ms 36684 KB Output is correct
5 Correct 19 ms 36620 KB Output is correct
6 Correct 19 ms 36684 KB Output is correct
7 Correct 19 ms 36732 KB Output is correct
8 Correct 21 ms 36684 KB Output is correct
9 Correct 19 ms 36736 KB Output is correct
10 Correct 710 ms 104704 KB Output is correct
11 Correct 385 ms 85176 KB Output is correct
12 Correct 127 ms 52948 KB Output is correct
13 Correct 572 ms 107900 KB Output is correct
14 Correct 278 ms 82368 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 36664 KB Output is correct
2 Correct 20 ms 36720 KB Output is correct
3 Correct 22 ms 36616 KB Output is correct
4 Correct 19 ms 36684 KB Output is correct
5 Correct 19 ms 36620 KB Output is correct
6 Correct 19 ms 36684 KB Output is correct
7 Correct 19 ms 36732 KB Output is correct
8 Correct 21 ms 36684 KB Output is correct
9 Correct 19 ms 36736 KB Output is correct
10 Correct 19 ms 36684 KB Output is correct
11 Correct 19 ms 36724 KB Output is correct
12 Correct 21 ms 36684 KB Output is correct
13 Correct 19 ms 36704 KB Output is correct
14 Correct 20 ms 36676 KB Output is correct
15 Correct 20 ms 36728 KB Output is correct
16 Correct 18 ms 36712 KB Output is correct
17 Correct 20 ms 36684 KB Output is correct
18 Correct 19 ms 36668 KB Output is correct
19 Correct 19 ms 36656 KB Output is correct
20 Correct 20 ms 36684 KB Output is correct
21 Correct 19 ms 36660 KB Output is correct
22 Correct 19 ms 36732 KB Output is correct
23 Correct 19 ms 36772 KB Output is correct
24 Correct 19 ms 36688 KB Output is correct
25 Correct 21 ms 36684 KB Output is correct
26 Correct 22 ms 36688 KB Output is correct
27 Correct 21 ms 37324 KB Output is correct
28 Correct 21 ms 37320 KB Output is correct
29 Correct 21 ms 37320 KB Output is correct
30 Correct 21 ms 36996 KB Output is correct
31 Correct 20 ms 36916 KB Output is correct
32 Correct 19 ms 36812 KB Output is correct
33 Correct 22 ms 36932 KB Output is correct
34 Correct 21 ms 36952 KB Output is correct
35 Correct 20 ms 36940 KB Output is correct
36 Correct 23 ms 37292 KB Output is correct
37 Correct 21 ms 37276 KB Output is correct
38 Correct 22 ms 37324 KB Output is correct
39 Correct 23 ms 37352 KB Output is correct
40 Correct 21 ms 37068 KB Output is correct
41 Correct 20 ms 37316 KB Output is correct
42 Correct 710 ms 104704 KB Output is correct
43 Correct 385 ms 85176 KB Output is correct
44 Correct 127 ms 52948 KB Output is correct
45 Correct 572 ms 107900 KB Output is correct
46 Correct 278 ms 82368 KB Output is correct
47 Correct 24 ms 36676 KB Output is correct
48 Correct 21 ms 36728 KB Output is correct
49 Correct 24 ms 36684 KB Output is correct
50 Correct 278 ms 81680 KB Output is correct
51 Correct 267 ms 84160 KB Output is correct
52 Correct 296 ms 95428 KB Output is correct
53 Correct 304 ms 95432 KB Output is correct
54 Correct 298 ms 95428 KB Output is correct
55 Correct 731 ms 121852 KB Output is correct
56 Correct 369 ms 108328 KB Output is correct
57 Correct 295 ms 104760 KB Output is correct
58 Correct 622 ms 112932 KB Output is correct
59 Correct 1147 ms 129640 KB Output is correct
60 Correct 435 ms 105256 KB Output is correct
61 Correct 2790 ms 115956 KB Output is correct
62 Correct 1057 ms 167132 KB Output is correct
63 Correct 461 ms 109892 KB Output is correct
64 Correct 25 ms 37452 KB Output is correct
65 Correct 24 ms 37460 KB Output is correct
66 Correct 1066 ms 167180 KB Output is correct
67 Correct 39 ms 41292 KB Output is correct
68 Correct 59 ms 44384 KB Output is correct
69 Correct 1144 ms 129636 KB Output is correct
70 Correct 98 ms 51904 KB Output is correct
71 Correct 275 ms 82320 KB Output is correct
72 Correct 1138 ms 129680 KB Output is correct
73 Correct 1072 ms 167072 KB Output is correct