oj.uz

Submission #525710

# Submission time Handle Problem Language Result Execution time Memory
525710 2022-02-12T15:57:36 Z leaked Simurgh (IOI17_simurgh) C++14
100 / 100
 237 ms 7400 KB 
#include "simurgh.h"
#include <bits/stdc++.h>


#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define m_p make_pair
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))

using namespace std;
const int N=5e2+10;
typedef pair<int,int> pii;
struct dsu{
    int p[N],sz[N];
    void make(int v){
        p[v]=v;
        sz[v]=1;
    }
    void init(){
        for(int i=0;i<N;i++)
            make(i);
    }
    int get(int v){
        return p[v]=(p[v]==v?v:get(p[v]));
    }
    bool mg(int a,int b){
        a=get(a),b=get(b);
        if(a==b) return 0;
        if(sz[a]>sz[b]) swap(a,b);
        p[a]=b;sz[b]+=sz[a];
        return 1;
    }
}ds;
vec<array<int,4>> goods;
vec<int> ones;
bool used[N*N];
int pr[N];
int ids[N];
bool ema[N*N];
int clr[N*N];
int u[N];
vec<array<int,3>> backt;
vec<array<int,3>> inc;
vec<pii> g[N];
int get(vec<array<int,3>> vc){
    ds.init();
    vec<int>asks;
    for(auto &z : vc){
        ds.mg(z[0],z[1]);
        asks.pb(z[2]);
    }
    int hv=0;
    for(auto &z : goods){
        if(ds.mg(z[0],z[1])){
            hv-=z[3];
            asks.pb(z[2]);
//            cout<<"DELETE "<<z[0]<<' '<<z[1]<<' '<<z[2]<<' '<<z[3]<<endl;
        }
    }
    hv+=count_common_roads(asks);
//    if(hv<0){
//        cout<<"EBLAN "<<endl;
//        for(auto &zt : asks){
//            cout<<zt<<endl;
//        }
//        cout<<endl;
//    }
    return hv;
}
void rec(vec<array<int,3>> vc, int have){
    if(!have || sz(vc)==0) return;
    if(sz(vc)==1){
        goods.pb({vc[0][0],vc[0][1],vc[0][2],1});
        return;
    }
    ds.init();
    vec<array<int,3>> lft,rgt;
    for(int i=0;i<sz(vc)/2;i++)
        lft.pb(vc[i]);
    for(int i=sz(lft);i<sz(vc);i++)
        rgt.pb(vc[i]);
//    for(auto &z : vc)
//        cout<<z[0]<<' '<<z[1]<<endl;
//    cout<<"HAVE "<<have<<endl;
    int hv=get(lft);
    rec(lft,hv);
    rec(rgt,have-hv);
}

