oj.uz

Submission #872639

# Submission time Handle Problem Language Result Execution time Memory
872639 2023-11-13T13:24:39 Z lighton Keys (IOI21_keys) C++17
100 / 100
 2114 ms 1273288 KB 
#include<bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
using namespace std;
using pi = pair<int,int>;
struct CC{
    int grp[300001];
    int fi(int x){
        if(grp[x] == x) return x;
        else return grp[x] = fi(grp[x]);
    }
    void un(int x, int y){
        x = fi(x);
        y = fi(y);
        assert(x!=y);
        grp[x] = y;
    }
} cc;
vector<int> R,U,V,C;
struct CYCLES{
    int grp[300001];
    int siz[300001];
    int toward[300001];
    set<int> components[300001];
    set<int> colors[300001];
    map<int, queue<int> > remainedge[300001];
    queue<int> remaincolor[300001];
    int fi(int x){
        if(grp[x] == x) return x;
        else return grp[x] = fi(grp[x]);
    }
    void un(int x, int y){
        x = fi(x);
        y = fi(y);
        assert(x!=y);
        if(siz[x] > siz[y]) swap(x,y);
        siz[y] += siz[x];
        for(auto &i :components[x]){
            components[y].insert(i);
        }
        for(auto &i :colors[x]){
            if(colors[y].find(i) == colors[y].end()) {
                colors[y].insert(i);
                remaincolor[y].push(i);
            }
        }
        for(auto &i : remainedge[x]){
            if(i.second.size() && colors[y].find(i.first) != colors[y].end()) remaincolor[y].push(i.first);
            while(i.second.size()){
                remainedge[y][i.first].push(i.second.front());
                i.second.pop();
            }
        }
        grp[x] = y;
        if(components[y].find(toward[y]) == components[y].end()){
            toward[y] = toward[y];
        }
        else if(components[y].find(toward[x]) == components[y].end()){
            toward[y] = toward[x];
        }
        else toward[y] = -1;
    }
    void findedge(int x){
        x=fi(x);
        if(toward[x] != -1 && components[x].find(toward[x]) == components[x].end()) return;
        toward[x] = -1;
        while(remaincolor[x].size()){
            int i = remaincolor[x].front();
            while(remainedge[x][i].size()){
                int j = remainedge[x][i].front();
                if(components[x].find(j) == components[x].end()) toward[x] = j;
                else remainedge[x][i].pop();
                if(toward[x] != -1) break;
            }
            if(toward[x] != -1) break;
            remaincolor[x].pop();
        }
    }
} cycles;
int N,M;
vector<pi> adj[300001];
int chk[300001];
vector<pi> candidate;
int ans = 1e9;
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	N = r.size();
    M = u.size();
    R=r;U=u;V=v;C=c;

    for(int i = 0; i<M; i++){
        adj[U[i]].push_back({V[i],C[i]});
        adj[V[i]].push_back({U[i],C[i]});
    }
    //init
    for(int i = 0; i<N; i++){
        cc.grp[i] = i;
        cycles.grp[i] = i;
    }

    for(int i = 0; i<N; i++){
        cycles.toward[i] = -1;
        cycles.components[i].insert(i);
        cycles.colors[i].insert(R[i]);
        cycles.remaincolor[i].push(R[i]);
        for(auto &j : adj[i]){
            cycles.remainedge[i][j.second].push(j.first);
            cycles.siz[i]++;
        }
        cycles.findedge(i);

        while(cycles.toward[cycles.fi(i)] != -1 && cc.fi(cycles.toward[cycles.fi(i)]) == cc.fi(i)){
            cycles.un(i,cycles.toward[cycles.fi(i)]);
            cycles.findedge(i);
        }
        if(cycles.toward[cycles.fi(i)] == -1){
            int tmp = cycles.components[cycles.fi(i)].size();
            for(int j : cycles.components[cycles.fi(i)]) candidate.push_back({j,tmp});
            ans = min(ans,tmp);
        }
        else{
            cc.un(cycles.toward[cycles.fi(i)],i);
        }
    }

    std::vector<int> ret(N, 0);
    for(auto &[i,j] : candidate){
        if(j==ans) ret[i] = 1;
    }
	return ret;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 256640 KB Output is correct
