Submission #718007

#	Time	Username	Problem	Language	Result	Execution time	Memory
718007		qwerasdfzxcl	Swapping Cities (APIO20_swap)	C++17	100 / 100	477 ms	46104 KiB

swap

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

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

int n;
vector<array<int, 3>> a;

struct Graph{
	int idx[100100], deg[300300], val[300300], ans[100100], sz, N;
	vector<int> adj[300300];

	void init(int n){
		N = n;
		sz = n;
		for (int i=1;i<=n;i++){
			idx[i] = i;
			deg[i] = 0;
			val[i] = INF;
			ans[i] = INF;
		}
	}

	int addV(){
		assert(sz+1 < 300300);
		deg[sz+1] = 0;
		val[sz+1] = INF;
		return ++sz;
	}

	void addE(int x, int y){
		y = idx[y];
		assert(x<=sz && y<=sz);
		adj[x].push_back(y);
		deg[y]++;
	}

	void change(int x, int y){
		idx[x] = y;
	}

	void update(int v, int w){
		v = idx[v];
		val[v] = min(val[v], w);
	}

	void dfs(int s, int v = INF){
		v = min(v, val[s]);
		if (s<=N) ans[s] = v;

		for (auto &nxt:adj[s]) dfs(nxt, v);
	}
	void init(){
		for (int i=1;i<=sz;i++) if (!deg[i]){
			dfs(i);
		}
	}
}G;

struct DSU2{
	int path[100100], mx[100100], deg[100100], isTree[100100];
	void init(int n){
		G.init(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]);
	}
	bool merge(int s, int v, int w){
		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);

			G.update(s, w);
			return 0;
		}

		path[s] = v;
		isTree[v] &= isTree[s];
		mx[v] = max(mx[v], mx[s]);
		mx[v] = max(mx[v], val);

		int tmp = G.addV();
		G.addE(tmp, s);
		G.addE(tmp, v);
		G.change(v, tmp);

		if (mx[v]>2 || !isTree[v]) G.update(v, w);

		return 1;
	}
}dsu;

struct TreeManager{
	vector<pair<int, int>> adj[100100];
	int sz, dep[100100], sp[100100][20], spE[100100][20], visited[100100];
 
	bool flag1 = 0, flag2 = 0;
 
	void init1(int n){
		flag1 = 1, flag2 = 0;
 
		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);
			visited[i] = 0, dep[i] = 0;
		}
	}
 
	void add_edge(int s, int e, int w){
		assert(flag1 && !flag2);
 
		adj[s].emplace_back(e, w);
		adj[e].emplace_back(s, 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]);
			}
		}
	}
 
	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]));
	}
}T1;

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N;
	T1.init1(n);
	dsu.init(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){
		if (dsu.merge(u, v, w)) T1.add_edge(u, v, w);
	}

	T1.init2();
	G.init();
}

int getMinimumFuelCapacity(int X, int Y) {
	++X, ++Y;
	int ans = T1.queryE(X, Y);
	ans = max(ans, G.ans[X]);
	
	return ans==INF?-1:ans;
}

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