oj.uz

Submission #679516

# Submission time Handle Problem Language Result Execution time Memory
679516 2023-01-08T12:41:35 Z Dan4Life Swapping Cities (APIO20_swap) C++17
6 / 100
 587 ms 66080 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, i; };
int p[maxn], lev[maxn], wei[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[e.i] = e.w;
	int x = findSet(i), y = findSet(j);
	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] | good[y] | !line[num];
	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],i};
	sort(edge,edge+m,[&](Edge &x, Edge &y){ return x.w<y.w; });
	for(int i = 0; i < m; i++) edge[i].i=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); 
	while(jmp[0][z]!=-1 and !good[z])
		for(int i = lgn-1; i >= 0; i--) 
			if(jmp[i][z]!=-1 and !good[z]) z = jmp[i][z];
	if(good[z]) return wei[z-n];
	if(jmp[0][z]!=-1) z=jmp[0][z];
	return good[z]?wei[z-n]:-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 24 ms 51156 KB Output is correct
2 Correct 29 ms 51168 KB Output is correct
3 Correct 27 ms 51132 KB Output is correct
4 Correct 23 ms 51200 KB Output is correct
5 Correct 22 ms 51216 KB Output is correct
6 Correct 26 ms 51184 KB Output is correct
7 Correct 27 ms 51168 KB Output is correct
8 Correct 25 ms 51296 KB Output is correct
9 Correct 77 ms 58440 KB Output is correct
10 Correct 94 ms 60028 KB Output is correct
11 Correct 103 ms 59884 KB Output is correct
12 Correct 95 ms 60460 KB Output is correct
13 Correct 79 ms 62744 KB Output is correct
14 Correct 89 ms 58632 KB Output is correct
15 Correct 232 ms 61928 KB Output is correct
16 Correct 211 ms 61820 KB Output is correct
17 Correct 213 ms 62204 KB Output is correct
18 Correct 471 ms 64548 KB Output is correct
19 Correct 101 ms 56092 KB Output is correct
20 Correct 244 ms 63140 KB Output is correct
21 Correct 216 ms 63248 KB Output is correct
22 Correct 224 ms 63644 KB Output is correct
23 Correct 424 ms 65960 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51156 KB Output is correct
2 Correct 29 ms 51168 KB Output is correct
3 Incorrect 587 ms 66080 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51156 KB Output is correct
2 Correct 29 ms 51168 KB Output is correct
3 Correct 27 ms 51132 KB Output is correct
4 Correct 23 ms 51200 KB Output is correct
5 Correct 22 ms 51216 KB Output is correct
6 Correct 26 ms 51184 KB Output is correct
7 Correct 27 ms 51168 KB Output is correct
8 Correct 25 ms 51296 KB Output is correct
9 Incorrect 22 ms 51156 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 51156 KB Output is correct
2 Correct 29 ms 51168 KB Output is correct
3 Correct 27 ms 51132 KB Output is correct
4 Correct 23 ms 51200 KB Output is correct
5 Correct 22 ms 51216 KB Output is correct
6 Correct 26 ms 51184 KB Output is correct
7 Correct 27 ms 51168 KB Output is correct
8 Correct 25 ms 51296 KB Output is correct
9 Correct 77 ms 58440 KB Output is correct
10 Correct 94 ms 60028 KB Output is correct
11 Correct 103 ms 59884 KB Output is correct
12 Correct 95 ms 60460 KB Output is correct
13 Correct 79 ms 62744 KB Output is correct
14 Correct 89 ms 58632 KB Output is correct
15 Correct 232 ms 61928 KB Output is correct
16 Correct 211 ms 61820 KB Output is correct
17 Correct 213 ms 62204 KB Output is correct
18 Correct 471 ms 64548 KB Output is correct
19 Incorrect 587 ms 66080 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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