Submission #1272229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272229		StefanSebez	Swapping Cities (APIO20_swap)	C++20	0 / 100	2096 ms	14888 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50,M=2e5+50,S=600,inf=1e9+50;
mt19937 rng(time(0));
vector<pair<int,int>>E[N];
int n,m;
vector<array<int,3>>edges;
/*struct DSU{
    vector<array<int,5>>undo;
    int par[N],sajz[N],deg[N],ciklus[N];
    DSU(){for(int i=0;i<N;i++)par[i]=i,sajz[i]=1,deg[i]=0;}
    int FS(int u){if(par[u]==u)return u;return FS(par[u]);}
    void US(int u,int v){
        deg[u]++,deg[v]++;
        int U=FS(u),V=FS(v);
        if(deg[u]>2) ciklus[U]++;
        if(deg[v]>2) ciklus[V]++;
        int swp=0;
        if(U==V) ciklus[U]++;
        else{
            if(sajz[U]<sajz[V]) swap(U,V),swp=1;
            par[V]=U;
            sajz[U]+=sajz[V];
            ciklus[U]+=ciklus[V];
            if(swp==1) swap(U,V);
        }
        undo.pb({u,v,U,V,swp});
    }
    void Undo(){
        auto [u,v,U,V,swp]=undo.back();undo.pop_back();
        if(U==V) ciklus[U]--;
        else{
            if(swp) swap(U,V);
            ciklus[U]-=ciklus[V];
            sajz[U]-=sajz[V];
            par[V]=V;
            if(swp) swap(U,V);
        }
        if(deg[u]>2) ciklus[U]--;
        if(deg[v]>2) ciklus[V]--;
        deg[u]--,deg[v]--;
    }
}dsu[M/S+1];*/
struct DSU{
    int par[N+M],deg[N+M],ciklus[N+M],sajz[N+M],tajm[N+M],tm,nc=N;
    DSU(){for(int i=0;i<N+M;i++)par[i]=i,sajz[i]=1;}
    void Copy(int u){
        ++nc;
        tajm[nc]=tm;
        par[u]=nc;
        sajz[nc]=sajz[u]+1;
        ciklus[nc]=ciklus[u];
    }
    int FS(int u,int t){if(tajm[par[u]]>t||par[u]==u)return u;return FS(par[u],t);}
    int Ciklus(int u,int t){if(tajm[par[u]]>t||par[u]==u)return ciklus[u];return max(ciklus[u],Ciklus(par[u],t));}
    void US(int u,int v){
        deg[u]++,deg[v]++;
        int U=FS(u,tm),V=FS(v,tm);
        //printf("%i %i %i %i\n",u,v,U,V);
        tm++;
        if(U==V){
            //printf("DA\n");
            if(ciklus[U]==0){
                //printf("DA\n");
                Copy(U);
                ciklus[nc]++;
            }
            return;
        }
        if(ciklus[U]==0&&deg[u]>=3){
            Copy(U);
            ciklus[nc]++;
            U=nc;
        }
        if(ciklus[V]==0&&deg[v]>=3){
            Copy(V);
            ciklus[nc]++;
            V=nc;
        }
        if(rng()%2) swap(U,V);
        Copy(V);V=nc;
        par[V]=U;
        //sajz[U]+=sajz[V];
        //ciklus[U]+=ciklus[V];
    }
}dsu;
void init(int n1,int m1,vector<int>U,vector<int>V,vector<int>W) {
    n=n1,m=m1;
    for(int i=0;i<m;i++){
        E[U[i]].pb({V[i],W[i]});
        E[V[i]].pb({U[i],W[i]});
        edges.pb({W[i],U[i],V[i]});
    }
    sort(edges.begin(),edges.end());
    for(int i=0;i<m;i++){
        //printf("%i\n",i);
        dsu.US(edges[i][1],edges[i][2]);
    }
    //printf("da\n");
    /*for(int B=0;B*S-S<=m;B++){
        for(int i=0;i<min(m,B*S);i++){
            dsu[B].US(edges[i][1],edges[i][2]);
        }
    }*/
    /*for(int i=0;i<n;i++){
        sort(E[i].begin(),E[i].end(),[&](pair<int,int>a,pair<int,int>b){return a.se<b.se;});
        if(E[i].size()<3) Val[i]=inf+100;
        else Val[i]=E[i][2].se;
    }*/
}
/*bool was[N],ciklus;
int par[N],deg[N];
void DFS(int u,int mid,int p=-1){
    was[u]=true;
    for(auto [v,w]:E[u]){
        if(w>mid) continue;
        if(was[v]&&v!=p) ciklus=true;
        if(!was[v]){
            par[v]=u;
            deg[u]++,deg[v]++;
            DFS(v,mid,u);
        }
    }
}*/
int getMinimumFuelCapacity(int X,int Y){
    int l=1,r=m,res=-1;
    while(l<=r){
        int mid=l+r>>1;
        int rootX=dsu.FS(X,mid),rootY=dsu.FS(Y,mid);
        if(rootX==rootY&&dsu.Ciklus(X,mid)>0){res=edges[mid-1][0],r=mid-1;}
        else l=mid+1;
    }
    return res;
    /*int ind=0;
    for(int B=0;B*S-S<=m;B++){
        int rootX=dsu[B].FS(X),rootY=dsu[B].FS(Y);
        if(rootX==rootY){
            if(dsu[B].ciklus[rootX]>0) break;
        }
        ind=B;
    }
    //printf("%i\n",ind);
    int res=-1,cnt=0;
    for(int B=ind,i=B*S;i<m;i++){
        //printf("%i %i %i\n",edges[i][0],edges[i][1],edges[i][2]);
        dsu[B].US(edges[i][1],edges[i][2]);
        cnt++;
        int rootX=dsu[B].FS(X),rootY=dsu[B].FS(Y);
        if(rootX==rootY){
            //printf("da\n");
            if(dsu[B].ciklus[rootX]>0) res=edges[i][0];
        }
        if(res>-1) break;
    }
    while(cnt--) dsu[ind].Undo();
    return res;*/
    /*int l=0,r=inf,res=-1;
    while(l<=r){
        int mid=l+r>>1;
        for(int i=0;i<=n;i++) was[i]=false,par[i]=deg[i]=0;ciklus=false;
        DFS(X,mid);
        if(!was[Y]){l=mid+1;continue;}
        if(ciklus){res=mid;r=mid-1;continue;}
        int mn=inf+1000;
        bool moze=false;
        for(int i=0;i<n;i++) if(deg[i]>2) moze=true;
        if(moze){res=mid;r=mid-1;}
        else l=mid+1;
    }
    return res;*/
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27