oj.uz

Submission #679494

# Submission time Handle Problem Language Result Execution time Memory
679494 2023-01-08T12:20:28 Z Dan4Life Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 70572 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];
int p[maxn], lev[maxn], wei[maxn], line[maxn], good[maxn];

struct Edge{ int u, v, w, i; };
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 jmp[0][a];
}

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 < n; 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];
	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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51160 KB Output is correct
2 Correct 21 ms 51096 KB Output is correct
3 Correct 22 ms 51184 KB Output is correct
4 Correct 23 ms 51228 KB Output is correct
5 Correct 23 ms 51236 KB Output is correct
6 Correct 23 ms 51284 KB Output is correct
7 Correct 23 ms 51348 KB Output is correct
8 Correct 24 ms 51284 KB Output is correct
9 Correct 72 ms 60752 KB Output is correct
10 Correct 89 ms 63076 KB Output is correct
11 Correct 86 ms 62832 KB Output is correct
12 Correct 92 ms 63408 KB Output is correct
13 Correct 89 ms 65816 KB Output is correct
14 Correct 95 ms 61092 KB Output is correct
15 Correct 378 ms 67176 KB Output is correct
16 Correct 365 ms 66824 KB Output is correct
17 Correct 378 ms 67468 KB Output is correct
18 Execution timed out 2075 ms 69656 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51160 KB Output is correct
2 Correct 21 ms 51096 KB Output is correct
3 Execution timed out 2068 ms 70572 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 51160 KB Output is correct
2 Correct 21 ms 51096 KB Output is correct
3 Correct 22 ms 51184 KB Output is correct
4 Correct 23 ms 51228 KB Output is correct
5 Correct 23 ms 51236 KB Output is correct
6 Correct 23 ms 51284 KB Output is correct
7 Correct 23 ms 51348 KB Output is correct
8 Correct 24 ms 51284 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 22 ms 51160 KB Output is correct
2 Correct 21 ms 51096 KB Output is correct
3 Correct 22 ms 51184 KB Output is correct
4 Correct 23 ms 51228 KB Output is correct
5 Correct 23 ms 51236 KB Output is correct
6 Correct 23 ms 51284 KB Output is correct
7 Correct 23 ms 51348 KB Output is correct
8 Correct 24 ms 51284 KB Output is correct
9 Correct 72 ms 60752 KB Output is correct
10 Correct 89 ms 63076 KB Output is correct
11 Correct 86 ms 62832 KB Output is correct
12 Correct 92 ms 63408 KB Output is correct
13 Correct 89 ms 65816 KB Output is correct
14 Correct 95 ms 61092 KB Output is correct
15 Correct 378 ms 67176 KB Output is correct
16 Correct 365 ms 66824 KB Output is correct
17 Correct 378 ms 67468 KB Output is correct
18 Execution timed out 2075 ms 69656 KB Time limit exceeded
19 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 -