oj.uz

Submission #897096

# Submission time Handle Problem Language Result Execution time Memory
897096 2024-01-02T14:29:09 Z LCJLY Swapping Cities (APIO20_swap) C++14
0 / 100
 216 ms 83960 KB 
#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;

vector<int>adj[500005];
int cost[500005];

struct DSU{
	vector<int>e;
	void init(int n){
		e=vector<int>(n,-1);
	}
	
	int get(int x){return e[x]<0?x:e[x]=get(e[x]);}
	
	bool unite(int x, int y){ //x is par
		x=get(x),y=get(y);
		if(x==y) return 0;
		adj[x].push_back(y);
		adj[y].push_back(x);
		e[x]+=e[y];
		e[y]=x;
		return 1;
	}
};

int two[22][500005];
int d[500005];
void dfs(int index, int par){
	for(int x=0;x<20;x++){
		if(two[x][index]==-1) break;
		two[x+1][index]=two[x][two[x][index]];
	}
	
	for(auto it:adj[index]){
		if(it==par) continue;
		two[0][it]=index;
		d[it]=d[index]+1;
		dfs(it,index);
	}
}

int lca(int a, int b){
	if(d[a]>d[b]) swap(a,b);
	int diff=d[b]-d[a];
	for(int x=0;x<20;x++){
		if(diff&(1<<x)) b=two[x][b];
	}
	
	if(a==b) return a;
	for(int x=19;x>=0;x--){
		if(two[x][b]!=two[x][a]){
			a=two[x][a];
			b=two[x][b];
		}
	}
	return two[0][a];
}

bool done[300005];


int root=0;
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
	pair<int,pii>edge[m];
	for(int x=0;x<m;x++){
		edge[x].first=w[x];
		edge[x].second={u[x],v[x]};
	}
	
	sort(edge,edge+m);
	
	DSU dsu;
	dsu.init(n+m+20);
	
	int in[n+5];
	memset(in,0,sizeof(in));
	
	for(int x=0;x<m;x++){
		int l=edge[x].second.first;
		int r=edge[x].second.second;
		int hold=edge[x].first;
		in[l]++;
		in[r]++;
		
		if(in[l]>2||in[r]>2) done[n+x+1]=true;
		l=dsu.get(l);
		r=dsu.get(r);
		if(l==r||done[l]||done[r]) done[n+x+1]=true;
		dsu.unite(n+x+1,l);
		dsu.unite(n+x+1,r);
		cost[n+x+1]=hold;
	}
	
	memset(two,-1,sizeof(two));
	
	dfs(n+m,-1);
	root=n+m;
}

