oj.uz

Submission #679542

# Submission time Handle Problem Language Result Execution time Memory
679542 2023-01-08T13:11:36 Z Dan4Life Swapping Cities (APIO20_swap) C++17
6 / 100
 479 ms 82756 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;
bool good[maxn];
int jmp[lgn][maxn], goodd[lgn][maxn];
vector<int> adj[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);
	goodd[0][i] = good[num] |= good[x]|good[y]|(deg[x]>=3)|(deg[y]>=3)|(x==y);
	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;
	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]];
	for(int i = 1; i < lgn; i++)
		for(int j = 0; j+(1<<i)-1 < num; j++)
			goodd[i][j] = goodd[i-1][goodd[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 !goodd[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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 51156 KB Output is correct
2 Correct 21 ms 51180 KB Output is correct
3 Correct 27 ms 51232 KB Output is correct
4 Correct 23 ms 51344 KB Output is correct
5 Correct 25 ms 51404 KB Output is correct
6 Correct 22 ms 51336 KB Output is correct
7 Correct 25 ms 51432 KB Output is correct
8 Correct 24 ms 51484 KB Output is correct
9 Correct 81 ms 68488 KB Output is correct
10 Correct 87 ms 72520 KB Output is correct
11 Correct 91 ms 72176 KB Output is correct
12 Correct 121 ms 73400 KB Output is correct
13 Correct 87 ms 75800 KB Output is correct
14 Correct 85 ms 68656 KB Output is correct
15 Correct 222 ms 74468 KB Output is correct
16 Correct 237 ms 73880 KB Output is correct
17 Correct 224 ms 75316 KB Output is correct
18 Correct 384 ms 77620 KB Output is correct
19 Correct 101 ms 59684 KB Output is correct
20 Correct 207 ms 79612 KB Output is correct
21 Correct 226 ms 78900 KB Output is correct
22 Correct 228 ms 80548 KB Output is correct
23 Correct 430 ms 82756 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 51156 KB Output is correct
2 Correct 21 ms 51180 KB Output is correct
3 Incorrect 479 ms 77988 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 51156 KB Output is correct
2 Correct 21 ms 51180 KB Output is correct
3 Correct 27 ms 51232 KB Output is correct
4 Correct 23 ms 51344 KB Output is correct
5 Correct 25 ms 51404 KB Output is correct
6 Correct 22 ms 51336 KB Output is correct
7 Correct 25 ms 51432 KB Output is correct
8 Correct 24 ms 51484 KB Output is correct
9 Correct 21 ms 51156 KB Output is correct
10 Incorrect 21 ms 51428 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 51156 KB Output is correct
2 Correct 20 ms 51156 KB Output is correct
3 Correct 21 ms 51180 KB Output is correct
4 Correct 27 ms 51232 KB Output is correct
5 Correct 23 ms 51344 KB Output is correct
6 Correct 25 ms 51404 KB Output is correct
7 Correct 22 ms 51336 KB Output is correct
8 Correct 25 ms 51432 KB Output is correct
9 Correct 24 ms 51484 KB Output is correct
10 Correct 81 ms 68488 KB Output is correct
11 Correct 87 ms 72520 KB Output is correct
12 Correct 91 ms 72176 KB Output is correct
13 Correct 121 ms 73400 KB Output is correct
14 Correct 87 ms 75800 KB Output is correct
15 Incorrect 21 ms 51428 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 51156 KB Output is correct
2 Correct 21 ms 51180 KB Output is correct
3 Correct 27 ms 51232 KB Output is correct
4 Correct 23 ms 51344 KB Output is correct
5 Correct 25 ms 51404 KB Output is correct
6 Correct 22 ms 51336 KB Output is correct
7 Correct 25 ms 51432 KB Output is correct
8 Correct 24 ms 51484 KB Output is correct
9 Correct 81 ms 68488 KB Output is correct
10 Correct 87 ms 72520 KB Output is correct
11 Correct 91 ms 72176 KB Output is correct
12 Correct 121 ms 73400 KB Output is correct
13 Correct 87 ms 75800 KB Output is correct
14 Correct 85 ms 68656 KB Output is correct
15 Correct 222 ms 74468 KB Output is correct
16 Correct 237 ms 73880 KB Output is correct
17 Correct 224 ms 75316 KB Output is correct
18 Correct 384 ms 77620 KB Output is correct
19 Incorrect 479 ms 77988 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 51156 KB Output is correct
2 Correct 20 ms 51156 KB Output is correct
3 Correct 21 ms 51180 KB Output is correct
4 Correct 27 ms 51232 KB Output is correct
5 Correct 23 ms 51344 KB Output is correct
6 Correct 25 ms 51404 KB Output is correct
7 Correct 22 ms 51336 KB Output is correct
8 Correct 25 ms 51432 KB Output is correct
9 Correct 24 ms 51484 KB Output is correct
10 Correct 81 ms 68488 KB Output is correct
11 Correct 87 ms 72520 KB Output is correct
12 Correct 91 ms 72176 KB Output is correct
13 Correct 121 ms 73400 KB Output is correct
14 Correct 87 ms 75800 KB Output is correct
15 Correct 85 ms 68656 KB Output is correct
16 Correct 222 ms 74468 KB Output is correct
17 Correct 237 ms 73880 KB Output is correct
18 Correct 224 ms 75316 KB Output is correct
19 Correct 384 ms 77620 KB Output is correct
20 Incorrect 479 ms 77988 KB Output isn't correct
21 Halted 0 ms 0 KB -