void dfs(int v,int p){
    u[v]=1;
    for(auto &z : g[v]){
        if(z.f==p || u[z.f]==2) continue;
        if(u[z.f]==1){
            backt.pb({v,z.f,z.s});
        }
        else{
            pr[z.f]=v;
            ids[z.f]=z.s;
            inc.pb({v,z.f,z.s});
            dfs(z.f,v);
        }
    }
    u[v]=2;
}
vec<int> find_roads(int n, vec<int> v,vec<int> u){
    int m=sz(v);
    for(int i=0;i<m;i++){
        g[v[i]].pb({u[i],i});
        g[u[i]].pb({v[i],i});
    }
    dfs(0,0);
    int ostov=get(inc);
    for(auto &z : backt){
        int v=z[0];
        vec<array<int,3>>idk;
        int iam1=-1;
        while(v!=z[1]){
            if(!used[ids[v]]){
                vec<array<int,3>> toask;
                for(auto &zt : inc){
                    if(zt[2]!=ids[v]) toask.pb(zt);
                }
                toask.pb(z);
                int me=get(toask);
                if(me==ostov){
                    idk.pb({v,pr[v],ids[v]});
                }
                else{
                    if(me>ostov){
                        goods.pb({v,pr[v],ids[v],0});
                        iam1=1;
                        clr[ids[v]]=0;
                        clr[z[2]]=1;
                        goods.pb({z[0],z[1],z[2],1});
                    }
                    else{
                        goods.pb({v,pr[v],ids[v],1});
                        iam1=0;
                        clr[ids[v]]=1;
                        clr[z[2]]=0;
                        goods.pb({z[0],z[1],z[2],0});
                    }
                    used[z[2]]=1;
                    used[ids[v]]=1;
                }
            }
            v=pr[v];
        }
        if(sz(idk)){
            if(iam1==-1){
                v=z[0];
                while(v!=z[1]){
                    int j=ids[v];
                    if(used[j]){
                        int cv=clr[j];
                        vec<array<int,3>> toask;
                        for(auto &zt : inc){
                            if(zt[2]!=ids[v]) toask.pb(zt);
                        }
                        toask.pb(z);
                        int me=get(toask);
                        if(me==ostov){
                            iam1=cv;
                            clr[z[2]]=cv;
                        }
                        else{
                            if(me<ostov){
                                assert(cv);
                                iam1=0;
                                clr[z[2]]=0;
                            }
                            else{
                                assert(!cv);
                                iam1=1;
                                clr[z[2]]=1;
                            }
                        }
                        break;
                    }
                    v=pr[v];
                }
                if(iam1==-1){
                    iam1=0;
                }
            }
            goods.pb({z[0],z[1],z[2],clr[z[2]]});
            used[z[2]]=1;
            for(auto &z : idk){
                goods.pb({z[0],z[1],z[2],iam1});
                clr[z[2]]=iam1;
//                cout<<z[2]<<endl;
                used[z[2]]=1;
            }
        }
//        cout<<"ALWAYS "<<z[2]<<endl<<endl;
//        for(auto &q : goods){
//            cout<<q[2]<<endl;
//        }
//        cout<<endl;
    }
//    for(auto &z : goods){
//        cout<<"KNOW "<<z[0]<<' '<<z[1]<<' '<<z[2]<<' '<<z[3]<<endl;
//    }
//    exit(0);
    for(auto &z : inc){
        if(!used[z[2]]){
            goods.pb({z[0],z[1],z[2],1});
            used[z[2]]=1;
        }
//        cout<<"INC "<<z[0]<<' '<<z[1]<<endl;
    }
    sort(all(goods));goods.erase(unique(all(goods)),goods.end());
//    for(auto &z : goods){
//        cout<<"KNOW "<<z[0]<<' '<<z[1]<<' '<<z[2]<<' '<<z[3]<<endl;
//    }
//    return ones;
    for(int i=0;i<n;i++){
        vec<array<int,3>>kekw;
        for(auto &z : g[i]){
            if(!used[z.s]){
                kekw.pb({i,z.f,z.s});
                used[z.s]=1;
            }
        }
        if(sz(kekw)){
            rec(kekw,get(kekw));
        }
    }
    for(auto &z : goods){
        if(z[3]==1)
            ones.pb(z[2]);
    }
	return ones;
}
/*
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5

6 7
0 1
1 2
2 3
2 4
4 5
0 2
1 5
0 2 4 5 6

*/

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 296 KB correct
3 Correct 1 ms 332 KB correct
4 Correct 0 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 0 ms 204 KB correct
7 Correct 0 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 0 ms 204 KB correct
12 Correct 0 ms 332 KB correct
13 Correct 0 ms 204 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 296 KB correct
3 Correct 1 ms 332 KB correct
4 Correct 0 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 0 ms 204 KB correct
7 Correct 0 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 0 ms 204 KB correct
12 Correct 0 ms 332 KB correct
13 Correct 0 ms 204 KB correct
14 Correct 3 ms 332 KB correct
15 Correct 2 ms 328 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 2 ms 324 KB correct
18 Correct 2 ms 332 KB correct
19 Correct 2 ms 320 KB correct
20 Correct 2 ms 332 KB correct
21 Correct 2 ms 324 KB correct
22 Correct 1 ms 324 KB correct
23 Correct 1 ms 332 KB correct
24 Correct 1 ms 332 KB correct
25 Correct 1 ms 316 KB correct
26 Correct 1 ms 320 KB correct
27 Correct 1 ms 332 KB correct
28 Correct 1 ms 332 KB correct
29 Correct 1 ms 332 KB correct
30 Correct 1 ms 332 KB correct
31 Correct 1 ms 332 KB correct
32 Correct 1 ms 316 KB correct
33 Correct 1 ms 320 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 296 KB correct
3 Correct 1 ms 332 KB correct
4 Correct 0 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 0 ms 204 KB correct
7 Correct 0 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 0 ms 204 KB correct
12 Correct 0 ms 332 KB correct
13 Correct 0 ms 204 KB correct
14 Correct 3 ms 332 KB correct
15 Correct 2 ms 328 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 2 ms 324 KB correct
18 Correct 2 ms 332 KB correct
19 Correct 2 ms 320 KB correct
20 Correct 2 ms 332 KB correct
21 Correct 2 ms 324 KB correct
22 Correct 1 ms 324 KB correct
23 Correct 1 ms 332 KB correct
24 Correct 1 ms 332 KB correct
25 Correct 1 ms 316 KB correct
26 Correct 1 ms 320 KB correct
27 Correct 1 ms 332 KB correct
28 Correct 1 ms 332 KB correct
29 Correct 1 ms 332 KB correct
30 Correct 1 ms 332 KB correct
31 Correct 1 ms 332 KB correct
32 Correct 1 ms 316 KB correct
33 Correct 1 ms 320 KB correct
34 Correct 44 ms 2060 KB correct
35 Correct 41 ms 2060 KB correct
36 Correct 34 ms 1804 KB correct
37 Correct 13 ms 452 KB correct
38 Correct 42 ms 2092 KB correct
39 Correct 35 ms 1968 KB correct
40 Correct 31 ms 1836 KB correct
41 Correct 41 ms 2064 KB correct
42 Correct 48 ms 2056 KB correct
43 Correct 14 ms 1504 KB correct
44 Correct 12 ms 1168 KB correct
45 Correct 13 ms 1312 KB correct
46 Correct 15 ms 1100 KB correct
47 Correct 9 ms 716 KB correct
48 Correct 4 ms 332 KB correct
49 Correct 6 ms 472 KB correct
50 Correct 8 ms 744 KB correct
51 Correct 15 ms 1288 KB correct
52 Correct 12 ms 1216 KB correct
53 Correct 11 ms 1092 KB correct
54 Correct 14 ms 1420 KB correct
55 Correct 15 ms 1296 KB correct
56 Correct 15 ms 1240 KB correct
57 Correct 15 ms 1376 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 136 ms 5064 KB correct
4 Correct 211 ms 6308 KB correct
5 Correct 220 ms 6404 KB correct
6 Correct 201 ms 6372 KB correct
7 Correct 167 ms 7380 KB correct
8 Correct 165 ms 7228 KB correct
9 Correct 227 ms 7284 KB correct
10 Correct 222 ms 7228 KB correct
11 Correct 218 ms 7252 KB correct
12 Correct 212 ms 7344 KB correct
13 Correct 1 ms 204 KB correct
14 Correct 195 ms 7400 KB correct
15 Correct 217 ms 7228 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 296 KB correct
3 Correct 1 ms 332 KB correct
4 Correct 0 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 0 ms 204 KB correct
7 Correct 0 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 0 ms 204 KB correct
12 Correct 0 ms 332 KB correct
13 Correct 0 ms 204 KB correct
14 Correct 3 ms 332 KB correct
15 Correct 2 ms 328 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 2 ms 324 KB correct
18 Correct 2 ms 332 KB correct
19 Correct 2 ms 320 KB correct
20 Correct 2 ms 332 KB correct
21 Correct 2 ms 324 KB correct
22 Correct 1 ms 324 KB correct
23 Correct 1 ms 332 KB correct
24 Correct 1 ms 332 KB correct
25 Correct 1 ms 316 KB correct
26 Correct 1 ms 320 KB correct
27 Correct 1 ms 332 KB correct
28 Correct 1 ms 332 KB correct
29 Correct 1 ms 332 KB correct
30 Correct 1 ms 332 KB correct
31 Correct 1 ms 332 KB correct
32 Correct 1 ms 316 KB correct
33 Correct 1 ms 320 KB correct
34 Correct 44 ms 2060 KB correct
35 Correct 41 ms 2060 KB correct
36 Correct 34 ms 1804 KB correct
37 Correct 13 ms 452 KB correct
38 Correct 42 ms 2092 KB correct
39 Correct 35 ms 1968 KB correct
40 Correct 31 ms 1836 KB correct
41 Correct 41 ms 2064 KB correct
42 Correct 48 ms 2056 KB correct
43 Correct 14 ms 1504 KB correct
44 Correct 12 ms 1168 KB correct
45 Correct 13 ms 1312 KB correct
46 Correct 15 ms 1100 KB correct
47 Correct 9 ms 716 KB correct
48 Correct 4 ms 332 KB correct
49 Correct 6 ms 472 KB correct
50 Correct 8 ms 744 KB correct
51 Correct 15 ms 1288 KB correct
52 Correct 12 ms 1216 KB correct
53 Correct 11 ms 1092 KB correct
54 Correct 14 ms 1420 KB correct
55 Correct 15 ms 1296 KB correct
56 Correct 15 ms 1240 KB correct
57 Correct 15 ms 1376 KB correct
58 Correct 0 ms 204 KB correct
59 Correct 1 ms 204 KB correct
60 Correct 136 ms 5064 KB correct
61 Correct 211 ms 6308 KB correct
62 Correct 220 ms 6404 KB correct
63 Correct 201 ms 6372 KB correct
64 Correct 167 ms 7380 KB correct
65 Correct 165 ms 7228 KB correct
66 Correct 227 ms 7284 KB correct
67 Correct 222 ms 7228 KB correct
68 Correct 218 ms 7252 KB correct
69 Correct 212 ms 7344 KB correct
70 Correct 1 ms 204 KB correct
71 Correct 195 ms 7400 KB correct
72 Correct 217 ms 7228 KB correct
73 Correct 0 ms 332 KB correct
74 Correct 228 ms 7336 KB correct
75 Correct 206 ms 7172 KB correct
76 Correct 103 ms 3152 KB correct
77 Correct 214 ms 7276 KB correct
78 Correct 219 ms 7340 KB correct
79 Correct 237 ms 7312 KB correct
80 Correct 209 ms 7184 KB correct
81 Correct 155 ms 6608 KB correct
82 Correct 231 ms 7256 KB correct
83 Correct 151 ms 4132 KB correct
84 Correct 75 ms 5524 KB correct
85 Correct 73 ms 4828 KB correct
86 Correct 50 ms 3316 KB correct
87 Correct 40 ms 2636 KB correct
88 Correct 37 ms 1988 KB correct
89 Correct 38 ms 1952 KB correct
90 Correct 41 ms 1840 KB correct
91 Correct 23 ms 564 KB correct
92 Correct 11 ms 432 KB correct
93 Correct 62 ms 4668 KB correct
94 Correct 50 ms 3304 KB correct
95 Correct 47 ms 3396 KB correct
96 Correct 35 ms 1944 KB correct
97 Correct 38 ms 2032 KB correct
98 Correct 43 ms 2644 KB correct
99 Correct 36 ms 1996 KB correct
100 Correct 25 ms 712 KB correct
101 Correct 16 ms 452 KB correct
102 Correct 78 ms 3984 KB correct
103 Correct 83 ms 3952 KB correct
104 Correct 77 ms 3828 KB correct
105 Correct 78 ms 3924 KB correct