제출 #1313095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313095		thuhienne	자매 도시 (APIO20_swap)	C++20	0 / 100	1 ms	332 KiB

swap

#include "swap.h"

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

using ll = long long;

#define re exit(0);

const int maxn = 100009;

int n,m;

struct E {
	int u,v,w;
	bool operator < (const E & other) {
		return w < other.w;
	}
} edge[maxn * 2];

//Kruskal reconstruction tree
int root[maxn];
int getroot(int node) {
	return (node == root[node] ? node : root[node] = getroot(root[node]));
}

int nodecount;

vector <int> krt[maxn * 2];
int weight[maxn * 2],edgepos[maxn * 2];

pair <int,int> segment[maxn * 2];

pair <int,int> merge(pair <int,int> a,pair <int,int> b) {
	if (a.first > a.second) swap(a.first,a.second);
	if (b.first > b.second) swap(b.first,b.second);
	
	if (a.first == -1 || b.first == -1) return {-1,-1};
	
	if (a.first == 0) return b;
	if (b.first == 0) return a;
	
	if (a.first == b.first && a.second == b.second) return {-1,-1};
	
	if (a.first == b.first) return {a.second,b.second};
	if (a.first == b.second) return {a.second,b.first};
	if (a.second == b.first) return {a.first,b.second};
	if (a.second == b.second) return {a.first,b.first};
	
	return {-1,-1};
}

void dfs(int node) {
	
	//leaf
	if (krt[node].empty()) {
		segment[node] = {node,node};
		return;
	}
	
	int index = edgepos[node];
	segment[node] = {edge[index].u,edge[index].v};
	for (int x : krt[node]) {
		dfs(x);
		segment[node] = merge(segment[node],segment[x]);
	}
	
	
}

void init(int N,int M,vector<int> U,vector<int> V,vector<int> W) {
	n = n,m = m;
	for (int i = 1;i <= m;i++) edge[i] = {U[i - 1] + 1,V[i - 1] + 1,W[i - 1]};
	
	//build krt
	nodecount = n;
	
	sort(edge + 1,edge + 1 + m);
	for (int i = 1;i <= n;i++) root[i] = i;
	
	for (int i = 1;i <= m;i++) {
		int u = getroot(edge[i].u),v = getroot(edge[i].v);
		
		if (u == v) continue;
		
		nodecount++;
		
		weight[nodecount] = edge[i].w;
		edgepos[nodecount] = i;
		
		krt[nodecount].push_back(u);
		krt[nodecount].push_back(v);
		
	}
	
	dfs(nodecount);
	
}

int getMinimumFuelCapacity(int x, int y) {
	x++,y++;
	
	return 0;
}

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