Submission #752820

#	Time	Username	Problem	Language	Result	Execution time	Memory
752820		winter0101	Swapping Cities (APIO20_swap)	C++14	100 / 100	386 ms	46944 KiB

swap

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
using pii=pair<int,int>;
using pli=pair<long long,int>;
const int inf=1e9+7;
const int maxn=1e5+9;
const int maxm=2e5+9;
int lab[maxn+maxm];
vector<int>a[maxn+maxm];
int deg[maxn];
int val[maxn+maxm];
bool ck[maxn+maxm];
int findset(int u){
if (lab[u]==u)return u;
return lab[u]=findset(lab[u]);
}
int nnode=0;
int n,m;
void unite(int u,int v,int w){
bool fl=false;
deg[u]++;
deg[v]++;
fl=(deg[u]>2||deg[v]>2);
u=findset(u),v=findset(v);
fl|=(ck[u]|ck[v]);
if (u==v){
   ck[u]=1;
   val[u]=min(val[u],w);
   return;
}
nnode++;
val[nnode]=1e9+7;
a[nnode].pb(u);
a[nnode].pb(v);
lab[u]=nnode;
lab[nnode]=nnode;
lab[v]=nnode;
if (fl){
    ck[nnode]=1;
    val[nnode]=w;
}
return;
}
struct edg{
int u,v,w;
bool operator < (const edg &p)const {
return w<p.w;
}
};
vector<edg>b;
int st[maxn+maxm][20];
int dep[maxn+maxm];
void dfs(int u){
for (auto v:a[u]){
    val[v]=min(val[v],val[u]);
    st[v][0]=u;
    for1(i,1,19){
    st[v][i]=st[st[v][i-1]][i-1];
    }
    dep[v]=dep[u]+1;
    dfs(v);
}
}
int lca(int u,int v){
if (dep[u]<dep[v])swap(u,v);
int k=dep[u]-dep[v];
for1(i,0,19){
if (k>>i&1)u=st[u][i];
}
if (u==v)return u;
for2(i,19,0){
if (!st[u][i]||!st[v][i])continue;
if (st[u][i]!=st[v][i]){
    u=st[u][i];
    v=st[v][i];
}
}
return st[u][0];
}
void init(int N,int M,vector<int>u1,vector<int>v1,vector<int>w){
n=N;
nnode=n;
m=M;
for1(i,1,n){
lab[i]=i;
val[i]=1e9+7;
}
for1(i,0,m-1){
b.pb({u1[i]+1,v1[i]+1,w[i]});
}
sort(all(b));
for (auto v:b){
    unite(v.u,v.v,v.w);
}
for1(i,1,nnode){
if (val[i]==0){
    val[i]=1e9+7;
}
}
dfs(nnode);
}
int getMinimumFuelCapacity(int u,int v){
int vl=val[lca(u+1,v+1)];
if (vl==inf)vl=-1;
return vl;
}

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