Submission #1305882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305882		StefanSebez	자매 도시 (APIO20_swap)	C++20	100 / 100	211 ms	50048 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,lg=19;
int n,m;
vector<array<int,3>>grane;
//kruskal reconstruction tree
vector<int>E[N+M];
int par[N+M][lg+1],w[N+M],depth[N+M],root,nc;
bool ciklus[N+M];
void DFS(int u){
    depth[u]=depth[par[u][0]]+1;
    for(int i=1;i<=lg;i++)par[u][i]=par[par[u][i-1]][i-1];
    for(auto i:E[u])DFS(i);
}
int LCA(int u,int v){
    if(depth[u]<depth[v])swap(u,v);
    for(int i=lg;i>=0;i--)if(depth[par[u][i]]>=depth[v])u=par[u][i];if(u==v)return u;
    for(int i=lg;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];return par[u][0];
}

int dsupar[N],deg[N],rep[N];
bool dsuciklus[N];
void Init(int n){
    for(int i=0;i<=n;i++)dsupar[i]=rep[i]=i;
    nc=n;
}
int FS(int u){if(dsupar[u]==u)return u;return dsupar[u]=FS(dsupar[u]);}
void US(int u,int v,int weight){
    deg[u]++,deg[v]++;
    bool mx=0;if(max(deg[u],deg[v])>=3)mx=1;
    u=FS(u),v=FS(v);
    nc++;
    w[nc]=weight;
    par[rep[u]][0]=par[rep[v]][0]=nc;
    rep[v]=nc;
    if(u==v){
        ciklus[nc]=dsuciklus[u]=true;
        return;
    }
    ciklus[nc]=dsuciklus[v]=max({dsuciklus[u],dsuciklus[v],mx});
    dsupar[u]=v;
}
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++)grane.pb({W[i],U[i]+1,V[i]+1});
    sort(grane.begin(),grane.end());
    Init(n);
    for(auto [w,u,v]:grane) US(u,v,w);
    //for(int i=1;i<=nc;i++) printf("%i: %i\n",i,par[i][0]);
    root=++nc;
    for(int i=1;i<nc;i++)if(par[i][0]==0)par[i][0]=root;
    for(int i=1;i<=nc;i++) E[par[i][0]].pb(i);
    DFS(root);
    ciklus[0]=ciklus[root]=true;
    w[0]=w[root]=-1;
}
int getMinimumFuelCapacity(int X,int Y){
    X++,Y++;
    int u=LCA(X,Y);
    for(int i=lg;i>=0;i--){
        if(!ciklus[par[u][i]])u=par[u][i];
    }
    if(!ciklus[u])u=par[u][0];
    return w[u];
}

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