제출 #717995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
717995		qwerasdfzxcl	Swapping Cities (APIO20_swap)	C++17	37 / 100	2083 ms	75500 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 1e9 + 100;

int n;
vector<int> adj[100100];
vector<array<int, 3>> a;

struct DSU{
	int path[100100];
	void init(int n){for (int i=0;i<=n;i++) path[i] = i;}
	int find(int s){
		if (s==path[s]) return s;
		return path[s] = find(path[s]);
	}
	bool merge(int s, int v){
		s = find(s), v = find(v);
		if (s==v) return 0;
		path[s] = v;
		return 1;
	}
};

struct DSU2{
	int path[100100], mx[100100], deg[100100], isTree[100100];
	void init(int n){for (int i=0;i<=n;i++) path[i] = i, mx[i] = 0, deg[i] = 0, isTree[i] = 1;}
	int find(int s){
		if (s==path[s]) return s;
		return path[s] = find(path[s]);
	}
	void merge(int s, int v){
		deg[s]++, deg[v]++;
		int val = max(deg[s], deg[v]);
		s = find(s), v = find(v);

		if (s==v){
			isTree[s] = 0;
			mx[s] = max(mx[s], val);
			return;
		}

		path[s] = v;
		isTree[v] &= isTree[s];
		mx[v] = max(mx[v], mx[s]);
		mx[v] = max(mx[v], val);
	}
	bool ok(int x, int y){
		x = find(x), y = find(y);
		return x==y && (mx[x]>2 || !isTree[x]);
	}
}dsu;

struct TreeManager{
	vector<pair<int, int>> adj[100100];
	int sz, dep[100100], sp[100100][20], spE[100100][20], spV[100100][20], visited[100100];
	DSU dsu;

	bool flag1 = 0, flag2 = 0;

	void init1(int n){
		flag1 = 1, flag2 = 0;
		dsu.init(n);

		sz = n;
		for (int i=0;i<=sz;i++){
			adj[i].clear();
			fill(sp[i], sp[i]+20, 0);
			fill(spE[i], spE[i]+20, INF);
			fill(spV[i], spV[i]+20, INF);
			visited[i] = 0, dep[i] = 0;
		}
	}

	bool add_edge(int s, int e, int w){
		assert(flag1 && !flag2);
		if (!dsu.merge(s, e)) return 0;
		// printf(" add %d %d %d\n", s-1, e-1, w);

		adj[s].emplace_back(e, w);
		adj[e].emplace_back(s, w);
		return 1;
	}

	void updateV(int s, int w){
		assert(flag1 && !flag2);
		// printf(" updateV %d %d\n", s-1, w);
		spV[s][0] = w;
	}

	void dfs(int s, int pa = 0, int paw = INF){
		assert(flag1 && flag2);
		sp[s][0] = pa;
		spE[s][0] = paw;
		dep[s] = dep[pa] + 1;
		visited[s] = 1;

		for (auto &[v, w]:adj[s]) if (!visited[v]) dfs(v, s, w);
	}

	void init2(){
		assert(flag1 && !flag2);
		flag2 = 1;
		for (int i=1;i<=sz;i++) if (!visited[i]){
			dfs(i);
		}

		for (int j=1;j<20;j++){
			for (int i=1;i<=sz;i++){
				sp[i][j] = sp[sp[i][j-1]][j-1];
				spE[i][j] = max(spE[i][j-1], spE[sp[i][j-1]][j-1]);
				spV[i][j] = min(spV[i][j-1], spV[sp[i][j-1]][j-1]);
			}
		}
	}

	int queryE(int s, int e){
		int ret = -INF;

		if (dep[s]!=dep[e]){
			if (dep[s] > dep[e]) swap(s, e);
			for (int j=19;j>=0;j--) if (dep[s] < dep[sp[e][j]]){
				ret = max(ret, spE[e][j]);
				e = sp[e][j];
			}

			ret = max(ret, spE[e][0]);
			e = sp[e][0];
		}

		if (s==e) return ret;
		for (int j=19;j>=0;j--) if (sp[s][j]!=sp[e][j]){
			ret = max(ret, spE[s][j]);
			ret = max(ret, spE[e][j]);

			s = sp[s][j];
			e = sp[e][j];
		}

		return max(ret, max(spE[s][0], spE[e][0]));
	}

	int queryV(int s, int e){
		int ret = INF;

		if (dep[s]!=dep[e]){
			if (dep[s] > dep[e]) swap(s, e);
			for (int j=19;j>=0;j--) if (dep[s] < dep[sp[e][j]]){
				ret = min(ret, spV[e][j]);
				e = sp[e][j];
			}

			ret = min(ret, spV[e][0]);
			e = sp[e][0];
		}

		if (s==e){
			ret = min(ret, spV[s][0]);
			return ret;
		}

		for (int j=19;j>=0;j--) if (sp[s][j]!=sp[e][j]){
			ret = min(ret, spV[s][j]);
			ret = min(ret, spV[e][j]);

			s = sp[s][j];
			e = sp[e][j];
		}

		ret = min(ret, min(spV[s][0], spV[e][0]));
		s = sp[s][0];
		ret = min(ret, spV[s][0]);

		return ret;
	}
}T1, T2;

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N;
	T1.init1(n);
	T2.init1(n);

	
	for (int i=0;i<M;i++) a.push_back({W[i], U[i]+1, V[i]+1});
	sort(a.begin(), a.end());

	for (const auto &[w, u, v]:a){
		adj[u].push_back(w);
		adj[v].push_back(w);

		if (T1.add_edge(u, v, w)) continue;
		// printf(" T2: ");
		T2.add_edge(u, v, w);
	}

	for (int i=1;i<=n;i++){
		sort(adj[i].begin(), adj[i].end());
		if (adj[i].size() >= 3) T1.updateV(i, adj[i][2]);
	}

	T1.init2();
	T2.init2();
}

int getMinimumFuelCapacity(int X, int Y) {
	++X, ++Y;
	int ans = INF;
	dsu.init(n);

	for (const auto &[w, u, v]:a){
		dsu.merge(u, v);
		if (dsu.ok(X, Y)){
			ans = w;
			break;
		}
	}
	
	return ans==INF?-1:ans;
}

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