2 Correct 111 ms 256688 KB Output is correct
3 Correct 115 ms 256872 KB Output is correct
4 Correct 113 ms 257020 KB Output is correct
5 Correct 109 ms 256860 KB Output is correct
6 Correct 107 ms 256848 KB Output is correct
7 Correct 106 ms 256884 KB Output is correct
8 Correct 108 ms 256848 KB Output is correct
9 Correct 110 ms 256848 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 256640 KB Output is correct
2 Correct 111 ms 256688 KB Output is correct
3 Correct 115 ms 256872 KB Output is correct
4 Correct 113 ms 257020 KB Output is correct
5 Correct 109 ms 256860 KB Output is correct
6 Correct 107 ms 256848 KB Output is correct
7 Correct 106 ms 256884 KB Output is correct
8 Correct 108 ms 256848 KB Output is correct
9 Correct 110 ms 256848 KB Output is correct
10 Correct 107 ms 257260 KB Output is correct
11 Correct 114 ms 257104 KB Output is correct
12 Correct 112 ms 257208 KB Output is correct
13 Correct 109 ms 256880 KB Output is correct
14 Correct 110 ms 256744 KB Output is correct
15 Correct 110 ms 257288 KB Output is correct
16 Correct 108 ms 256904 KB Output is correct
17 Correct 108 ms 256848 KB Output is correct
18 Correct 106 ms 256852 KB Output is correct
19 Correct 112 ms 256704 KB Output is correct
20 Correct 108 ms 256872 KB Output is correct
21 Correct 109 ms 257172 KB Output is correct
22 Correct 107 ms 256852 KB Output is correct
23 Correct 111 ms 257124 KB Output is correct
24 Correct 108 ms 257292 KB Output is correct
25 Correct 108 ms 257104 KB Output is correct
26 Correct 107 ms 257200 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 256640 KB Output is correct
2 Correct 111 ms 256688 KB Output is correct
3 Correct 115 ms 256872 KB Output is correct
4 Correct 113 ms 257020 KB Output is correct
5 Correct 109 ms 256860 KB Output is correct
6 Correct 107 ms 256848 KB Output is correct
7 Correct 106 ms 256884 KB Output is correct
8 Correct 108 ms 256848 KB Output is correct
9 Correct 110 ms 256848 KB Output is correct
10 Correct 107 ms 257260 KB Output is correct
11 Correct 114 ms 257104 KB Output is correct
12 Correct 112 ms 257208 KB Output is correct
13 Correct 109 ms 256880 KB Output is correct
14 Correct 110 ms 256744 KB Output is correct
15 Correct 110 ms 257288 KB Output is correct
16 Correct 108 ms 256904 KB Output is correct
17 Correct 108 ms 256848 KB Output is correct
18 Correct 106 ms 256852 KB Output is correct
19 Correct 112 ms 256704 KB Output is correct
20 Correct 108 ms 256872 KB Output is correct
21 Correct 109 ms 257172 KB Output is correct
22 Correct 107 ms 256852 KB Output is correct
23 Correct 111 ms 257124 KB Output is correct
24 Correct 108 ms 257292 KB Output is correct
25 Correct 108 ms 257104 KB Output is correct
26 Correct 107 ms 257200 KB Output is correct
27 Correct 124 ms 260688 KB Output is correct
28 Correct 131 ms 260944 KB Output is correct
29 Correct 129 ms 260688 KB Output is correct
30 Correct 108 ms 258900 KB Output is correct
31 Correct 119 ms 258388 KB Output is correct
32 Correct 115 ms 257872 KB Output is correct
33 Correct 109 ms 258972 KB Output is correct
34 Correct 108 ms 258388 KB Output is correct
35 Correct 110 ms 258896 KB Output is correct
36 Correct 123 ms 259864 KB Output is correct
37 Correct 128 ms 260952 KB Output is correct
38 Correct 121 ms 260148 KB Output is correct
39 Correct 126 ms 261520 KB Output is correct
40 Correct 108 ms 259296 KB Output is correct
41 Correct 114 ms 260944 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 256640 KB Output is correct
2 Correct 111 ms 256688 KB Output is correct
3 Correct 115 ms 256872 KB Output is correct
4 Correct 113 ms 257020 KB Output is correct
5 Correct 109 ms 256860 KB Output is correct
6 Correct 107 ms 256848 KB Output is correct
7 Correct 106 ms 256884 KB Output is correct
8 Correct 108 ms 256848 KB Output is correct
9 Correct 110 ms 256848 KB Output is correct
10 Correct 734 ms 654588 KB Output is correct
11 Correct 705 ms 544952 KB Output is correct
12 Correct 289 ms 373116 KB Output is correct
13 Correct 998 ms 792276 KB Output is correct
14 Correct 602 ms 565112 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 256640 KB Output is correct
2 Correct 111 ms 256688 KB Output is correct
3 Correct 115 ms 256872 KB Output is correct
4 Correct 113 ms 257020 KB Output is correct
5 Correct 109 ms 256860 KB Output is correct
6 Correct 107 ms 256848 KB Output is correct
7 Correct 106 ms 256884 KB Output is correct
8 Correct 108 ms 256848 KB Output is correct
9 Correct 110 ms 256848 KB Output is correct
10 Correct 107 ms 257260 KB Output is correct
11 Correct 114 ms 257104 KB Output is correct
12 Correct 112 ms 257208 KB Output is correct
13 Correct 109 ms 256880 KB Output is correct
14 Correct 110 ms 256744 KB Output is correct
15 Correct 110 ms 257288 KB Output is correct
16 Correct 108 ms 256904 KB Output is correct
17 Correct 108 ms 256848 KB Output is correct
18 Correct 106 ms 256852 KB Output is correct
19 Correct 112 ms 256704 KB Output is correct
20 Correct 108 ms 256872 KB Output is correct
21 Correct 109 ms 257172 KB Output is correct
22 Correct 107 ms 256852 KB Output is correct
23 Correct 111 ms 257124 KB Output is correct
24 Correct 108 ms 257292 KB Output is correct
25 Correct 108 ms 257104 KB Output is correct
26 Correct 107 ms 257200 KB Output is correct
27 Correct 124 ms 260688 KB Output is correct
28 Correct 131 ms 260944 KB Output is correct
29 Correct 129 ms 260688 KB Output is correct
30 Correct 108 ms 258900 KB Output is correct
31 Correct 119 ms 258388 KB Output is correct
32 Correct 115 ms 257872 KB Output is correct
33 Correct 109 ms 258972 KB Output is correct
34 Correct 108 ms 258388 KB Output is correct
35 Correct 110 ms 258896 KB Output is correct
36 Correct 123 ms 259864 KB Output is correct
37 Correct 128 ms 260952 KB Output is correct
38 Correct 121 ms 260148 KB Output is correct
39 Correct 126 ms 261520 KB Output is correct
40 Correct 108 ms 259296 KB Output is correct
41 Correct 114 ms 260944 KB Output is correct
42 Correct 734 ms 654588 KB Output is correct
43 Correct 705 ms 544952 KB Output is correct
44 Correct 289 ms 373116 KB Output is correct
45 Correct 998 ms 792276 KB Output is correct
46 Correct 602 ms 565112 KB Output is correct
47 Correct 107 ms 256852 KB Output is correct
48 Correct 107 ms 256728 KB Output is correct
49 Correct 114 ms 256716 KB Output is correct
50 Correct 637 ms 551272 KB Output is correct
51 Correct 658 ms 558860 KB Output is correct
52 Correct 546 ms 660508 KB Output is correct
53 Correct 555 ms 660424 KB Output is correct
54 Correct 550 ms 660420 KB Output is correct
55 Correct 986 ms 766668 KB Output is correct
56 Correct 668 ms 754780 KB Output is correct
57 Correct 665 ms 756156 KB Output is correct
58 Correct 870 ms 752416 KB Output is correct
59 Correct 2005 ms 893812 KB Output is correct
60 Correct 2012 ms 851060 KB Output is correct
61 Correct 2114 ms 853080 KB Output is correct
62 Correct 1719 ms 1273288 KB Output is correct
63 Correct 695 ms 784176 KB Output is correct
64 Correct 136 ms 262276 KB Output is correct
65 Correct 140 ms 262420 KB Output is correct
66 Correct 1654 ms 1249228 KB Output is correct
67 Correct 188 ms 287824 KB Output is correct
68 Correct 201 ms 308676 KB Output is correct
69 Correct 1885 ms 894108 KB Output is correct
70 Correct 280 ms 359200 KB Output is correct
71 Correct 610 ms 566812 KB Output is correct
72 Correct 1874 ms 894260 KB Output is correct
73 Correct 1653 ms 1253320 KB Output is correct