제출 #1272300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272300		StefanSebez	자매 도시 (APIO20_swap)	C++20	7 / 100	2092 ms	16788 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;
void chmx(int &x,int y){x=max(x,y);}
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,tajm[i]=0;tm=0;}
    void Copy(int u){
        ++nc;
        tajm[u]=tm;
        par[u]=nc;
        sajz[nc]=sajz[u]+1;
        ciklus[nc]=ciklus[u];
    }
    int FS(int u,int t){if(par[u]==u||tajm[u]>t)return u;return FS(par[u],t);}
    int Ciklus(int u,int t){if(par[u]==u||tajm[u]>t)return ciklus[u];return max(ciklus[u],Ciklus(par[u],t));}
    int US(int u,int v){
        deg[u]++,deg[v]++;
        int U=FS(u,tm),V=FS(v,tm);
        tm++;
        //printf("%i %i %i %i\n",u,v,U,V);
        if(U==V){
            //printf("DA\n");
            if(ciklus[U]==0){
                //printf("DA\n");
                Copy(U);
                ciklus[nc]++;
            }
            return tm;
        }
        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(sajz[U]<sajz[V]) swap(U,V);
        //Copy(V);V=nc;
        par[V]=U;
        ciklus[U]+=ciklus[V];
        //chmx(maks[U],maks[V]);
        tajm[V]=tm;
        return tm;
        //sajz[U]+=sajz[V];
        //ciklus[U]+=ciklus[V];
    }
}dsu;
/*struct DSU{
    int par[N],maks[N],deg[N],ciklus[N];
    DSU(){for(int i=0;i<N;i++) par[i]=i;}
    int FS(int u){if(par[u]==u)return u;return par[u]=FS(par[u]);}
    void US(int u,int v,int w){
        deg[u]++,deg[v]++;
        int x=deg[u],y=deg[v];
        u=FS(u),v=FS(v);
        if(x>=3) ciklus[u]++;
        if(y>=3) ciklus[v]++;
        if(u==v){chmx(maks[u],w);ciklus[u]++;return;}
        par[u]=v;
        chmx(maks[v],maks[u]);
        ciklus[v]+=ciklus[u];
    }
}dsu;
int ANS[N];*/
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());
    /*vector<int>vtx;
    bool was[n+10]={0};was[0]=true;
    for(int i=0;i<n;i++) ANS[i]=-1;
    for(auto [w,u,v]:edges){
        dsu.US(u,v,w);
        if(!was[u]&&dsu.FS(u)==dsu.FS(0)) vtx.pb(u),was[u]=true;
        if(!was[v]&&dsu.FS(v)==dsu.FS(0)) vtx.pb(v),was[v]=true;
        if(dsu.ciklus[dsu.FS(0)]>0){
            for(auto i:vtx) ANS[i]=w;
            vtx.clear();
        }
    }*/
    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){
    //return ANS[Y];
    /*if(dsu.FS(X)!=dsu.FS(Y)) return -1;
    if(dsu.ciklus[dsu.FS(X)]==0) return -1;
    return dsu.maks[dsu.FS(X)];*/
    /*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[rootX]>0){res=edges[mid-1][0],r=mid-1;}
        else l=mid+1;
    }
    return res;*/
    int res=-1;
    while(X!=Y){
        //printf("%i %i %i %i\n",X,Y,dsu.tajm[X],dsu.tajm[Y]);
        res=max({res,dsu.tajm[X],dsu.tajm[Y]});
        if(dsu.tajm[X]>dsu.tajm[Y]) X=dsu.par[X];
        else Y=dsu.par[Y];
    }
    //printf("da\n");
    bool moze=false;
    while(1){
        //printf("%i\n",X);
        if(dsu.ciklus[X]>0){
            moze=true;
            break;
        }
        if(X==dsu.par[X]) break;
        chmx(res,dsu.tajm[X]);
        X=dsu.par[X];
    }
    if(!moze) res=-1;
    if(res>-1) res=edges[res-1][0];
    //printf("da\n");
    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: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27