Submission #1233402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233402		clemmy14	Swapping Cities (APIO20_swap)	C++20	0 / 100	2095 ms	22368 KiB

swap

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

int n;
// weight then node
vector<vector<pair<int, int>>> adj;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n=N;
	adj = vector<vector<pair<int, int>>>(N);
	for(int i=0; i<M; i++) {
		adj[U[i]].push_back({W[i], V[i]});
		adj[V[i]].push_back({W[i], U[i]});
	}
	for(int i=0; i<N; i++) sort(adj[i].begin(), adj[i].end());
	
}

int ans=-1;
vector<int> par;
set<pair<int, int>> noUse;

void cal(int X, int Y, int thisD) {
	vector<int> path;

	path.push_back(Y);
	for(int i=Y; i!=X; i=par[i]) {
		path.push_back(par[i]);
	}

	// for(auto x : path) cout << x << ' ';
	// cout << endl;
	int newAns=-1;
	for(int i=0; i<path.size(); i++) {
		if(path[i] == X || path[i] == Y) {
			int cnt=0;
			for(int j=0; j<adj[path[i]].size(); j++) {
				if(i != 0 && adj[path[i]][j].second == path[i-1]) continue;
				if(i != path.size()-1 && adj[path[i]][j].second == path[i+1]) continue;
				cnt++;
				if(cnt == 2) {
					if(newAns != -1) newAns=min(newAns, adj[path[i]][j].first);
					else newAns = adj[path[i]][j].first;
				}
			}
		} else {
			int cnt=0;
			for(int j=0; j<adj[path[i]].size(); j++) {
				if(i != 0 && adj[path[i]][j].second == path[i-1]) continue;
				if(i != path.size()-1 && adj[path[i]][j].second == path[i+1]) continue;
				cnt++;
				if(cnt == 1) {
					if(newAns != -1) newAns=min(newAns, adj[path[i]][j].first);
					else newAns = adj[path[i]][j].first;
				}
			}
		}
	}
	noUse.clear();
	for(int i=1; i<path.size(); i++) {
		noUse.insert({path[i], path[i-1]});
		noUse.insert({path[i-1], path[i]});
	}

	if(newAns == -1) ans=max(ans, -1);
	else if(ans == -1) ans = max(newAns, thisD);
	else ans = min(ans, max(newAns, thisD));
}

vector<bool> vis;

void dfs(int node, int X, int Y, int d) {
	if(vis[node]) return;
	if(node == Y) {
		//cout << "Yay!";
		cal(X, Y, d); 
		return;
	}
	vis[node]=true;
	for(auto [w, child] : adj[node]) if(!vis[child]) {
		par[child]=node;
		dfs(child, X, Y, max(d, w));
	} 
	//vis[node]=false;
}

int getMinimumFuelCapacity(int X, int Y) {
	ans=-1;
	par=vector<int>(n);
	vis=vector<bool>(n, false);
	dfs(X, X, Y, 0);
	return ans;
}


// void dijkstra(int s, int e) {
// 	vector<int> par(n, 0), dis(n, 1e9); dis[s]=0;
// 	vector<bool> vis(n, false);
// 	priority_queue<pair<int, int>> q; q.push({0, s});
// 	while(!q.empty()) {
// 		int node = q.top().second; q.pop();
// 		if(vis[node]) continue;
// 		if(node == e) {
// 			cal(s, e, par, dis[e]);
// 			continue;
// 		}
// 		vis[node]=true;
// 		for(auto [w, child] : adj[node]) if(!noUse.count({node, child})) {
// 			if(dis[child] > max(dis[node], w)) {
// 				dis[child]=max(dis[node], w);
// 				par[child]=node;
// 				q.push({-dis[child], child});
// 			}
// 		}
// 	}
// }

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