Submission #395327

#	Time	Username	Problem	Language	Result	Execution time	Memory
395327		ankhbayar06	Swapping Cities (APIO20_swap)	C++14	37 / 100	2088 ms	7296 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define mk make_pair

int i,n,m,b[300000],t[300000],sz[300000],a[300000],x,y;
pair<int , pair<int , int>> p[300000];

void init(int N, int M, vector <int> U, vector <int> V, vector <int> W) {
    n = N;
    m = M;
    for (i=0 ; i<m ; i++){
        p[i].first=W[i];
        p[i].second.first=U[i];
        p[i].second.second=V[i];
    }
    sort (p,p+m);
}
int fnd(int xx){
	if(xx==t[xx]){
		return xx;
	}
	else return t[xx]=fnd(t[xx]);
}
void negtge( int x , int y){
	x=fnd(x);
	y=fnd(y);
	if(sz[x] < sz[y]){
		swap(x,y);
	}
	sz[x]+=sz[y];
	if(b[y]==1){
		b[x]=1;
	}
	t[y]=x;
}
int getMinimumFuelCapacity(int u, int v){
	for(i=0 ; i<n ; i++){
		t[i]=i;
		sz[i]=1;
		b[i]=0;
		a[i]=0;
	}	
	for(i=0 ; i<m ; i++){
		x=p[i].second.first;
        y=p[i].second.second;	
        a[x]++;
        a[y]++;
        if(fnd(x)==fnd(y) || a[x]>2 || a[y]>2){
        	b[fnd(x)]=1;
        	b[fnd(y)]=1;
		}
		negtge(x,y);
		if(fnd(u)==fnd(v) && b[fnd(u)]==1){
			return p[i].first;
		}
	}
	
	return -1;	
}

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