oj.uz

Submission #996967

# Submission time Handle Problem Language Result Execution time Memory
996967 2024-06-11T14:18:13 Z Dan4Life Swapping Cities (APIO20_swap) C++17
13 / 100
 158 ms 65356 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
 
#define all(a) begin(a),end(a)
#define sz(a) (int)a.size()
#define pb push_back
 
const int mxN = (int)4e5+10;
const int mxLg = 20;
int n, m, newN, deg[mxN];
int p[mxN], line[mxN], good[mxN]; 
vector<array<int,3>> edges;
int jmp[mxLg][mxN], dep[mxN];
vector<int> adj[mxN];

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(int i, int j){
	deg[i]++, deg[j]++;
	
	int x = findSet(i), y = findSet(j);
	
	if(x==y) line[x] = 0;
	if(!line[x] or !line[y] or deg[i]>=3 or deg[j]>=3)
		line[x]=line[y]=0, good[newN]=1;
		
	adj[newN].pb(y),adj[y].pb(newN);
	if(x!=y) adj[newN].pb(x),adj[x].pb(newN);
	
	p[y] = p[x] = p[newN] = newN; newN++;
}
 
void dfs(int s, int p){
	if(p!=-1) dep[s] = dep[p]+1;
	else dep[s] = 0;
	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; newN = N;
	for(int i = 0; i < N+M; i++) 
		p[i]=i,deg[i]=0,line[i]=1;
	for(int i = 0; i < M; i++)
		edges.pb({W[i],U[i],V[i]});
	sort(all(edges),[&](array<int,3> a, array<int,3> b){
		return a[0]<b[0];
	});
	
	memset(jmp,-1,sizeof(jmp));
	
	for(int i = 0; i < M; i++)
		unionSet(edges[i][1],edges[i][2]);
		
	for(int i = newN-1; i>=0; i--) 
		if(!dep[i]) dfs(i,-1);
		
	for(int i = 1; i < mxLg; i++)
		for(int j = 0; j < newN; j++)
			if(jmp[i-1][j]!=-1) jmp[i][j] = jmp[i-1][jmp[i-1][j]];
}

int jump(int s, int x){
	for(int k = mxLg-1; k>=0 and s!=-1; k--)
		if((x>>k)&1) s = jmp[k][s];
	return s;
}

int lca(int a, int b){
	if(a==b) return a;
	if(jmp[0][a]==jmp[0][b]) return jmp[0][a];
	if(dep[a]>dep[b]) swap(a,b);
	if(dep[a]!=dep[b]) b = jump(b,dep[b]-dep[a]); 
	for(int i = mxLg-1; i>=0; i--)
		if(jmp[i][a]!=jmp[i][b] and jmp[i][a]!=-1) 
			a=jmp[i][a],b=jmp[i][b];
	if(jmp[0][a]!=jmp[0][b] or jmp[0][a]==-1) return -1;
	return lca(a,b);
}

int findNearestAnc(int s){
	if(good[s]) return s;
	for(int i = mxLg-1; i>=0; i--)
		if(jmp[i][s]!=-1 and !good[jmp[i][s]])
			s = jmp[i][s];
	return jmp[0][s];
}

