oj.uz

Submission #679506

# Submission time Handle Problem Language Result Execution time Memory
679506 2023-01-08T12:27:23 Z Dan4Life Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 81644 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int maxn = (int)6e5+10;
const int lgn = 22;

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

# Verdict Execution time Memory Grader output
1 Correct 27 ms 66084 KB Output is correct
2 Correct 36 ms 65968 KB Output is correct
3 Correct 30 ms 66060 KB Output is correct
4 Correct 30 ms 66116 KB Output is correct
5 Correct 29 ms 66108 KB Output is correct
6 Correct 29 ms 66124 KB Output is correct
7 Correct 29 ms 66080 KB Output is correct
8 Correct 28 ms 66152 KB Output is correct
9 Correct 75 ms 74020 KB Output is correct
10 Correct 96 ms 75824 KB Output is correct
11 Correct 115 ms 75672 KB Output is correct
12 Correct 100 ms 76272 KB Output is correct
13 Correct 94 ms 78552 KB Output is correct
14 Correct 119 ms 74144 KB Output is correct
15 Correct 453 ms 77688 KB Output is correct
16 Correct 415 ms 77412 KB Output is correct
17 Correct 398 ms 77960 KB Output is correct
18 Execution timed out 2087 ms 80088 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 66084 KB Output is correct
2 Correct 36 ms 65968 KB Output is correct
3 Execution timed out 2089 ms 81644 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 66084 KB Output is correct
2 Correct 36 ms 65968 KB Output is correct
3 Correct 30 ms 66060 KB Output is correct
4 Correct 30 ms 66116 KB Output is correct
5 Correct 29 ms 66108 KB Output is correct
6 Correct 29 ms 66124 KB Output is correct
7 Correct 29 ms 66080 KB Output is correct
8 Correct 28 ms 66152 KB Output is correct
9 Incorrect 29 ms 66072 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 66084 KB Output is correct
2 Correct 36 ms 65968 KB Output is correct
3 Correct 30 ms 66060 KB Output is correct
4 Correct 30 ms 66116 KB Output is correct
5 Correct 29 ms 66108 KB Output is correct
6 Correct 29 ms 66124 KB Output is correct
7 Correct 29 ms 66080 KB Output is correct
8 Correct 28 ms 66152 KB Output is correct
9 Correct 75 ms 74020 KB Output is correct
10 Correct 96 ms 75824 KB Output is correct
11 Correct 115 ms 75672 KB Output is correct
12 Correct 100 ms 76272 KB Output is correct
13 Correct 94 ms 78552 KB Output is correct
14 Correct 119 ms 74144 KB Output is correct
15 Correct 453 ms 77688 KB Output is correct
16 Correct 415 ms 77412 KB Output is correct
17 Correct 398 ms 77960 KB Output is correct
18 Execution timed out 2087 ms 80088 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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