oj.uz

Submission #897099

# Submission time Handle Problem Language Result Execution time Memory
897099 2024-01-02T14:37:45 Z LCJLY Swapping Cities (APIO20_swap) C++14
0 / 100
 266 ms 82096 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];
long long 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){
	assert(x!=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 9 ms 56920 KB Output is correct
2 Correct 9 ms 56924 KB Output is correct
3 Correct 8 ms 57088 KB Output is correct
4 Correct 9 ms 56924 KB Output is correct
5 Correct 9 ms 57180 KB Output is correct
6 Correct 9 ms 57192 KB Output is correct
7 Correct 9 ms 59228 KB Output is correct
8 Correct 9 ms 59252 KB Output is correct
9 Correct 70 ms 68180 KB Output is correct
10 Correct 89 ms 70224 KB Output is correct
11 Correct 77 ms 70228 KB Output is correct
12 Correct 91 ms 70756 KB Output is correct
13 Correct 89 ms 74820 KB Output is correct
14 Correct 83 ms 68324 KB Output is correct
15 Correct 157 ms 72000 KB Output is correct
16 Correct 174 ms 71760 KB Output is correct
17 Correct 236 ms 72308 KB Output is correct
18 Correct 204 ms 76368 KB Output is correct
19 Incorrect 81 ms 64452 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 56920 KB Output is correct
2 Correct 9 ms 56924 KB Output is correct
3 Correct 173 ms 81244 KB Output is correct
4 Correct 199 ms 82096 KB Output is correct
5 Incorrect 266 ms 81668 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 56920 KB Output is correct
2 Correct 9 ms 56924 KB Output is correct
3 Correct 8 ms 57088 KB Output is correct
4 Correct 9 ms 56924 KB Output is correct
5 Correct 9 ms 57180 KB Output is correct
6 Correct 9 ms 57192 KB Output is correct
7 Correct 9 ms 59228 KB Output is correct
8 Correct 9 ms 59252 KB Output is correct
9 Correct 8 ms 56924 KB Output is correct
10 Correct 10 ms 59228 KB Output is correct
11 Correct 9 ms 59092 KB Output is correct
12 Correct 9 ms 59228 KB Output is correct
13 Correct 9 ms 57180 KB Output is correct
14 Correct 9 ms 57180 KB Output is correct
15 Incorrect 9 ms 59232 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 56924 KB Output is correct
2 Correct 9 ms 56920 KB Output is correct
3 Correct 9 ms 56924 KB Output is correct
4 Correct 8 ms 57088 KB Output is correct
5 Correct 9 ms 56924 KB Output is correct
6 Correct 9 ms 57180 KB Output is correct
7 Correct 9 ms 57192 KB Output is correct
8 Correct 9 ms 59228 KB Output is correct
9 Correct 9 ms 59252 KB Output is correct
10 Correct 70 ms 68180 KB Output is correct
11 Correct 89 ms 70224 KB Output is correct
12 Correct 77 ms 70228 KB Output is correct
13 Correct 91 ms 70756 KB Output is correct
14 Correct 89 ms 74820 KB Output is correct
15 Correct 10 ms 59228 KB Output is correct
16 Correct 9 ms 59092 KB Output is correct
17 Correct 9 ms 59228 KB Output is correct
18 Correct 9 ms 57180 KB Output is correct
19 Correct 9 ms 57180 KB Output is correct
20 Incorrect 9 ms 59232 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 56920 KB Output is correct
2 Correct 9 ms 56924 KB Output is correct
3 Correct 8 ms 57088 KB Output is correct
4 Correct 9 ms 56924 KB Output is correct
5 Correct 9 ms 57180 KB Output is correct
6 Correct 9 ms 57192 KB Output is correct
7 Correct 9 ms 59228 KB Output is correct
8 Correct 9 ms 59252 KB Output is correct
9 Correct 70 ms 68180 KB Output is correct
10 Correct 89 ms 70224 KB Output is correct
11 Correct 77 ms 70228 KB Output is correct
12 Correct 91 ms 70756 KB Output is correct
13 Correct 89 ms 74820 KB Output is correct
14 Correct 83 ms 68324 KB Output is correct
15 Correct 157 ms 72000 KB Output is correct
16 Correct 174 ms 71760 KB Output is correct
17 Correct 236 ms 72308 KB Output is correct
18 Correct 204 ms 76368 KB Output is correct
19 Correct 173 ms 81244 KB Output is correct
20 Correct 199 ms 82096 KB Output is correct
21 Incorrect 266 ms 81668 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 56924 KB Output is correct
2 Correct 9 ms 56920 KB Output is correct
3 Correct 9 ms 56924 KB Output is correct
4 Correct 8 ms 57088 KB Output is correct
5 Correct 9 ms 56924 KB Output is correct
6 Correct 9 ms 57180 KB Output is correct
7 Correct 9 ms 57192 KB Output is correct
8 Correct 9 ms 59228 KB Output is correct
9 Correct 9 ms 59252 KB Output is correct
10 Correct 70 ms 68180 KB Output is correct
11 Correct 89 ms 70224 KB Output is correct
12 Correct 77 ms 70228 KB Output is correct
13 Correct 91 ms 70756 KB Output is correct
14 Correct 89 ms 74820 KB Output is correct
15 Correct 83 ms 68324 KB Output is correct
16 Correct 157 ms 72000 KB Output is correct
17 Correct 174 ms 71760 KB Output is correct
18 Correct 236 ms 72308 KB Output is correct
19 Correct 204 ms 76368 KB Output is correct
20 Correct 173 ms 81244 KB Output is correct
21 Correct 199 ms 82096 KB Output is correct
22 Incorrect 266 ms 81668 KB Output isn't correct
23 Halted 0 ms 0 KB -