oj.uz

Submission #1047678

# Submission time Handle Problem Language Result Execution time Memory
1047678 2024-08-07T14:58:29 Z vjudge1 Swapping Cities (APIO20_swap) C++17
0 / 100
 3 ms 20824 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

const int N =  5e5 + 20;
const int LOG = 21;

#define ar array

int p[N];
int nn;
vector<int> g[N];
bool ok[N];
int deg[N];

int find(int x){
	if(p[x] == x)return x;
	return p[x] = find(p[x]);
}

void join(int a,int b){
	deg[a]++, deg[b]++;
	if(deg[a] >= 3 || deg[b] >= 3)ok[nn] = 1;
	
	a = find(a), b = find(b);
	
	if(a == b)ok[nn] = 1;
	if(ok[a] || ok[b])ok[nn] = 1;
	
	p[a] = p[b] = p[nn] = nn;
	g[nn].push_back(a);
	if(a != b)g[nn].push_back(b);
	++nn;
}

int up[N][LOG];
int dp[N];
int dep[N];

void dfs(int x, int p,int lst = -1){
	//cout<<"->"<<x<<": "<<ok[x]<<endl;
	up[x][0] = p;
	for(int i = 1;i < LOG;i++)up[x][i] = up[up[x][i - 1]][i - 1];
	
	if(ok[x])lst = x;
	dp[x] = lst;
	
	for(auto u: g[x]){
		dep[u] = dep[x] + 1;
		dfs(u, x, lst);
	}
	//cout<<"<-"<<endl;
}

int lca(int a,int b){
	if(dep[a] < dep[b])swap(a, b);
	int k = dep[a] - dep[b];
	for(int i = 0;i < LOG;i++){
		if((1 << i) & k)a = up[a][i];
	}
	if(a == b)return a;
	for(int i = LOG - 1;i >= 0;i--){
		if(up[a][i] != up[b][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
}

ar<int, 3> ed[N];

int n;

void init(int _n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = _n;
	for(int i = 0;i < m;i++)ed[i] = {W[i], U[i], V[i]};
	sort(ed, ed + m);
	for(int i = 0;i < n;i++)p[i] = i;
	nn = n;
	for(int i = 0;i < m;i++)join(ed[i][1], ed[i][2]);
	dfs(nn-1, nn-1, -1);
}

int getMinimumFuelCapacity(int x, int y) {
	int l = lca(x, y);
	cout<<x<<" "<<y<<": "<<l<<endl;
	if(dp[l] - n < 0)return -1;
	return ed[dp[l] - n][0];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 20824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 20824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 20824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 20824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 20824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 20824 KB Output isn't correct
2 Halted 0 ms 0 KB -