oj.uz

Submission #679547

# Submission time Handle Problem Language Result Execution time Memory
679547 2023-01-08T13:17:57 Z Dan4Life Swapping Cities (APIO20_swap) C++17
6 / 100
 515 ms 129868 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[i]>=3)|(deg[j]>=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 41 ms 102052 KB Output is correct
2 Correct 41 ms 102068 KB Output is correct
3 Correct 41 ms 102032 KB Output is correct
4 Correct 43 ms 102192 KB Output is correct
5 Correct 44 ms 102212 KB Output is correct
6 Correct 47 ms 102228 KB Output is correct
7 Correct 47 ms 102340 KB Output is correct
8 Correct 41 ms 102300 KB Output is correct
9 Correct 95 ms 119052 KB Output is correct
10 Correct 111 ms 122984 KB Output is correct
11 Correct 108 ms 122672 KB Output is correct
12 Correct 111 ms 123960 KB Output is correct
13 Correct 99 ms 126352 KB Output is correct
14 Correct 100 ms 119172 KB Output is correct
15 Correct 214 ms 125056 KB Output is correct
16 Correct 225 ms 124436 KB Output is correct
17 Correct 220 ms 125748 KB Output is correct
18 Correct 408 ms 128052 KB Output is correct
19 Correct 114 ms 108748 KB Output is correct
20 Correct 213 ms 126316 KB Output is correct
21 Correct 223 ms 125664 KB Output is correct
22 Correct 236 ms 127084 KB Output is correct
23 Correct 418 ms 129456 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 102052 KB Output is correct
2 Correct 41 ms 102068 KB Output is correct
3 Incorrect 515 ms 129868 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 102052 KB Output is correct
2 Correct 41 ms 102068 KB Output is correct
3 Correct 41 ms 102032 KB Output is correct
4 Correct 43 ms 102192 KB Output is correct
5 Correct 44 ms 102212 KB Output is correct
6 Correct 47 ms 102228 KB Output is correct
7 Correct 47 ms 102340 KB Output is correct
8 Correct 41 ms 102300 KB Output is correct
9 Correct 44 ms 102092 KB Output is correct
10 Incorrect 43 ms 102244 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 102092 KB Output is correct
2 Correct 41 ms 102052 KB Output is correct
3 Correct 41 ms 102068 KB Output is correct
4 Correct 41 ms 102032 KB Output is correct
5 Correct 43 ms 102192 KB Output is correct
6 Correct 44 ms 102212 KB Output is correct
7 Correct 47 ms 102228 KB Output is correct
8 Correct 47 ms 102340 KB Output is correct
9 Correct 41 ms 102300 KB Output is correct
10 Correct 95 ms 119052 KB Output is correct
11 Correct 111 ms 122984 KB Output is correct
12 Correct 108 ms 122672 KB Output is correct
13 Correct 111 ms 123960 KB Output is correct
14 Correct 99 ms 126352 KB Output is correct
15 Incorrect 43 ms 102244 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 102052 KB Output is correct
2 Correct 41 ms 102068 KB Output is correct
3 Correct 41 ms 102032 KB Output is correct
4 Correct 43 ms 102192 KB Output is correct
5 Correct 44 ms 102212 KB Output is correct
6 Correct 47 ms 102228 KB Output is correct
7 Correct 47 ms 102340 KB Output is correct
8 Correct 41 ms 102300 KB Output is correct
9 Correct 95 ms 119052 KB Output is correct
10 Correct 111 ms 122984 KB Output is correct
11 Correct 108 ms 122672 KB Output is correct
12 Correct 111 ms 123960 KB Output is correct
13 Correct 99 ms 126352 KB Output is correct
14 Correct 100 ms 119172 KB Output is correct
15 Correct 214 ms 125056 KB Output is correct
16 Correct 225 ms 124436 KB Output is correct
17 Correct 220 ms 125748 KB Output is correct
18 Correct 408 ms 128052 KB Output is correct
19 Incorrect 515 ms 129868 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 102092 KB Output is correct
2 Correct 41 ms 102052 KB Output is correct
3 Correct 41 ms 102068 KB Output is correct
4 Correct 41 ms 102032 KB Output is correct
5 Correct 43 ms 102192 KB Output is correct
6 Correct 44 ms 102212 KB Output is correct
7 Correct 47 ms 102228 KB Output is correct
8 Correct 47 ms 102340 KB Output is correct
9 Correct 41 ms 102300 KB Output is correct
10 Correct 95 ms 119052 KB Output is correct
11 Correct 111 ms 122984 KB Output is correct
12 Correct 108 ms 122672 KB Output is correct
13 Correct 111 ms 123960 KB Output is correct
14 Correct 99 ms 126352 KB Output is correct
15 Correct 100 ms 119172 KB Output is correct
16 Correct 214 ms 125056 KB Output is correct
17 Correct 225 ms 124436 KB Output is correct
18 Correct 220 ms 125748 KB Output is correct
19 Correct 408 ms 128052 KB Output is correct
20 Incorrect 515 ms 129868 KB Output isn't correct
21 Halted 0 ms 0 KB -