oj.uz

Submission #442061

# Submission time Handle Problem Language Result Execution time Memory
442061 2021-07-07T00:56:31 Z Dormi Keys (IOI21_keys) C++17
100 / 100
 1868 ms 173612 KB 
#include "bits/stdc++.h"
#include "keys.h"
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
int sz(const T &a){return int(a.size());}
const int MN=3e5+1;
struct dsu {
    pii t[MN];

    void reset(int n) {
        for (int i = 0; i <= n; i++)t[i] = {i, 1};
    }

    int find(int a) {
        if (t[a].first == a)return a;
        return t[a].first = find(t[a].first);
    }

    bool uni(int a, int b) {
        int ap = find(a), bp = find(b);
        if (ap == bp)return false;
        if (t[ap].second < t[bp].second)swap(ap, bp);
        t[bp].first = ap;
        t[ap].second += t[bp].second;
        return true;
    }
}cn,cc;
int parent[MN],n,m;
vector<int> totake[MN];
map<int,vector<int>> notkeyed[MN];
set<int> keys[MN];
priority_queue<pii> tocheck;
void merge(int a, int b){
    cn.uni(a,b);
    int par=cn.find(a);
    int ch=(a==par?b:a);
    parent[par]=-1;
    totake[par].insert(totake[par].end(),totake[ch].begin(),totake[ch].end());
    for(auto x:keys[ch]){
        keys[par].insert(x);
        if(notkeyed[par].count(x)){
            totake[par].insert(totake[par].end(),notkeyed[par][x].begin(),notkeyed[par][x].end());
            notkeyed[par].erase(x);
        }
    }
    for(auto x:notkeyed[ch]){
        if(keys[par].count(x.first))totake[par].insert(totake[par].end(),x.second.begin(),x.second.end());
        else notkeyed[par][x.first].insert(notkeyed[par][x.first].end(),x.second.begin(),x.second.end());
    }
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
    n=sz(r),m=sz(u);
    for(int i=0;i<m;i++)notkeyed[u[i]][c[i]].push_back(v[i]),notkeyed[v[i]][c[i]].push_back(u[i]);
    vector<int> ans(n);
    cn.reset(n),cc.reset(n);
    for(int i=0;i<n;i++){
        parent[i]=-1;
        keys[i].insert(r[i]);
        if(notkeyed[i].count(r[i])){
            totake[i].insert(totake[i].end(),notkeyed[i][r[i]].begin(),notkeyed[i][r[i]].end());
            notkeyed[i].erase(r[i]);
        }
        tocheck.push({sz(totake[i]),i});
    }
    while(sz(tocheck)){
        auto cur=tocheck.top().second;
        tocheck.pop();
        cur=cn.find(cur);
        if(parent[cur]!=-1)continue;
        if(!sz(totake[cur]))continue;
        int oth=cn.find(totake[cur].back());
        totake[cur].pop_back();
        if(oth==cur){
            tocheck.push({sz(totake[cur]),cur});
            continue;
        }
        if(cc.find(oth)!=cc.find(cur)){
            parent[cur]=oth;
            cc.uni(oth,cur);
        }
        else{
            vector<int> route;
            while(oth!=cur){
                route.push_back(oth);
                oth=cn.find(parent[oth]);
            }
            while(sz(route)){
                merge(cur,route.back());
                cur=cn.find(cur);
                route.pop_back();
            }
            tocheck.push({sz(totake[cur]),cur});
        }
    }
    int misize=INT_MAX;
    for(int i=0;i<n;i++){
        if(cn.find(i)==i){
            if(parent[i]==-1){
                misize=min(misize,cn.t[i].second);
            }
        }
    }
    for(int i=0;i<n;i++)ans[i]=(cn.t[cn.find(i)].second==misize&&parent[cn.find(i)]==-1);
    return ans;
}

