Submission #1272219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272219		StefanSebez	Swapping Cities (APIO20_swap)	C++20	17 / 100	2108 ms	557652 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=1000,inf=1e9+50;
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];int neput[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) neput[U]++;
        if(deg[v]>2) neput[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];
            neput[U]+=neput[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];
            neput[U]-=neput[V];
            sajz[U]-=sajz[V];
            par[V]=V;
            if(swp) swap(U,V);
        }
        if(deg[u]>2) neput[U]--;
        if(deg[v]>2) neput[V]--;
        deg[u]--,deg[v]--;
    }
}dsu[M/S+1];
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 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 ind=0;
    for(int B=0;B*S-S<=m;B++){
        if(dsu[B].FS(X)==dsu[B].FS(Y)){
            int i=dsu[B].FS(X);
            if(dsu[B].ciklus[i]>0) break;
            if(dsu[B].neput[i]>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++;
        if(dsu[B].FS(X)==dsu[B].FS(Y)){
            //printf("da\n");
            int root=dsu[B].FS(X);
            if(dsu[B].ciklus[root]>0){res=edges[i][0];}
            if(dsu[B].neput[root]>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: 17 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27