Submission #717986

#	Time	Username	Problem	Language	Result	Execution time	Memory
717986		qwerasdfzxcl	Swapping Cities (APIO20_swap)	C++17	0 / 100	714 ms	70848 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];

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 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;
	int lca, prv;

	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]);
			prv = e;
			e = sp[e][0];
		}

		if (s==e) {lca = s; 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];
		}

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

	int queryV(int s, int e){
		int ret = INF;
		if (sp[e][0]==s || sp[s][0]==e) return ret;
		
		if (lca==s) s = prv, e = sp[e][0];
		else if (lca==e) s = sp[s][0], e = prv;
		else s = sp[s][0], e = sp[e][0];

		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);

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

	for (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 = T1.queryE(X, Y);
	int v1 = T1.queryV(X, Y), v2 = T2.queryE(X, Y);
	
	ans = max(ans, min(v1, v2));
	return ans==INF?-1:ans;
}

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