oj.uz

Submission #679554

# Submission time Handle Problem Language Result Execution time Memory
679554 2023-01-08T13:37:34 Z Dan4Life Swapping Cities (APIO20_swap) C++17
6 / 100
 659 ms 184332 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int maxn = (int)1e6+10;
const int lgn = 31;

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;
	deg[i]++, deg[j]++;
	bool chk = (deg[i]>=3 or deg[j]>=3);
	int x = findSet(i), y = findSet(j);
	if(x!=y) adj[num].pb(y);
	adj[num].pb(x); p[x]=p[y]=num;
	good[num] |= good[x]|good[y]|chk|(x==y);
	wei[num] = e.w; num++;
}

void dfs(int s, int p){
	if(p!=-1) lev[s] = lev[p]+1, jmp[0][s] = p, goodd[0][s] = good[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 < 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 < 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 54 ms 145284 KB Output is correct
2 Correct 58 ms 145292 KB Output is correct
3 Correct 55 ms 145316 KB Output is correct
4 Correct 59 ms 145504 KB Output is correct
5 Correct 57 ms 145660 KB Output is correct
6 Correct 65 ms 145584 KB Output is correct
7 Correct 54 ms 145612 KB Output is correct
8 Correct 61 ms 145732 KB Output is correct
9 Correct 120 ms 171652 KB Output is correct
10 Correct 132 ms 177376 KB Output is correct
11 Correct 160 ms 176844 KB Output is correct
12 Correct 135 ms 178700 KB Output is correct
13 Correct 121 ms 181072 KB Output is correct
14 Correct 125 ms 171568 KB Output is correct
15 Correct 289 ms 179456 KB Output is correct
16 Correct 290 ms 178568 KB Output is correct
17 Correct 310 ms 180472 KB Output is correct
18 Correct 509 ms 182808 KB Output is correct
19 Correct 160 ms 154060 KB Output is correct
20 Correct 280 ms 180676 KB Output is correct
21 Correct 311 ms 179616 KB Output is correct
22 Correct 317 ms 181884 KB Output is correct
23 Correct 494 ms 184224 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 145284 KB Output is correct
2 Correct 58 ms 145292 KB Output is correct
3 Incorrect 659 ms 184332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 145284 KB Output is correct
2 Correct 58 ms 145292 KB Output is correct
3 Correct 55 ms 145316 KB Output is correct
4 Correct 59 ms 145504 KB Output is correct
5 Correct 57 ms 145660 KB Output is correct
6 Correct 65 ms 145584 KB Output is correct
7 Correct 54 ms 145612 KB Output is correct
8 Correct 61 ms 145732 KB Output is correct
9 Correct 59 ms 145356 KB Output is correct
10 Correct 65 ms 145612 KB Output is correct
11 Correct 58 ms 145612 KB Output is correct
12 Correct 62 ms 145720 KB Output is correct
13 Correct 57 ms 145612 KB Output is correct
14 Correct 64 ms 145668 KB Output is correct
15 Incorrect 65 ms 145716 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 145356 KB Output is correct
2 Correct 54 ms 145284 KB Output is correct
3 Correct 58 ms 145292 KB Output is correct
4 Correct 55 ms 145316 KB Output is correct
5 Correct 59 ms 145504 KB Output is correct
6 Correct 57 ms 145660 KB Output is correct
7 Correct 65 ms 145584 KB Output is correct
8 Correct 54 ms 145612 KB Output is correct
9 Correct 61 ms 145732 KB Output is correct
10 Correct 120 ms 171652 KB Output is correct
11 Correct 132 ms 177376 KB Output is correct
12 Correct 160 ms 176844 KB Output is correct
13 Correct 135 ms 178700 KB Output is correct
14 Correct 121 ms 181072 KB Output is correct
15 Correct 65 ms 145612 KB Output is correct
16 Correct 58 ms 145612 KB Output is correct
17 Correct 62 ms 145720 KB Output is correct
18 Correct 57 ms 145612 KB Output is correct
19 Correct 64 ms 145668 KB Output is correct
20 Incorrect 65 ms 145716 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 145284 KB Output is correct
2 Correct 58 ms 145292 KB Output is correct
3 Correct 55 ms 145316 KB Output is correct
4 Correct 59 ms 145504 KB Output is correct
5 Correct 57 ms 145660 KB Output is correct
6 Correct 65 ms 145584 KB Output is correct
7 Correct 54 ms 145612 KB Output is correct
8 Correct 61 ms 145732 KB Output is correct
9 Correct 120 ms 171652 KB Output is correct
10 Correct 132 ms 177376 KB Output is correct
11 Correct 160 ms 176844 KB Output is correct
12 Correct 135 ms 178700 KB Output is correct
13 Correct 121 ms 181072 KB Output is correct
14 Correct 125 ms 171568 KB Output is correct
15 Correct 289 ms 179456 KB Output is correct
16 Correct 290 ms 178568 KB Output is correct
17 Correct 310 ms 180472 KB Output is correct
18 Correct 509 ms 182808 KB Output is correct
19 Incorrect 659 ms 184332 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 145356 KB Output is correct
2 Correct 54 ms 145284 KB Output is correct
3 Correct 58 ms 145292 KB Output is correct
4 Correct 55 ms 145316 KB Output is correct
5 Correct 59 ms 145504 KB Output is correct
6 Correct 57 ms 145660 KB Output is correct
7 Correct 65 ms 145584 KB Output is correct
8 Correct 54 ms 145612 KB Output is correct
9 Correct 61 ms 145732 KB Output is correct
10 Correct 120 ms 171652 KB Output is correct
11 Correct 132 ms 177376 KB Output is correct
12 Correct 160 ms 176844 KB Output is correct
13 Correct 135 ms 178700 KB Output is correct
14 Correct 121 ms 181072 KB Output is correct
15 Correct 125 ms 171568 KB Output is correct
16 Correct 289 ms 179456 KB Output is correct
17 Correct 290 ms 178568 KB Output is correct
18 Correct 310 ms 180472 KB Output is correct
19 Correct 509 ms 182808 KB Output is correct
20 Incorrect 659 ms 184332 KB Output isn't correct
21 Halted 0 ms 0 KB -