제출 #394645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
394645		khangal	자매 도시 (APIO20_swap)	C++14	17 / 100	2077 ms	6560 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,c[123456],x,y,z,l,r,cnt,cnt1,ans;
vector<pair<ll,pl>> edge;
bool ok,ok1;
ll par[123456],path[123456],sz[123456],w,mx[123456];
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]}});
    }
    n=N;
    sort(edge.begin(),edge.end());
}

ll dsu(ll x){
    if(par[x]==x)return x;
    else return dsu(par[x]);
}

void connect(ll x,ll y){
    x=dsu(x);
    y=dsu(y);
    if(x!=y){
        par[y]=x;
        mx[x]=max(mx[x],mx[y]);
        sz[x]+=sz[y];
        path[x]+=path[y];
    }
}

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;
	}
}
int getMinimumFuelCapacity(int X, int Y) {
	run();
    for(auto u:edge){
        x=u.ss.ff;
        y=u.ss.ss;
        connect(x,y);
        c[x]++;
        c[y]++;
        x=dsu(x);
        y=dsu(y);
        path[x]++;
        mx[x] = max(mx[x],c[u.ss.ff]);
        mx[y] = max(mx[y],c[u.ss.ss]);
        if(dsu(X)!=dsu(Y))continue;
        if(mx[dsu(X)]<3&&path[dsu(X)]<sz[dsu(X)])continue;
        return u.ff;
    }
    return -1;
}

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