oj.uz

Submission #679546

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

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

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;
	int x = findSet(i), y = findSet(j);
	deg[i]++, deg[j]++;
	p[x]=p[y]=p[num]=num;
	if(x!=y) adj[num].pb(y);
	adj[num].pb(x);
	goodd[0][i] = good[num] |= good[x]|good[y]|(deg[x]>=3)|(deg[y]>=3)|(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 40 ms 102028 KB Output is correct
2 Correct 39 ms 102092 KB Output is correct
3 Correct 45 ms 102012 KB Output is correct
4 Correct 41 ms 102220 KB Output is correct
5 Correct 46 ms 102220 KB Output is correct
6 Correct 45 ms 102228 KB Output is correct
7 Correct 40 ms 102312 KB Output is correct
8 Correct 46 ms 102356 KB Output is correct
9 Correct 91 ms 119048 KB Output is correct
10 Correct 114 ms 123076 KB Output is correct
11 Correct 112 ms 122828 KB Output is correct
12 Correct 116 ms 123908 KB Output is correct
13 Correct 105 ms 126280 KB Output is correct
14 Correct 105 ms 119160 KB Output is correct
15 Correct 230 ms 125036 KB Output is correct
16 Correct 238 ms 124404 KB Output is correct
17 Correct 249 ms 125716 KB Output is correct
18 Correct 421 ms 128056 KB Output is correct
19 Correct 124 ms 108704 KB Output is correct
20 Correct 226 ms 126312 KB Output is correct
21 Correct 219 ms 125700 KB Output is correct
22 Correct 246 ms 127116 KB Output is correct
23 Correct 414 ms 129524 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 102028 KB Output is correct
2 Correct 39 ms 102092 KB Output is correct
3 Incorrect 478 ms 128504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 102028 KB Output is correct
2 Correct 39 ms 102092 KB Output is correct
3 Correct 45 ms 102012 KB Output is correct
4 Correct 41 ms 102220 KB Output is correct
5 Correct 46 ms 102220 KB Output is correct
6 Correct 45 ms 102228 KB Output is correct
7 Correct 40 ms 102312 KB Output is correct
8 Correct 46 ms 102356 KB Output is correct
9 Correct 49 ms 102124 KB Output is correct
10 Incorrect 45 ms 102280 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 102124 KB Output is correct
2 Correct 40 ms 102028 KB Output is correct
3 Correct 39 ms 102092 KB Output is correct
4 Correct 45 ms 102012 KB Output is correct
5 Correct 41 ms 102220 KB Output is correct
6 Correct 46 ms 102220 KB Output is correct
7 Correct 45 ms 102228 KB Output is correct
8 Correct 40 ms 102312 KB Output is correct
9 Correct 46 ms 102356 KB Output is correct
10 Correct 91 ms 119048 KB Output is correct
11 Correct 114 ms 123076 KB Output is correct
12 Correct 112 ms 122828 KB Output is correct
13 Correct 116 ms 123908 KB Output is correct
14 Correct 105 ms 126280 KB Output is correct
15 Incorrect 45 ms 102280 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 102028 KB Output is correct
2 Correct 39 ms 102092 KB Output is correct
3 Correct 45 ms 102012 KB Output is correct
4 Correct 41 ms 102220 KB Output is correct
5 Correct 46 ms 102220 KB Output is correct
6 Correct 45 ms 102228 KB Output is correct
7 Correct 40 ms 102312 KB Output is correct
8 Correct 46 ms 102356 KB Output is correct
9 Correct 91 ms 119048 KB Output is correct
10 Correct 114 ms 123076 KB Output is correct
11 Correct 112 ms 122828 KB Output is correct
12 Correct 116 ms 123908 KB Output is correct
13 Correct 105 ms 126280 KB Output is correct
14 Correct 105 ms 119160 KB Output is correct
15 Correct 230 ms 125036 KB Output is correct
16 Correct 238 ms 124404 KB Output is correct
17 Correct 249 ms 125716 KB Output is correct
18 Correct 421 ms 128056 KB Output is correct
19 Incorrect 478 ms 128504 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 102124 KB Output is correct
2 Correct 40 ms 102028 KB Output is correct
3 Correct 39 ms 102092 KB Output is correct
4 Correct 45 ms 102012 KB Output is correct
5 Correct 41 ms 102220 KB Output is correct
6 Correct 46 ms 102220 KB Output is correct
7 Correct 45 ms 102228 KB Output is correct
8 Correct 40 ms 102312 KB Output is correct
9 Correct 46 ms 102356 KB Output is correct
10 Correct 91 ms 119048 KB Output is correct
11 Correct 114 ms 123076 KB Output is correct
12 Correct 112 ms 122828 KB Output is correct
13 Correct 116 ms 123908 KB Output is correct
14 Correct 105 ms 126280 KB Output is correct
15 Correct 105 ms 119160 KB Output is correct
16 Correct 230 ms 125036 KB Output is correct
17 Correct 238 ms 124404 KB Output is correct
18 Correct 249 ms 125716 KB Output is correct
19 Correct 421 ms 128056 KB Output is correct
20 Incorrect 478 ms 128504 KB Output isn't correct
21 Halted 0 ms 0 KB -