| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 369373 | YJU | Swapping Cities (APIO20_swap) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e6+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
struct edge{
ll x,y,c;
bool operator <(edge B){
return c<B.c;
}
}ed[N];
ll dir[N],cnt[N][2],weight[N],anc[N][20],dg[N],ptr;
vector<ll> v[N];
ll f(ll id){
return (dir[id]==id?id:dir[id]=f(dir[id]));
}
void uni(ll par,ll son){
cnt[par][0]+=cnt[son][0];
cnt[par][1]+=cnt[son][1];
dir[son]=par;
v[par].pb(son);
}
ll dcnt=1,in[N],out[N];
bool is_anc(ll x,ll y){//x is y's ancestor? true : false
return (in[x]<in[y]&&out[x]>out[y]);
}
void DFS(ll nd,ll pa){
in[nd]=dcnt++;
for(int i=1;i<20;i++){
anc[nd][i]=anc[anc[nd][i-1]][i-1];
}
for(auto i:v[nd]){
if(weight[i]==INF)weight[i]=weight[nd];
//weight[i]=min(weight[i],weight[nd]);
DFS(i,nd);
}
out[nd]=dcnt++;
}
void init(int _n,int _m,int *_u,int *_v,int *_w){
//prepare
REP(i,N)dir[i]=i;
ptr=_n;
//
REP(i,_m){
ed[i].x=_u[i]+1,ed[i].y=_v[i]+1,ed[i].c=_w[i];
}
sort(ed,ed+_m);
REP(i,_m){
ll x=ed[i].x,y=ed[i].y;
//cnt[i][0] for degree ==1,cnt[i][1] for degree >=3
if(dg[x]==1)--cnt[f(x)][0];
if(dg[y]==1)--cnt[f(y)][0];
++dg[x];++dg[y];
if(dg[x]==1)++cnt[f(x)][0];
if(dg[y]==1)++cnt[f(y)][0];
if(dg[x]==3)++cnt[f(x)][1];
if(dg[y]==3)++cnt[f(y)][1];
//
weight[++ptr]=INF;
if(f(x)==f(y)){
anc[f(x)][0]=ptr;
uni(ptr,f(x));
}else{
anc[f(x)][0]=ptr;
anc[f(y)][0]=ptr;
uni(ptr,f(x));
uni(ptr,f(y));
}
if(cnt[ptr][0]==0||cnt[ptr][1]){
weight[ptr]=ed[i].c;
}
}
REP1(i,ptr){
if(!anc[i][0])DFS(i,0);
}
}
ll lca(ll nda,ll ndb){
if(is_anc(nda,ndb))return nda;
for(int i=19;i>=0;i--){
if(anc[nda][i]&&!is_anc(anc[nda][i],ndb))nda=anc[nda][i];
}
return anc[nda][0];
}
ll getMinimumFuelCapacity(ll nda,ll ndb){
++nda;++ndb;
return (f(nda)==f(ndb)?(weight[lca(nda,ndb)]==INF?-1:weight[lca(nda,ndb)]):-1);
}
/*
ll get(ll nda,ll ndb){
return getMinimumFuelCapacity(nda,ndb);
}
int a[]={0,0};
int b[]={1,2};
int c[]={5,5};
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
init(3,2,a,b,c);
cout<<get(1,2)<<"\n";
return 0;
}
*/