int getMinimumFuelCapacity(int X, int Y) {
	int Z = lca(X, Y);
	if(Z==-1) return -1;
	Z = findNearestAnc(Z);
	if(Z==-1 or !good[Z]) return -1;
	return edges[Z-n][0];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47704 KB Output is correct
2 Correct 6 ms 47776 KB Output is correct
3 Correct 6 ms 47708 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 6 ms 47708 KB Output is correct
6 Correct 6 ms 47896 KB Output is correct
7 Correct 6 ms 47708 KB Output is correct
8 Correct 6 ms 47708 KB Output is correct
9 Correct 52 ms 55496 KB Output is correct
10 Correct 81 ms 57540 KB Output is correct
11 Correct 61 ms 57264 KB Output is correct
12 Correct 63 ms 57740 KB Output is correct
13 Correct 56 ms 60104 KB Output is correct
14 Correct 69 ms 55692 KB Output is correct
15 Correct 124 ms 59216 KB Output is correct
16 Correct 124 ms 58996 KB Output is correct
17 Correct 130 ms 59696 KB Output is correct
18 Correct 158 ms 61996 KB Output is correct
19 Correct 63 ms 52764 KB Output is correct
20 Correct 125 ms 60568 KB Output is correct
21 Correct 128 ms 60440 KB Output is correct
22 Correct 132 ms 60972 KB Output is correct
23 Correct 158 ms 63280 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47704 KB Output is correct
2 Correct 6 ms 47776 KB Output is correct
3 Correct 131 ms 64756 KB Output is correct
4 Correct 126 ms 65356 KB Output is correct
5 Correct 130 ms 65120 KB Output is correct
6 Correct 124 ms 65324 KB Output is correct
7 Correct 132 ms 65348 KB Output is correct
8 Correct 124 ms 64628 KB Output is correct
9 Correct 126 ms 65096 KB Output is correct
10 Correct 149 ms 64644 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47704 KB Output is correct
2 Correct 6 ms 47776 KB Output is correct
3 Correct 6 ms 47708 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 6 ms 47708 KB Output is correct
6 Correct 6 ms 47896 KB Output is correct
7 Correct 6 ms 47708 KB Output is correct
8 Correct 6 ms 47708 KB Output is correct
9 Correct 6 ms 47708 KB Output is correct
10 Correct 7 ms 47804 KB Output is correct
11 Incorrect 6 ms 47708 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47708 KB Output is correct
2 Correct 6 ms 47704 KB Output is correct
3 Correct 6 ms 47776 KB Output is correct
4 Correct 6 ms 47708 KB Output is correct
5 Correct 7 ms 47708 KB Output is correct
6 Correct 6 ms 47708 KB Output is correct
7 Correct 6 ms 47896 KB Output is correct
8 Correct 6 ms 47708 KB Output is correct
9 Correct 6 ms 47708 KB Output is correct
10 Correct 52 ms 55496 KB Output is correct
11 Correct 81 ms 57540 KB Output is correct
12 Correct 61 ms 57264 KB Output is correct
13 Correct 63 ms 57740 KB Output is correct
14 Correct 56 ms 60104 KB Output is correct
15 Correct 7 ms 47804 KB Output is correct
16 Incorrect 6 ms 47708 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47704 KB Output is correct
2 Correct 6 ms 47776 KB Output is correct
3 Correct 6 ms 47708 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 6 ms 47708 KB Output is correct
6 Correct 6 ms 47896 KB Output is correct
7 Correct 6 ms 47708 KB Output is correct
8 Correct 6 ms 47708 KB Output is correct
9 Correct 52 ms 55496 KB Output is correct
10 Correct 81 ms 57540 KB Output is correct
11 Correct 61 ms 57264 KB Output is correct
12 Correct 63 ms 57740 KB Output is correct
13 Correct 56 ms 60104 KB Output is correct
14 Correct 69 ms 55692 KB Output is correct
15 Correct 124 ms 59216 KB Output is correct
16 Correct 124 ms 58996 KB Output is correct
17 Correct 130 ms 59696 KB Output is correct
18 Correct 158 ms 61996 KB Output is correct
19 Correct 131 ms 64756 KB Output is correct
20 Correct 126 ms 65356 KB Output is correct
21 Correct 130 ms 65120 KB Output is correct
22 Correct 124 ms 65324 KB Output is correct
23 Correct 132 ms 65348 KB Output is correct
24 Correct 124 ms 64628 KB Output is correct
25 Correct 126 ms 65096 KB Output is correct
26 Correct 149 ms 64644 KB Output is correct
27 Correct 7 ms 47804 KB Output is correct
28 Incorrect 6 ms 47708 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 47708 KB Output is correct
2 Correct 6 ms 47704 KB Output is correct
3 Correct 6 ms 47776 KB Output is correct
4 Correct 6 ms 47708 KB Output is correct
5 Correct 7 ms 47708 KB Output is correct
6 Correct 6 ms 47708 KB Output is correct
7 Correct 6 ms 47896 KB Output is correct
8 Correct 6 ms 47708 KB Output is correct
9 Correct 6 ms 47708 KB Output is correct
10 Correct 52 ms 55496 KB Output is correct
11 Correct 81 ms 57540 KB Output is correct
12 Correct 61 ms 57264 KB Output is correct
13 Correct 63 ms 57740 KB Output is correct
14 Correct 56 ms 60104 KB Output is correct
15 Correct 69 ms 55692 KB Output is correct
16 Correct 124 ms 59216 KB Output is correct
17 Correct 124 ms 58996 KB Output is correct
18 Correct 130 ms 59696 KB Output is correct
19 Correct 158 ms 61996 KB Output is correct
20 Correct 131 ms 64756 KB Output is correct
21 Correct 126 ms 65356 KB Output is correct
22 Correct 130 ms 65120 KB Output is correct
23 Correct 124 ms 65324 KB Output is correct
24 Correct 132 ms 65348 KB Output is correct
25 Correct 124 ms 64628 KB Output is correct
26 Correct 126 ms 65096 KB Output is correct
27 Correct 149 ms 64644 KB Output is correct
28 Correct 7 ms 47804 KB Output is correct
29 Incorrect 6 ms 47708 KB Output isn't correct
30 Halted 0 ms 0 KB -