oj.uz

Submission #679549

# Submission time Handle Problem Language Result Execution time Memory
679549 2023-01-08T13:22:04 Z Dan4Life Swapping Cities (APIO20_swap) C++17
6 / 100
 592 ms 172832 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; wei[num] = e.w;
	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;
	goodd[0][i] = good[num] |= good[x]|good[y]|chk|(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 54 ms 145128 KB Output is correct
2 Correct 54 ms 145056 KB Output is correct
3 Correct 56 ms 145076 KB Output is correct
4 Correct 57 ms 145264 KB Output is correct
5 Correct 65 ms 145376 KB Output is correct
6 Correct 61 ms 145440 KB Output is correct
7 Correct 54 ms 145324 KB Output is correct
8 Correct 57 ms 145368 KB Output is correct
9 Correct 133 ms 162088 KB Output is correct
10 Correct 121 ms 166092 KB Output is correct
11 Correct 117 ms 165712 KB Output is correct
12 Correct 135 ms 166972 KB Output is correct
13 Correct 120 ms 169392 KB Output is correct
14 Correct 137 ms 162228 KB Output is correct
15 Correct 315 ms 168028 KB Output is correct
16 Correct 274 ms 167488 KB Output is correct
17 Correct 321 ms 168756 KB Output is correct
18 Correct 483 ms 171184 KB Output is correct
19 Correct 139 ms 151756 KB Output is correct
20 Correct 264 ms 169364 KB Output is correct
21 Correct 320 ms 168680 KB Output is correct
22 Correct 291 ms 170288 KB Output is correct
23 Correct 493 ms 172544 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 145128 KB Output is correct
2 Correct 54 ms 145056 KB Output is correct
3 Incorrect 592 ms 172832 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 145128 KB Output is correct
2 Correct 54 ms 145056 KB Output is correct
3 Correct 56 ms 145076 KB Output is correct
4 Correct 57 ms 145264 KB Output is correct
5 Correct 65 ms 145376 KB Output is correct
6 Correct 61 ms 145440 KB Output is correct
7 Correct 54 ms 145324 KB Output is correct
8 Correct 57 ms 145368 KB Output is correct
9 Correct 55 ms 145100 KB Output is correct
10 Incorrect 58 ms 145364 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 145100 KB Output is correct
2 Correct 54 ms 145128 KB Output is correct
3 Correct 54 ms 145056 KB Output is correct
4 Correct 56 ms 145076 KB Output is correct
5 Correct 57 ms 145264 KB Output is correct
6 Correct 65 ms 145376 KB Output is correct
7 Correct 61 ms 145440 KB Output is correct
8 Correct 54 ms 145324 KB Output is correct
9 Correct 57 ms 145368 KB Output is correct
10 Correct 133 ms 162088 KB Output is correct
11 Correct 121 ms 166092 KB Output is correct
12 Correct 117 ms 165712 KB Output is correct
13 Correct 135 ms 166972 KB Output is correct
14 Correct 120 ms 169392 KB Output is correct
15 Incorrect 58 ms 145364 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 145128 KB Output is correct
2 Correct 54 ms 145056 KB Output is correct
3 Correct 56 ms 145076 KB Output is correct
4 Correct 57 ms 145264 KB Output is correct
5 Correct 65 ms 145376 KB Output is correct
6 Correct 61 ms 145440 KB Output is correct
7 Correct 54 ms 145324 KB Output is correct
8 Correct 57 ms 145368 KB Output is correct
9 Correct 133 ms 162088 KB Output is correct
10 Correct 121 ms 166092 KB Output is correct
11 Correct 117 ms 165712 KB Output is correct
12 Correct 135 ms 166972 KB Output is correct
13 Correct 120 ms 169392 KB Output is correct
14 Correct 137 ms 162228 KB Output is correct
15 Correct 315 ms 168028 KB Output is correct
16 Correct 274 ms 167488 KB Output is correct
17 Correct 321 ms 168756 KB Output is correct
18 Correct 483 ms 171184 KB Output is correct
19 Incorrect 592 ms 172832 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 145100 KB Output is correct
2 Correct 54 ms 145128 KB Output is correct
3 Correct 54 ms 145056 KB Output is correct
4 Correct 56 ms 145076 KB Output is correct
5 Correct 57 ms 145264 KB Output is correct
6 Correct 65 ms 145376 KB Output is correct
7 Correct 61 ms 145440 KB Output is correct
8 Correct 54 ms 145324 KB Output is correct
9 Correct 57 ms 145368 KB Output is correct
10 Correct 133 ms 162088 KB Output is correct
11 Correct 121 ms 166092 KB Output is correct
12 Correct 117 ms 165712 KB Output is correct
13 Correct 135 ms 166972 KB Output is correct
14 Correct 120 ms 169392 KB Output is correct
15 Correct 137 ms 162228 KB Output is correct
16 Correct 315 ms 168028 KB Output is correct
17 Correct 274 ms 167488 KB Output is correct
18 Correct 321 ms 168756 KB Output is correct
19 Correct 483 ms 171184 KB Output is correct
20 Incorrect 592 ms 172832 KB Output isn't correct
21 Halted 0 ms 0 KB -