제출 #434466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434466		dqhungdl	자매 도시 (APIO20_swap)	C++17	0 / 100	1683 ms	524292 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int MAX=1e5+5;
int P[MAX];
bool isTree[MAX];
vector<int> S[MAX];
vector<iii> edges,history[MAX];

int find(int u) {
	if(P[u]==u)
		return u;
	return P[u]=find(P[u]);
}

void merge(int u,int v,int w) {
	if(S[u].size()>S[v].size())
		swap(u,v);
	P[v]=u;
	int newIsTree=isTree[u]&isTree[v];
	while(S[v].size()>0) {
		int tmp=S[v].back();
		S[v].pop_back();
		S[u].push_back(tmp);
		history[tmp].push_back({w,{u,newIsTree}});
	}
}

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++)
		edges.push_back({W[i],{U[i],V[i]}});
	sort(edges.begin(),edges.end());
	for(int i=0;i<N;i++) {
		P[i]=i;
		isTree[i]=true;
		S[i].push_back(i);
		history[i].push_back({2e9,{i,false}});
	}
	for(iii edge:edges) {
		int u=find(edge.second.first),v=find(edge.second.second),w=edge.first;
		if(u!=v)
			merge(u,v,w);
		else if(isTree[u]) {
			isTree[u]=false;
			for(int tmp:S[u])
				history[tmp].push_back({w,{u,false}});
		}
	}
}

vector<ii> getHistory(int u) {
	vector<ii> rs;
	for(iii his:history[u])
		if(!his.second.second)
			rs.push_back({his.first,his.second.first});
	return rs;
}

int getMinimumFuelCapacity(int X, int Y) {
	vector<ii> hisX=getHistory(X),hisY=getHistory(Y);
	int rs=-1;
	while(hisX.size()>0&&hisY.size()>0&&hisX.back().second==hisY.back().second) {
		rs=min(hisX.back().first,hisY.back().first);
		hisX.pop_back(),hisY.pop_back();
	}
	return rs;
}

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