Submission #525710

#	Time	Username	Problem	Language	Result	Execution time	Memory
525710		leaked	Simurgh (IOI17_simurgh)	C++14	100 / 100	237 ms	7400 KiB

simurgh

#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 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30