oj.uz

Submission #570926

# Submission time Handle Problem Language Result Execution time Memory
570926 2022-05-31T14:33:10 Z doowey Keys (IOI21_keys) C++17
100 / 100
 1681 ms 62444 KB 
#include "keys.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair


const int N = (int)3e5 + 1;

vector<pii> T[N];
int col[N];
bool collect[N];
vector<int> st[N];
bool vis[N];

vector<int> nds;
vector<int> keys;

int par[N];

int fin(int u){
    if(par[u] == u) return u;
    return par[u]=fin(par[u]);
}

void unite(int ui, int vi){
    ui=fin(ui);
    vi=fin(vi);
    if(ui==vi) return;
    par[ui]=vi;
}

vector<pii> cc;

void clean(int xi, int yi){
    for(auto x : keys){
        collect[x] = false;
        st[x].clear();
    }
    cc.push_back(mp(xi, yi));
    keys.clear();
}


void travel(int node, bool mode){
    queue<int> que;
    que.push(node);
    vis[node]=true;
    int cur;

    while(!que.empty()){
        cur = que.front();
        que.pop();
        collect[col[cur]] = true;
        keys.push_back(col[cur]);
        nds.push_back(cur);
        for(auto x : T[cur]){
            if(vis[x.fi]) continue;
            if(mode)nds.push_back(x.fi);
            keys.push_back(x.se);
            if(collect[x.se]){
                if(fin(x.fi) != fin(node) && mode){
                    clean(node, x.fi); // f(x.fi) <= f(node)
                    return;
                }
                vis[x.fi]=true;
                que.push(x.fi);
            }
            else{
                st[x.se].push_back(x.fi);
            }
        }
        for(auto x : st[col[cur]]){
            if(vis[x]) continue;
            if(fin(x) != fin(node) && mode){
                clean(node, x);
                return;
            }
            vis[x] = true;
            que.push(x);
        }
        st[col[cur]].clear();
    }
    for(auto x : keys){
        collect[x]=false;
        st[x].clear();
    }
    keys.clear();
}


vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    int m = u.size();
    int n = r.size();
    for(int i = 0 ; i < n; i ++ ){
        col[i] = r[i];
        par[i] = i;
    }
    for(int i = 0 ; i < m ; i ++ ){
        T[u[i]].push_back(mp(v[i], c[i]));
        T[v[i]].push_back(mp(u[i], c[i]));
    }
    for(int iter = 0; iter < 20; iter ++ ){
        for(int i = 0 ; i < n; i ++ ){
            if(vis[i]) continue;
            if(par[i] == i){
                travel(i, true);
                for(auto x : nds){
                    vis[x]=false;
                }
                nds.clear();
            }
        }
        for(int i = 0 ; i < n; i ++ ){
            vis[i]=false;
            collect[i]=false;
            st[i].clear();
        }
        for(auto x : cc){
            unite(x.fi, x.se);
        }
        cc.clear();
    }
    vector<int> sol(n);
    int sz = n + 1;
    vector<int> trav;
    for(int i = 0 ; i < n; i ++ ){
        if(par[i] == i){
            travel(i, false);
            if(nds.size() < sz){
                sz = nds.size();
                trav = nds;
            }
            else if(nds.size() == sz){
                for(auto x : nds){
                    trav.push_back(x);
                }
            }
            nds.clear();
        }
    }
    for(auto x : trav) sol[x] = 1;
    return sol;
}

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:136:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  136 |             if(nds.size() < sz){
      |                ~~~~~~~~~~~^~~~
keys.cpp:140:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |             else if(nds.size() == sz){
      |                     ~~~~~~~~~~~^~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14292 KB Output is correct
6 Correct 9 ms 14292 KB Output is correct
7 Correct 9 ms 14292 KB Output is correct
8 Correct 10 ms 14420 KB Output is correct
9 Correct 10 ms 14424 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14292 KB Output is correct
6 Correct 9 ms 14292 KB Output is correct
7 Correct 9 ms 14292 KB Output is correct
8 Correct 10 ms 14420 KB Output is correct
9 Correct 10 ms 14424 KB Output is correct
10 Correct 10 ms 14428 KB Output is correct
11 Correct 10 ms 14420 KB Output is correct
12 Correct 9 ms 14364 KB Output is correct
13 Correct 10 ms 14416 KB Output is correct
14 Correct 8 ms 14340 KB Output is correct
15 Correct 8 ms 14404 KB Output is correct
16 Correct 8 ms 14368 KB Output is correct
17 Correct 9 ms 14320 KB Output is correct
18 Correct 9 ms 14336 KB Output is correct
19 Correct 9 ms 14292 KB Output is correct
20 Correct 10 ms 14420 KB Output is correct
21 Correct 11 ms 14420 KB Output is correct
22 Correct 9 ms 14424 KB Output is correct
23 Correct 9 ms 14420 KB Output is correct
24 Correct 9 ms 14328 KB Output is correct
25 Correct 9 ms 14436 KB Output is correct
26 Correct 10 ms 14324 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14292 KB Output is correct
6 Correct 9 ms 14292 KB Output is correct
7 Correct 9 ms 14292 KB Output is correct
8 Correct 10 ms 14420 KB Output is correct
9 Correct 10 ms 14424 KB Output is correct
10 Correct 10 ms 14428 KB Output is correct
11 Correct 10 ms 14420 KB Output is correct
12 Correct 9 ms 14364 KB Output is correct
13 Correct 10 ms 14416 KB Output is correct
14 Correct 8 ms 14340 KB Output is correct
15 Correct 8 ms 14404 KB Output is correct
16 Correct 8 ms 14368 KB Output is correct
17 Correct 9 ms 14320 KB Output is correct
18 Correct 9 ms 14336 KB Output is correct
19 Correct 9 ms 14292 KB Output is correct
20 Correct 10 ms 14420 KB Output is correct
21 Correct 11 ms 14420 KB Output is correct
22 Correct 9 ms 14424 KB Output is correct
23 Correct 9 ms 14420 KB Output is correct
24 Correct 9 ms 14328 KB Output is correct
25 Correct 9 ms 14436 KB Output is correct
26 Correct 10 ms 14324 KB Output is correct
27 Correct 11 ms 14548 KB Output is correct
28 Correct 12 ms 14548 KB Output is correct
29 Correct 17 ms 14640 KB Output is correct
30 Correct 12 ms 14440 KB Output is correct
31 Correct 12 ms 14500 KB Output is correct
32 Correct 10 ms 14376 KB Output is correct
33 Correct 10 ms 14456 KB Output is correct
34 Correct 10 ms 14424 KB Output is correct
35 Correct 8 ms 14420 KB Output is correct
36 Correct 11 ms 14584 KB Output is correct
37 Correct 14 ms 14516 KB Output is correct
38 Correct 13 ms 14568 KB Output is correct
39 Correct 13 ms 14548 KB Output is correct
40 Correct 12 ms 14420 KB Output is correct
41 Correct 10 ms 14548 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14292 KB Output is correct
6 Correct 9 ms 14292 KB Output is correct
7 Correct 9 ms 14292 KB Output is correct
8 Correct 10 ms 14420 KB Output is correct
9 Correct 10 ms 14424 KB Output is correct
10 Correct 646 ms 36508 KB Output is correct
11 Correct 663 ms 53204 KB Output is correct
12 Correct 173 ms 20664 KB Output is correct
13 Correct 1191 ms 45808 KB Output is correct
14 Correct 443 ms 53428 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14292 KB Output is correct
6 Correct 9 ms 14292 KB Output is correct
7 Correct 9 ms 14292 KB Output is correct
8 Correct 10 ms 14420 KB Output is correct
9 Correct 10 ms 14424 KB Output is correct
10 Correct 10 ms 14428 KB Output is correct
11 Correct 10 ms 14420 KB Output is correct
12 Correct 9 ms 14364 KB Output is correct
13 Correct 10 ms 14416 KB Output is correct
14 Correct 8 ms 14340 KB Output is correct
15 Correct 8 ms 14404 KB Output is correct
16 Correct 8 ms 14368 KB Output is correct
17 Correct 9 ms 14320 KB Output is correct
18 Correct 9 ms 14336 KB Output is correct
19 Correct 9 ms 14292 KB Output is correct
20 Correct 10 ms 14420 KB Output is correct
21 Correct 11 ms 14420 KB Output is correct
22 Correct 9 ms 14424 KB Output is correct
23 Correct 9 ms 14420 KB Output is correct
24 Correct 9 ms 14328 KB Output is correct
25 Correct 9 ms 14436 KB Output is correct
26 Correct 10 ms 14324 KB Output is correct
27 Correct 11 ms 14548 KB Output is correct
28 Correct 12 ms 14548 KB Output is correct
29 Correct 17 ms 14640 KB Output is correct
30 Correct 12 ms 14440 KB Output is correct
31 Correct 12 ms 14500 KB Output is correct
32 Correct 10 ms 14376 KB Output is correct
33 Correct 10 ms 14456 KB Output is correct
34 Correct 10 ms 14424 KB Output is correct
35 Correct 8 ms 14420 KB Output is correct
36 Correct 11 ms 14584 KB Output is correct
37 Correct 14 ms 14516 KB Output is correct
38 Correct 13 ms 14568 KB Output is correct
39 Correct 13 ms 14548 KB Output is correct
40 Correct 12 ms 14420 KB Output is correct
41 Correct 10 ms 14548 KB Output is correct
42 Correct 646 ms 36508 KB Output is correct
43 Correct 663 ms 53204 KB Output is correct
44 Correct 173 ms 20664 KB Output is correct
45 Correct 1191 ms 45808 KB Output is correct
46 Correct 443 ms 53428 KB Output is correct
47 Correct 11 ms 14376 KB Output is correct
48 Correct 10 ms 14420 KB Output is correct
49 Correct 9 ms 14420 KB Output is correct
50 Correct 509 ms 54640 KB Output is correct
51 Correct 528 ms 57880 KB Output is correct
52 Correct 885 ms 43292 KB Output is correct
53 Correct 872 ms 43244 KB Output is correct
54 Correct 1043 ms 43204 KB Output is correct
55 Correct 1511 ms 42104 KB Output is correct
56 Correct 1154 ms 51520 KB Output is correct
57 Correct 1633 ms 50772 KB Output is correct
58 Correct 791 ms 62444 KB Output is correct
59 Correct 1404 ms 53496 KB Output is correct
60 Correct 448 ms 51568 KB Output is correct
61 Correct 1681 ms 51848 KB Output is correct
62 Correct 1339 ms 47060 KB Output is correct
63 Correct 418 ms 46008 KB Output is correct
64 Correct 15 ms 15060 KB Output is correct
65 Correct 16 ms 15116 KB Output is correct
66 Correct 1346 ms 47376 KB Output is correct
67 Correct 49 ms 18044 KB Output is correct
68 Correct 75 ms 20552 KB Output is correct
69 Correct 1491 ms 53492 KB Output is correct
70 Correct 140 ms 26736 KB Output is correct
71 Correct 412 ms 53988 KB Output is correct
72 Correct 1627 ms 53564 KB Output is correct
73 Correct 1276 ms 46364 KB Output is correct