int getMinimumFuelCapacity(int x, int y){
	int hold=lca(x,y);
	
	if(done[hold]){
		return cost[hold];
	}
	
	int cur=hold;
	for(int x=19;x>=0;x--){
		if(d[hold]&(1<<x)){
			if(!done[two[x][cur]]){
				cur=two[x][cur];
			}
		}
	}
	
	if(cur==root) return -1;
	return cost[two[0][cur]];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 57176 KB Output is correct
2 Correct 9 ms 57180 KB Output is correct
3 Correct 9 ms 57180 KB Output is correct
4 Correct 9 ms 57176 KB Output is correct
5 Correct 10 ms 57264 KB Output is correct
6 Correct 9 ms 57180 KB Output is correct
7 Correct 9 ms 57180 KB Output is correct
8 Correct 9 ms 57180 KB Output is correct
9 Correct 64 ms 67892 KB Output is correct
10 Correct 106 ms 70484 KB Output is correct
11 Correct 92 ms 70228 KB Output is correct
12 Correct 86 ms 70972 KB Output is correct
13 Correct 92 ms 74860 KB Output is correct
14 Correct 78 ms 68236 KB Output is correct
15 Correct 173 ms 74284 KB Output is correct
16 Correct 162 ms 73964 KB Output is correct
17 Correct 214 ms 74832 KB Output is correct
18 Correct 216 ms 78772 KB Output is correct
19 Incorrect 74 ms 64404 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 57176 KB Output is correct
2 Correct 9 ms 57180 KB Output is correct
3 Correct 199 ms 79368 KB Output is correct
4 Correct 176 ms 83960 KB Output is correct
5 Incorrect 191 ms 83704 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 57176 KB Output is correct
2 Correct 9 ms 57180 KB Output is correct
3 Correct 9 ms 57180 KB Output is correct
4 Correct 9 ms 57176 KB Output is correct
5 Correct 10 ms 57264 KB Output is correct
6 Correct 9 ms 57180 KB Output is correct
7 Correct 9 ms 57180 KB Output is correct
8 Correct 9 ms 57180 KB Output is correct
9 Correct 10 ms 57180 KB Output is correct
10 Correct 9 ms 57176 KB Output is correct
11 Correct 9 ms 57180 KB Output is correct
12 Correct 11 ms 57180 KB Output is correct
13 Correct 9 ms 57224 KB Output is correct
14 Correct 9 ms 57128 KB Output is correct
15 Incorrect 9 ms 57140 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 57180 KB Output is correct
2 Correct 12 ms 57176 KB Output is correct
3 Correct 9 ms 57180 KB Output is correct
4 Correct 9 ms 57180 KB Output is correct
5 Correct 9 ms 57176 KB Output is correct
6 Correct 10 ms 57264 KB Output is correct
7 Correct 9 ms 57180 KB Output is correct
8 Correct 9 ms 57180 KB Output is correct
9 Correct 9 ms 57180 KB Output is correct
10 Correct 64 ms 67892 KB Output is correct
11 Correct 106 ms 70484 KB Output is correct
12 Correct 92 ms 70228 KB Output is correct
13 Correct 86 ms 70972 KB Output is correct
14 Correct 92 ms 74860 KB Output is correct
15 Correct 9 ms 57176 KB Output is correct
16 Correct 9 ms 57180 KB Output is correct
17 Correct 11 ms 57180 KB Output is correct
18 Correct 9 ms 57224 KB Output is correct
19 Correct 9 ms 57128 KB Output is correct
20 Incorrect 9 ms 57140 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 57176 KB Output is correct
2 Correct 9 ms 57180 KB Output is correct
3 Correct 9 ms 57180 KB Output is correct
4 Correct 9 ms 57176 KB Output is correct
5 Correct 10 ms 57264 KB Output is correct
6 Correct 9 ms 57180 KB Output is correct
7 Correct 9 ms 57180 KB Output is correct
8 Correct 9 ms 57180 KB Output is correct
9 Correct 64 ms 67892 KB Output is correct
10 Correct 106 ms 70484 KB Output is correct
11 Correct 92 ms 70228 KB Output is correct
12 Correct 86 ms 70972 KB Output is correct
13 Correct 92 ms 74860 KB Output is correct
14 Correct 78 ms 68236 KB Output is correct
15 Correct 173 ms 74284 KB Output is correct
16 Correct 162 ms 73964 KB Output is correct
17 Correct 214 ms 74832 KB Output is correct
18 Correct 216 ms 78772 KB Output is correct
19 Correct 199 ms 79368 KB Output is correct
20 Correct 176 ms 83960 KB Output is correct
21 Incorrect 191 ms 83704 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 57180 KB Output is correct
2 Correct 12 ms 57176 KB Output is correct
3 Correct 9 ms 57180 KB Output is correct
4 Correct 9 ms 57180 KB Output is correct
5 Correct 9 ms 57176 KB Output is correct
6 Correct 10 ms 57264 KB Output is correct
7 Correct 9 ms 57180 KB Output is correct
8 Correct 9 ms 57180 KB Output is correct
9 Correct 9 ms 57180 KB Output is correct
10 Correct 64 ms 67892 KB Output is correct
11 Correct 106 ms 70484 KB Output is correct
12 Correct 92 ms 70228 KB Output is correct
13 Correct 86 ms 70972 KB Output is correct
14 Correct 92 ms 74860 KB Output is correct
15 Correct 78 ms 68236 KB Output is correct
16 Correct 173 ms 74284 KB Output is correct
17 Correct 162 ms 73964 KB Output is correct
18 Correct 214 ms 74832 KB Output is correct
19 Correct 216 ms 78772 KB Output is correct
20 Correct 199 ms 79368 KB Output is correct
21 Correct 176 ms 83960 KB Output is correct
22 Incorrect 191 ms 83704 KB Output isn't correct
23 Halted 0 ms 0 KB -