oj.uz

Submission #679545

# Submission time Handle Problem Language Result Execution time Memory
679545 2023-01-08T13:14:46 Z Dan4Life Swapping Cities (APIO20_swap) C++17
6 / 100
 476 ms 129848 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[x]++, deg[y]++;
	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 39 ms 102124 KB Output is correct
2 Correct 41 ms 102068 KB Output is correct
3 Correct 39 ms 102056 KB Output is correct
4 Correct 40 ms 102204 KB Output is correct
5 Correct 40 ms 102288 KB Output is correct
6 Correct 42 ms 102220 KB Output is correct
7 Correct 40 ms 102328 KB Output is correct
8 Correct 40 ms 102244 KB Output is correct
9 Correct 98 ms 119444 KB Output is correct
10 Correct 111 ms 123480 KB Output is correct
11 Correct 108 ms 123084 KB Output is correct
12 Correct 113 ms 124408 KB Output is correct
13 Correct 101 ms 126728 KB Output is correct
14 Correct 119 ms 119500 KB Output is correct
15 Correct 216 ms 125444 KB Output is correct
16 Correct 214 ms 124776 KB Output is correct
17 Correct 232 ms 126124 KB Output is correct
18 Correct 398 ms 128532 KB Output is correct
19 Correct 118 ms 108808 KB Output is correct
20 Correct 217 ms 126672 KB Output is correct
21 Correct 221 ms 125992 KB Output is correct
22 Correct 232 ms 127748 KB Output is correct
23 Correct 411 ms 129848 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 102124 KB Output is correct
2 Correct 41 ms 102068 KB Output is correct
3 Incorrect 476 ms 128900 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 102124 KB Output is correct
2 Correct 41 ms 102068 KB Output is correct
3 Correct 39 ms 102056 KB Output is correct
4 Correct 40 ms 102204 KB Output is correct
5 Correct 40 ms 102288 KB Output is correct
6 Correct 42 ms 102220 KB Output is correct
7 Correct 40 ms 102328 KB Output is correct
8 Correct 40 ms 102244 KB Output is correct
9 Correct 40 ms 102092 KB Output is correct
10 Incorrect 41 ms 102260 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 102092 KB Output is correct
2 Correct 39 ms 102124 KB Output is correct
3 Correct 41 ms 102068 KB Output is correct
4 Correct 39 ms 102056 KB Output is correct
5 Correct 40 ms 102204 KB Output is correct
6 Correct 40 ms 102288 KB Output is correct
7 Correct 42 ms 102220 KB Output is correct
8 Correct 40 ms 102328 KB Output is correct
9 Correct 40 ms 102244 KB Output is correct
10 Correct 98 ms 119444 KB Output is correct
11 Correct 111 ms 123480 KB Output is correct
12 Correct 108 ms 123084 KB Output is correct
13 Correct 113 ms 124408 KB Output is correct
14 Correct 101 ms 126728 KB Output is correct
15 Incorrect 41 ms 102260 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 102124 KB Output is correct
2 Correct 41 ms 102068 KB Output is correct
3 Correct 39 ms 102056 KB Output is correct
4 Correct 40 ms 102204 KB Output is correct
5 Correct 40 ms 102288 KB Output is correct
6 Correct 42 ms 102220 KB Output is correct
7 Correct 40 ms 102328 KB Output is correct
8 Correct 40 ms 102244 KB Output is correct
9 Correct 98 ms 119444 KB Output is correct
10 Correct 111 ms 123480 KB Output is correct
11 Correct 108 ms 123084 KB Output is correct
12 Correct 113 ms 124408 KB Output is correct
13 Correct 101 ms 126728 KB Output is correct
14 Correct 119 ms 119500 KB Output is correct
15 Correct 216 ms 125444 KB Output is correct
16 Correct 214 ms 124776 KB Output is correct
17 Correct 232 ms 126124 KB Output is correct
18 Correct 398 ms 128532 KB Output is correct
19 Incorrect 476 ms 128900 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 102092 KB Output is correct
2 Correct 39 ms 102124 KB Output is correct
3 Correct 41 ms 102068 KB Output is correct
4 Correct 39 ms 102056 KB Output is correct
5 Correct 40 ms 102204 KB Output is correct
6 Correct 40 ms 102288 KB Output is correct
7 Correct 42 ms 102220 KB Output is correct
8 Correct 40 ms 102328 KB Output is correct
9 Correct 40 ms 102244 KB Output is correct
10 Correct 98 ms 119444 KB Output is correct
11 Correct 111 ms 123480 KB Output is correct
12 Correct 108 ms 123084 KB Output is correct
13 Correct 113 ms 124408 KB Output is correct
14 Correct 101 ms 126728 KB Output is correct
15 Correct 119 ms 119500 KB Output is correct
16 Correct 216 ms 125444 KB Output is correct
17 Correct 214 ms 124776 KB Output is correct
18 Correct 232 ms 126124 KB Output is correct
19 Correct 398 ms 128532 KB Output is correct
20 Incorrect 476 ms 128900 KB Output isn't correct
21 Halted 0 ms 0 KB -