Submission #394746

#	Time	Username	Problem	Language	Result	Execution time	Memory
394746		khangal	Swapping Cities (APIO20_swap)	C++14	6 / 100	128 ms	9252 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pl;
#define pb push_back
#define ff first
#define ss second
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,m,mid,mn,T,sum,h1,h2,x,y,z,l,r,cnt,cnt1,ans;
vector<pair<ll,pl>> edge;
bool ok,ok1;
vector<int> par,path,sz,w,mx,lvl,c;
ll len;
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    for(int i=0;i<M;i++){
        edge.pb({W[i],{U[i],V[i]}});
        ans=max(ans,W[i]);
    }
    n=N;
    m=M;
    par.resize(n);
	path.resize(n);
    sz.resize(n);
    mx.resize(n);
    lvl.resize(n);
    c.resize(n);
    sort(edge.begin(),edge.end());
    len=U.size();
}


int dsu(ll x){
    return par[x] = (par[x] == x ? x : dsu(par[x]));
}
 
void connect(ll x,ll y){
    x=dsu(x);
    y=dsu(y);
    if(x==y){
    	return;
    }
    else{
    	
    	if(lvl[x]>=lvl[y]){
	        par[y]=x;
	        mx[x]=max(mx[x],mx[y]);
	        sz[x]+=sz[y];
	        path[x]+=path[y];
		}
		else{
			par[x]=y;
	        mx[y]=max(mx[x],mx[y]);
	        sz[y]+=sz[x];
	        path[y]+=path[x];
		}
	}
}

void run(){
	for(int i=0;i<n;i++){
        par[i]=i;
    }
    for(int i=0;i<n;i++){
    	c[i]=0;
    	path[i]=0;
    	sz[i]=1;
    	mx[i]=0;
    	lvl[i]=0;
	}
}
int getMinimumFuelCapacity(int X, int Y) {
	if(len<=5){
	run();
    for(auto u:edge){
        x=u.ss.ff;
        y=u.ss.ss;
        connect(x,y);
        c[x]++;
        c[y]++;
        path[dsu(x)]++;
        mx[dsu(x)] = max(mx[dsu(x)],c[x]);
        mx[dsu(y)] = max(mx[dsu(y)],c[y]);
        if(dsu(X)!=dsu(Y))continue;
        if(mx[dsu(X)]<3&&path[dsu(X)]<sz[dsu(X)])continue;
        return u.ff;
    }
    return -1;}
    else{
		if(m+1==n)return -1;
		else return ans;
	}
}	

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