oj.uz

Submission #996963

# Submission time Handle Problem Language Result Execution time Memory
996963 2024-06-11T14:13:38 Z Dan4Life Swapping Cities (APIO20_swap) C++17
13 / 100
 173 ms 69244 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]==-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 7 ms 47708 KB Output is correct
2 Correct 6 ms 47784 KB Output is correct
3 Correct 8 ms 47708 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 6 ms 47728 KB Output is correct
6 Correct 6 ms 47704 KB Output is correct
7 Correct 7 ms 47708 KB Output is correct
8 Correct 6 ms 47708 KB Output is correct
9 Correct 51 ms 57332 KB Output is correct
10 Correct 66 ms 59360 KB Output is correct
11 Correct 66 ms 59332 KB Output is correct
12 Correct 66 ms 59844 KB Output is correct
13 Correct 58 ms 62404 KB Output is correct
14 Correct 59 ms 57596 KB Output is correct
15 Correct 145 ms 63568 KB Output is correct
16 Correct 123 ms 63344 KB Output is correct
17 Correct 151 ms 64304 KB Output is correct
18 Correct 158 ms 66348 KB Output is correct
19 Correct 68 ms 54612 KB Output is correct
20 Correct 160 ms 64636 KB Output is correct
21 Correct 130 ms 64640 KB Output is correct
22 Correct 131 ms 65584 KB Output is correct
23 Correct 173 ms 67888 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47708 KB Output is correct
2 Correct 6 ms 47784 KB Output is correct
3 Correct 131 ms 68492 KB Output is correct
4 Correct 137 ms 69244 KB Output is correct
5 Correct 136 ms 69244 KB Output is correct
6 Correct 135 ms 69088 KB Output is correct
7 Correct 134 ms 69216 KB Output is correct
8 Correct 138 ms 68816 KB Output is correct
9 Correct 136 ms 68900 KB Output is correct
10 Correct 124 ms 68484 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47708 KB Output is correct
2 Correct 6 ms 47784 KB Output is correct
3 Correct 8 ms 47708 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 6 ms 47728 KB Output is correct
6 Correct 6 ms 47704 KB Output is correct
7 Correct 7 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 6 ms 47848 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 7 ms 47708 KB Output is correct
3 Correct 6 ms 47784 KB Output is correct
4 Correct 8 ms 47708 KB Output is correct
5 Correct 7 ms 47708 KB Output is correct
6 Correct 6 ms 47728 KB Output is correct
7 Correct 6 ms 47704 KB Output is correct
8 Correct 7 ms 47708 KB Output is correct
9 Correct 6 ms 47708 KB Output is correct
10 Correct 51 ms 57332 KB Output is correct
11 Correct 66 ms 59360 KB Output is correct
12 Correct 66 ms 59332 KB Output is correct
13 Correct 66 ms 59844 KB Output is correct
14 Correct 58 ms 62404 KB Output is correct
15 Correct 6 ms 47848 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 7 ms 47708 KB Output is correct
2 Correct 6 ms 47784 KB Output is correct
3 Correct 8 ms 47708 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 6 ms 47728 KB Output is correct
6 Correct 6 ms 47704 KB Output is correct
7 Correct 7 ms 47708 KB Output is correct
8 Correct 6 ms 47708 KB Output is correct
9 Correct 51 ms 57332 KB Output is correct
10 Correct 66 ms 59360 KB Output is correct
11 Correct 66 ms 59332 KB Output is correct
12 Correct 66 ms 59844 KB Output is correct
13 Correct 58 ms 62404 KB Output is correct
14 Correct 59 ms 57596 KB Output is correct
15 Correct 145 ms 63568 KB Output is correct
16 Correct 123 ms 63344 KB Output is correct
17 Correct 151 ms 64304 KB Output is correct
18 Correct 158 ms 66348 KB Output is correct
19 Correct 131 ms 68492 KB Output is correct
20 Correct 137 ms 69244 KB Output is correct
21 Correct 136 ms 69244 KB Output is correct
22 Correct 135 ms 69088 KB Output is correct
23 Correct 134 ms 69216 KB Output is correct
24 Correct 138 ms 68816 KB Output is correct
25 Correct 136 ms 68900 KB Output is correct
26 Correct 124 ms 68484 KB Output is correct
27 Correct 6 ms 47848 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 7 ms 47708 KB Output is correct
3 Correct 6 ms 47784 KB Output is correct
4 Correct 8 ms 47708 KB Output is correct
5 Correct 7 ms 47708 KB Output is correct
6 Correct 6 ms 47728 KB Output is correct
7 Correct 6 ms 47704 KB Output is correct
8 Correct 7 ms 47708 KB Output is correct
9 Correct 6 ms 47708 KB Output is correct
10 Correct 51 ms 57332 KB Output is correct
11 Correct 66 ms 59360 KB Output is correct
12 Correct 66 ms 59332 KB Output is correct
13 Correct 66 ms 59844 KB Output is correct
14 Correct 58 ms 62404 KB Output is correct
15 Correct 59 ms 57596 KB Output is correct
16 Correct 145 ms 63568 KB Output is correct
17 Correct 123 ms 63344 KB Output is correct
18 Correct 151 ms 64304 KB Output is correct
19 Correct 158 ms 66348 KB Output is correct
20 Correct 131 ms 68492 KB Output is correct
21 Correct 137 ms 69244 KB Output is correct
22 Correct 136 ms 69244 KB Output is correct
23 Correct 135 ms 69088 KB Output is correct
24 Correct 134 ms 69216 KB Output is correct
25 Correct 138 ms 68816 KB Output is correct
26 Correct 136 ms 68900 KB Output is correct
27 Correct 124 ms 68484 KB Output is correct
28 Correct 6 ms 47848 KB Output is correct
29 Incorrect 6 ms 47708 KB Output isn't correct
30 Halted 0 ms 0 KB -