oj.uz

Submission #679539

# Submission time Handle Problem Language Result Execution time Memory
679539 2023-01-08T13:02:43 Z Dan4Life Swapping Cities (APIO20_swap) C++17
0 / 100
 454 ms 66460 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int maxn = (int)5e5+10;
const int lgn = 20;

int n, m, num;
int jmp[lgn][maxn];
vector<int> adj[maxn];
bool line[maxn], good[maxn];
struct Edge{ int u, v, w; };
int p[maxn], lev[maxn], wei[maxn], deg[maxn];

Edge edge[maxn];

int getPath(int x, int steps){
	for(int i = lgn-1; i >= 0; i--)
		if(steps&(1<<i) and x!=-1) x = jmp[i][x];
	return x; 
}

int lca(int a, int b){
	if(a==b) return a;
	if(jmp[0][a]==jmp[0][b]) return jmp[0][a];
	if(lev[a] < lev[b]) swap(a,b);
	a = getPath(a, lev[a]-lev[b]);
	for(int i = lgn-1; i >= 0; i--)
		if(jmp[i][a]!=-1 and jmp[i][a]!=jmp[i][b])
			a = jmp[i][a], b = jmp[i][b];
	return lca(a,b);
}

int findSet(int i){ return p[i]==i?i:p[i]=findSet(p[i]); }
bool isSameSet(int i, int j) { return findSet(i)==findSet(j); }

void unionSet(Edge &e){
	int i = e.u, j = e.v; wei[num] = e.w;
	int x = findSet(i), y = findSet(j);
	deg[x]++, deg[y]++;
	p[x]=p[y]=p[num]=num;
	if(x!=y) adj[num].pb(y);
	adj[num].pb(x); line[num]^=(x==y) | !line[x] | !line[y];
	good[num] |= good[x] or good[y] or (deg[x]>=3) or (deg[y]>=3);
	num++;
}

void dfs(int s, int p){
	if(p!=-1) lev[s] = lev[p]+1, jmp[0][s] = p;
	for(auto u : adj[s]) if(u!=p) dfs(u,s);
}

void init(int N, int M, vector<int> u, vector<int> v, vector<int> w) {
	n = N, m = M; num = n; memset(jmp,-1,sizeof(jmp));
	for(int i = 0; i <= n+m; i++) p[i] = i, line[i] = 1;
	for(int i = 0; i < m; i++) edge[i] = {u[i],v[i],w[i]};
	sort(edge,edge+m,[&](Edge &x, Edge &y){ return x.w<y.w; });
	for(int i = 0; i < m; i++) unionSet(edge[i]);
	dfs(num-1,-1);
	for(int i = 1; i < lgn; i++)
		for(int j = 0; j+(1<<i)-1 < num; j++)
			if(jmp[i-1][j]!=-1) jmp[i][j] = jmp[i-1][jmp[i-1][j]];
}

int getMinimumFuelCapacity(int x, int y) {
	int z = lca(x,y);
	for(int i = lgn-1; i >= 0; i--) 
		if(jmp[i][z]!=-1 and !good[jmp[i][z]]) z = jmp[i][z];
	if(good[z]) return wei[z];
	if(jmp[0][z]!=-1) z=jmp[0][z];
	return good[z]?wei[z]:-1;
}

/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 51176 KB Output is correct
2 Correct 20 ms 51160 KB Output is correct
3 Correct 21 ms 51140 KB Output is correct
4 Correct 23 ms 51144 KB Output is correct
5 Correct 21 ms 51284 KB Output is correct
6 Correct 23 ms 51200 KB Output is correct
7 Correct 21 ms 51212 KB Output is correct
8 Correct 20 ms 51284 KB Output is correct
9 Correct 67 ms 58796 KB Output is correct
10 Correct 115 ms 60480 KB Output is correct
11 Correct 80 ms 60364 KB Output is correct
12 Correct 86 ms 60852 KB Output is correct
13 Correct 76 ms 63144 KB Output is correct
14 Correct 90 ms 58884 KB Output is correct
15 Correct 202 ms 62316 KB Output is correct
16 Correct 195 ms 62080 KB Output is correct
17 Correct 200 ms 62604 KB Output is correct
18 Correct 366 ms 64944 KB Output is correct
19 Incorrect 91 ms 55148 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 51176 KB Output is correct
2 Correct 20 ms 51160 KB Output is correct
3 Incorrect 454 ms 66460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 51176 KB Output is correct
2 Correct 20 ms 51160 KB Output is correct
3 Correct 21 ms 51140 KB Output is correct
4 Correct 23 ms 51144 KB Output is correct
5 Correct 21 ms 51284 KB Output is correct
6 Correct 23 ms 51200 KB Output is correct
7 Correct 21 ms 51212 KB Output is correct
8 Correct 20 ms 51284 KB Output is correct
9 Incorrect 26 ms 51200 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 51176 KB Output is correct
2 Correct 20 ms 51160 KB Output is correct
3 Correct 21 ms 51140 KB Output is correct
4 Correct 23 ms 51144 KB Output is correct
5 Correct 21 ms 51284 KB Output is correct
6 Correct 23 ms 51200 KB Output is correct
7 Correct 21 ms 51212 KB Output is correct
8 Correct 20 ms 51284 KB Output is correct
9 Correct 67 ms 58796 KB Output is correct
10 Correct 115 ms 60480 KB Output is correct
11 Correct 80 ms 60364 KB Output is correct
12 Correct 86 ms 60852 KB Output is correct
13 Correct 76 ms 63144 KB Output is correct
14 Correct 90 ms 58884 KB Output is correct
15 Correct 202 ms 62316 KB Output is correct
16 Correct 195 ms 62080 KB Output is correct
17 Correct 200 ms 62604 KB Output is correct
18 Correct 366 ms 64944 KB Output is correct
19 Incorrect 454 ms 66460 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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