oj.uz

Submission #679544

# Submission time Handle Problem Language Result Execution time Memory
679544 2023-01-08T13:13:51 Z Dan4Life Swapping Cities (APIO20_swap) C++17
6 / 100
 510 ms 79024 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][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 22 ms 51156 KB Output is correct
2 Correct 23 ms 51232 KB Output is correct
3 Correct 23 ms 51156 KB Output is correct
4 Correct 23 ms 51296 KB Output is correct
5 Correct 24 ms 51448 KB Output is correct
6 Correct 25 ms 51412 KB Output is correct
7 Correct 24 ms 51412 KB Output is correct
8 Correct 24 ms 51540 KB Output is correct
9 Correct 81 ms 68484 KB Output is correct
10 Correct 97 ms 72468 KB Output is correct
11 Correct 90 ms 72136 KB Output is correct
12 Correct 100 ms 73388 KB Output is correct
13 Correct 86 ms 75820 KB Output is correct
14 Correct 90 ms 68548 KB Output is correct
15 Correct 214 ms 74536 KB Output is correct
16 Correct 215 ms 73904 KB Output is correct
17 Correct 223 ms 75316 KB Output is correct
18 Correct 405 ms 77548 KB Output is correct
19 Correct 98 ms 57908 KB Output is correct
20 Correct 209 ms 75820 KB Output is correct
21 Correct 225 ms 75144 KB Output is correct
22 Correct 225 ms 76700 KB Output is correct
23 Correct 417 ms 79024 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51156 KB Output is correct
2 Correct 23 ms 51232 KB Output is correct
3 Incorrect 510 ms 77968 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51156 KB Output is correct
2 Correct 23 ms 51232 KB Output is correct
3 Correct 23 ms 51156 KB Output is correct
4 Correct 23 ms 51296 KB Output is correct
5 Correct 24 ms 51448 KB Output is correct
6 Correct 25 ms 51412 KB Output is correct
7 Correct 24 ms 51412 KB Output is correct
8 Correct 24 ms 51540 KB Output is correct
9 Correct 23 ms 51156 KB Output is correct
10 Incorrect 24 ms 51416 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 51156 KB Output is correct
2 Correct 22 ms 51156 KB Output is correct
3 Correct 23 ms 51232 KB Output is correct
4 Correct 23 ms 51156 KB Output is correct
5 Correct 23 ms 51296 KB Output is correct
6 Correct 24 ms 51448 KB Output is correct
7 Correct 25 ms 51412 KB Output is correct
8 Correct 24 ms 51412 KB Output is correct
9 Correct 24 ms 51540 KB Output is correct
10 Correct 81 ms 68484 KB Output is correct
11 Correct 97 ms 72468 KB Output is correct
12 Correct 90 ms 72136 KB Output is correct
13 Correct 100 ms 73388 KB Output is correct
14 Correct 86 ms 75820 KB Output is correct
15 Incorrect 24 ms 51416 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51156 KB Output is correct
2 Correct 23 ms 51232 KB Output is correct
3 Correct 23 ms 51156 KB Output is correct
4 Correct 23 ms 51296 KB Output is correct
5 Correct 24 ms 51448 KB Output is correct
6 Correct 25 ms 51412 KB Output is correct
7 Correct 24 ms 51412 KB Output is correct
8 Correct 24 ms 51540 KB Output is correct
9 Correct 81 ms 68484 KB Output is correct
10 Correct 97 ms 72468 KB Output is correct
11 Correct 90 ms 72136 KB Output is correct
12 Correct 100 ms 73388 KB Output is correct
13 Correct 86 ms 75820 KB Output is correct
14 Correct 90 ms 68548 KB Output is correct
15 Correct 214 ms 74536 KB Output is correct
16 Correct 215 ms 73904 KB Output is correct
17 Correct 223 ms 75316 KB Output is correct
18 Correct 405 ms 77548 KB Output is correct
19 Incorrect 510 ms 77968 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 51156 KB Output is correct
2 Correct 22 ms 51156 KB Output is correct
3 Correct 23 ms 51232 KB Output is correct
4 Correct 23 ms 51156 KB Output is correct
5 Correct 23 ms 51296 KB Output is correct
6 Correct 24 ms 51448 KB Output is correct
7 Correct 25 ms 51412 KB Output is correct
8 Correct 24 ms 51412 KB Output is correct
9 Correct 24 ms 51540 KB Output is correct
10 Correct 81 ms 68484 KB Output is correct
11 Correct 97 ms 72468 KB Output is correct
12 Correct 90 ms 72136 KB Output is correct
13 Correct 100 ms 73388 KB Output is correct
14 Correct 86 ms 75820 KB Output is correct
15 Correct 90 ms 68548 KB Output is correct
16 Correct 214 ms 74536 KB Output is correct
17 Correct 215 ms 73904 KB Output is correct
18 Correct 223 ms 75316 KB Output is correct
19 Correct 405 ms 77548 KB Output is correct
20 Incorrect 510 ms 77968 KB Output isn't correct
21 Halted 0 ms 0 KB -