//int main(){
//    cin.tie(NULL);
//    ios_base::sync_with_stdio(false);
//    int nn,mm;
//    cin>>nn>>mm;
//    vector<int> kkeys(nn),ledge(mm),redge(nn),cedge(nn);
//    for(int i=0;i<nn;i++){
//        cin>>kkeys[i];
//    }
//    for(int i=0;i<mm;i++){
//        cin>>ledge[i]>>redge[i]>>cedge[i];
//    }
//    auto te=find_reachable(kkeys,ledge,redge,cedge);
//    for(auto x:te)printf("%d ",x);
//    return 0;
//}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35532 KB Output is correct
2 Correct 21 ms 35536 KB Output is correct
3 Correct 21 ms 35508 KB Output is correct
4 Correct 21 ms 35488 KB Output is correct
5 Correct 21 ms 35464 KB Output is correct
6 Correct 22 ms 35452 KB Output is correct
7 Correct 23 ms 35532 KB Output is correct
8 Correct 22 ms 35532 KB Output is correct
9 Correct 22 ms 35560 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35532 KB Output is correct
2 Correct 21 ms 35536 KB Output is correct
3 Correct 21 ms 35508 KB Output is correct
4 Correct 21 ms 35488 KB Output is correct
5 Correct 21 ms 35464 KB Output is correct
6 Correct 22 ms 35452 KB Output is correct
7 Correct 23 ms 35532 KB Output is correct
8 Correct 22 ms 35532 KB Output is correct
9 Correct 22 ms 35560 KB Output is correct
10 Correct 22 ms 35532 KB Output is correct
11 Correct 22 ms 35600 KB Output is correct
12 Correct 21 ms 35532 KB Output is correct
13 Correct 22 ms 35540 KB Output is correct
14 Correct 21 ms 35532 KB Output is correct
15 Correct 24 ms 35476 KB Output is correct
16 Correct 22 ms 35532 KB Output is correct
17 Correct 23 ms 35548 KB Output is correct
18 Correct 22 ms 35448 KB Output is correct
19 Correct 23 ms 35540 KB Output is correct
20 Correct 22 ms 35508 KB Output is correct
21 Correct 22 ms 35660 KB Output is correct
22 Correct 21 ms 35504 KB Output is correct
23 Correct 22 ms 35592 KB Output is correct
24 Correct 22 ms 35532 KB Output is correct
25 Correct 23 ms 35508 KB Output is correct
26 Correct 22 ms 35532 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35532 KB Output is correct
2 Correct 21 ms 35536 KB Output is correct
3 Correct 21 ms 35508 KB Output is correct
4 Correct 21 ms 35488 KB Output is correct
5 Correct 21 ms 35464 KB Output is correct
6 Correct 22 ms 35452 KB Output is correct
7 Correct 23 ms 35532 KB Output is correct
8 Correct 22 ms 35532 KB Output is correct
9 Correct 22 ms 35560 KB Output is correct
10 Correct 22 ms 35532 KB Output is correct
11 Correct 22 ms 35600 KB Output is correct
12 Correct 21 ms 35532 KB Output is correct
13 Correct 22 ms 35540 KB Output is correct
14 Correct 21 ms 35532 KB Output is correct
15 Correct 24 ms 35476 KB Output is correct
16 Correct 22 ms 35532 KB Output is correct
17 Correct 23 ms 35548 KB Output is correct
18 Correct 22 ms 35448 KB Output is correct
19 Correct 23 ms 35540 KB Output is correct
20 Correct 22 ms 35508 KB Output is correct
21 Correct 22 ms 35660 KB Output is correct
22 Correct 21 ms 35504 KB Output is correct
23 Correct 22 ms 35592 KB Output is correct
24 Correct 22 ms 35532 KB Output is correct
25 Correct 23 ms 35508 KB Output is correct
26 Correct 22 ms 35532 KB Output is correct
27 Correct 22 ms 36044 KB Output is correct
28 Correct 23 ms 36120 KB Output is correct
29 Correct 23 ms 36100 KB Output is correct
30 Correct 24 ms 35824 KB Output is correct
31 Correct 23 ms 35728 KB Output is correct
32 Correct 22 ms 35568 KB Output is correct
33 Correct 24 ms 35788 KB Output is correct
34 Correct 25 ms 35788 KB Output is correct
35 Correct 23 ms 35796 KB Output is correct
36 Correct 25 ms 36144 KB Output is correct
37 Correct 26 ms 36124 KB Output is correct
38 Correct 25 ms 36172 KB Output is correct
39 Correct 26 ms 36200 KB Output is correct
40 Correct 23 ms 35788 KB Output is correct
41 Correct 26 ms 36100 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35532 KB Output is correct
2 Correct 21 ms 35536 KB Output is correct
3 Correct 21 ms 35508 KB Output is correct
4 Correct 21 ms 35488 KB Output is correct
5 Correct 21 ms 35464 KB Output is correct
6 Correct 22 ms 35452 KB Output is correct
7 Correct 23 ms 35532 KB Output is correct
8 Correct 22 ms 35532 KB Output is correct
9 Correct 22 ms 35560 KB Output is correct
10 Correct 832 ms 101064 KB Output is correct
11 Correct 695 ms 90296 KB Output is correct
12 Correct 205 ms 53048 KB Output is correct
13 Correct 896 ms 115092 KB Output is correct
14 Correct 347 ms 91772 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35532 KB Output is correct
2 Correct 21 ms 35536 KB Output is correct
3 Correct 21 ms 35508 KB Output is correct
4 Correct 21 ms 35488 KB Output is correct
5 Correct 21 ms 35464 KB Output is correct
6 Correct 22 ms 35452 KB Output is correct
7 Correct 23 ms 35532 KB Output is correct
8 Correct 22 ms 35532 KB Output is correct
9 Correct 22 ms 35560 KB Output is correct
10 Correct 22 ms 35532 KB Output is correct
11 Correct 22 ms 35600 KB Output is correct
12 Correct 21 ms 35532 KB Output is correct
13 Correct 22 ms 35540 KB Output is correct
14 Correct 21 ms 35532 KB Output is correct
15 Correct 24 ms 35476 KB Output is correct
16 Correct 22 ms 35532 KB Output is correct
17 Correct 23 ms 35548 KB Output is correct
18 Correct 22 ms 35448 KB Output is correct
19 Correct 23 ms 35540 KB Output is correct
20 Correct 22 ms 35508 KB Output is correct
21 Correct 22 ms 35660 KB Output is correct
22 Correct 21 ms 35504 KB Output is correct
23 Correct 22 ms 35592 KB Output is correct
24 Correct 22 ms 35532 KB Output is correct
25 Correct 23 ms 35508 KB Output is correct
26 Correct 22 ms 35532 KB Output is correct
27 Correct 22 ms 36044 KB Output is correct
28 Correct 23 ms 36120 KB Output is correct
29 Correct 23 ms 36100 KB Output is correct
30 Correct 24 ms 35824 KB Output is correct
31 Correct 23 ms 35728 KB Output is correct
32 Correct 22 ms 35568 KB Output is correct
33 Correct 24 ms 35788 KB Output is correct
34 Correct 25 ms 35788 KB Output is correct
35 Correct 23 ms 35796 KB Output is correct
36 Correct 25 ms 36144 KB Output is correct
37 Correct 26 ms 36124 KB Output is correct
38 Correct 25 ms 36172 KB Output is correct
39 Correct 26 ms 36200 KB Output is correct
40 Correct 23 ms 35788 KB Output is correct
41 Correct 26 ms 36100 KB Output is correct
42 Correct 832 ms 101064 KB Output is correct
43 Correct 695 ms 90296 KB Output is correct
44 Correct 205 ms 53048 KB Output is correct
45 Correct 896 ms 115092 KB Output is correct
46 Correct 347 ms 91772 KB Output is correct
47 Correct 22 ms 35532 KB Output is correct
48 Correct 21 ms 35416 KB Output is correct
49 Correct 21 ms 35540 KB Output is correct
50 Correct 356 ms 92076 KB Output is correct
51 Correct 425 ms 90608 KB Output is correct
52 Correct 468 ms 96604 KB Output is correct
53 Correct 458 ms 96700 KB Output is correct
54 Correct 514 ms 96624 KB Output is correct
55 Correct 923 ms 112552 KB Output is correct
56 Correct 566 ms 109236 KB Output is correct
57 Correct 482 ms 102436 KB Output is correct
58 Correct 866 ms 121916 KB Output is correct
59 Correct 1799 ms 129752 KB Output is correct
60 Correct 692 ms 108600 KB Output is correct
61 Correct 1286 ms 119840 KB Output is correct
62 Correct 1388 ms 173432 KB Output is correct
63 Correct 493 ms 117616 KB Output is correct
64 Correct 28 ms 36556 KB Output is correct
65 Correct 27 ms 36556 KB Output is correct
66 Correct 1397 ms 173556 KB Output is correct
67 Correct 52 ms 41920 KB Output is correct
68 Correct 73 ms 46020 KB Output is correct
69 Correct 1796 ms 137096 KB Output is correct
70 Correct 125 ms 56164 KB Output is correct
71 Correct 345 ms 97896 KB Output is correct
72 Correct 1868 ms 137088 KB Output is correct
73 Correct 1384 ms 173612 KB Output is correct