Submission #1288294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288294		Jawad_Akbar_JJ	Swapping Cities (APIO20_swap)	C++20	7 / 100	550 ms	68236 KiB

swap

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
const int N = 1<<18;
vector<pair<int, int>> nei[N];
vector<int> ins[N], ers[N];
multiset<int> weiNei[N];
int Par[N][20], parent[N], hei[N], Mn[N][20], Mx[N][20], seen[N], wei[N], MinCycle[N], inf = 1e9 + 7;

int moveUpMx(int v, int d, int Ans = 0){
	for (int i=0;i<17;i++){
		if ((1<<i) & d)
			Ans = max(Ans, Mx[v][i]), v = Par[v][i]; 
	}
	return Ans;
}

int moveUpMn(int v, int d, int Ans = inf){
	for (int i=0;i<17;i++){
		if ((1<<i) & d)
			Ans = min(Ans, Mn[v][i]), v = Par[v][i]; 
	}
	return Ans;
}

void dfs1(int u, int p, int id){
	seen[u] = 1;
	hei[u] = hei[p] + 1;
	Par[u][0] = p;
	Mx[u][0] = wei[id];

	for (int i=0;i<17;i++){
		Par[u][i+1] = Par[Par[u][i]][i];
		Mx[u][i+1] = max(Mx[u][i], Mx[Par[u][i]][i]);
	}

	for (auto [i, id2] : nei[u]){
		if (id2 == id)
			continue;
		if (seen[i] == 1 and hei[i] < hei[u]){
			int mn = max(wei[id2], moveUpMx(u, hei[u] - hei[i]));
			// if (mn == 2){
			// 	cout<<u<<" "<<i<<" "<<p<<" eendndkdn "<<hei[u] - hei[i]<<" "<<Mx[u][1]<<" "<<moveUpMx(u, hei[u] - hei[i])<<endl;
			// }
			ins[i].push_back(mn);
			ers[u].push_back(mn);
		}
		else if (seen[i] != 1){
			// cout<<u<<" --> "<<i<<endl;
			dfs1(i, u, id2);
		}
	}
}

multiset<int> ms;
void dfs2(int u, int p, int id){
	seen[u] = 2;
	for (int i : ins[u])
		ms.insert(i);
	if (ms.size() > 0)
		MinCycle[u] = *ms.begin();
	else
		MinCycle[u] = inf;

	for (auto [i, id2] : nei[u]){
		if (id2 != id and seen[i] != 2)
			dfs2(i, u, id2);
	}
	for (int i : ers[u])
		ms.erase(ms.find(i));
}

int root(int v){
	return (parent[v] == v ? v : parent[v] = root(parent[v]));
}

void dfs3(int u, int p, int edWei){
	weiNei[p].erase(weiNei[p].find(edWei));
	Mn[u][0] = *weiNei[p].begin();
	Mx[u][0] = edWei;
	hei[u] = hei[p] + 1;
	Par[u][0] = p;
	
	for (int i=0;i<17;i++){
		Par[u][i+1] = Par[Par[u][i]][i];
		Mx[u][i+1] = max(Mx[u][i], Mx[Par[u][i]][i]);
		Mn[u][i+1] = min(Mn[u][i], Mn[Par[u][i]][i]);
	}

	for (auto [i, c] : nei[u]){
		if (i == p)
			continue;
		weiNei[i].erase(weiNei[i].find(c));

		dfs3(i, u, c);
		weiNei[i].insert(c);
	}

	weiNei[p].insert(edWei);
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
	vector<pair<int, pair<int,int>>> Ed;
	for (int i=0;i<m;i++){
		wei[i] = w[i];
		u[i]++, v[i]++;
		weiNei[u[i]].insert(w[i]);
		weiNei[v[i]].insert(w[i]);
		nei[u[i]].push_back({v[i], i});
		nei[v[i]].push_back({u[i], i});
		Ed.push_back({w[i], {u[i], v[i]}});
	}

	dfs1(1, 0, N - 1);
	dfs2(1, 0, N - 1);

	for (int i=0;i<=n;i++){
		nei[i].clear(), parent[i] = i;
		weiNei[i].insert(inf);
		weiNei[i].insert(inf);
	}

	sort(Ed.begin(), Ed.end());

	for (auto [c, pr] : Ed){
		int A = root(pr.first), B = root(pr.second);

		if (A != B){
			parent[B] = A;
			nei[pr.first].push_back({pr.second, c});
			nei[pr.second].push_back({pr.first, c});
			// cout<<pr.first<<"    "<<pr.second<<" "<<c<<endl;
		}
	}


	dfs3(1, 0, inf);
}

int getMinimumFuelCapacity(int u, int v){
	u++, v++;

	int AnsCycle = min(MinCycle[u], MinCycle[v]), EndPoint;	
	if (hei[u] > hei[v])
		swap(u, v);
	
	int a = u, b = v, minEx = inf, maxOnPath = 0;

	weiNei[b].erase(weiNei[b].find(Mx[b][0]));
	EndPoint = *next(weiNei[b].begin());
	weiNei[b].insert(Mx[b][0]);

	for (int i=16;i>=0;i--){
		if (hei[a] + (1<<i) < hei[b])
			b = Par[b][i];
	}

	if (Par[b][0] == a){
		weiNei[a].erase(weiNei[a].find(Mx[b][0]));
		EndPoint = min(EndPoint, *next(weiNei[a].begin()));
		weiNei[a].insert(Mx[b][0]);

		minEx = moveUpMn(u, hei[v] - hei[b]);
		maxOnPath = moveUpMx(v, hei[v] - hei[a]);
	}
	else{
		weiNei[a].erase(weiNei[a].find(Mx[a][0]));
		EndPoint = min(EndPoint, *next(weiNei[a].begin()));
		weiNei[a].insert(Mx[a][0]);

		if (hei[b] != hei[a])
			b = Par[b][0];

		for (int i=16;i>=0;i--){
			if (Par[a][i] != Par[b][i])
				a = Par[a][i], b = Par[b][i];
		}

		int lca = Par[a][0];
		minEx = min(moveUpMn(u, hei[u] - hei[a]), moveUpMn(v, hei[v] - hei[b]));
		maxOnPath = max(moveUpMx(u, hei[u] - hei[lca]), moveUpMx(v, hei[v] - hei[lca]));

		weiNei[lca].erase(weiNei[lca].find(Mx[a][0]));
		weiNei[lca].erase(weiNei[lca].find(Mx[b][0]));

		minEx = min(minEx, *weiNei[lca].begin());

		weiNei[lca].insert(Mx[a][0]);
		weiNei[lca].insert(Mx[b][0]);
	}

	int finalAns = max(maxOnPath, min(minEx, min(EndPoint, AnsCycle)));
	if (finalAns == inf)
		finalAns = -1;
	return finalAns;
}

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