oj.uz

Submission #897119

# Submission time Handle Problem Language Result Execution time Memory
897119 2024-01-02T15:01:31 Z LCJLY Swapping Cities (APIO20_swap) C++14
0 / 100
 654 ms 127840 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;
#define int long long

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(int32_t n, int32_t m, vector<int32_t> u, vector<int32_t> v, vector<int32_t> 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]=true;
			cost[l]=hold;
		}
		if(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;
}

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 102120 KB Output is correct
2 Correct 14 ms 101980 KB Output is correct
3 Correct 15 ms 101980 KB Output is correct
4 Correct 14 ms 101980 KB Output is correct
5 Correct 14 ms 102236 KB Output is correct
6 Correct 16 ms 102236 KB Output is correct
7 Correct 14 ms 102204 KB Output is correct
8 Correct 16 ms 102200 KB Output is correct
9 Correct 77 ms 116536 KB Output is correct
10 Correct 97 ms 119544 KB Output is correct
11 Correct 95 ms 119120 KB Output is correct
12 Correct 115 ms 120032 KB Output is correct
13 Correct 105 ms 122708 KB Output is correct
14 Correct 108 ms 116872 KB Output is correct
15 Correct 571 ms 121044 KB Output is correct
16 Correct 447 ms 120656 KB Output is correct
17 Correct 454 ms 121684 KB Output is correct
18 Correct 588 ms 124496 KB Output is correct
19 Incorrect 112 ms 109916 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 102120 KB Output is correct
2 Correct 14 ms 101980 KB Output is correct
3 Correct 566 ms 126992 KB Output is correct
4 Correct 549 ms 127840 KB Output is correct
5 Incorrect 654 ms 127492 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 102120 KB Output is correct
2 Correct 14 ms 101980 KB Output is correct
3 Correct 15 ms 101980 KB Output is correct
4 Correct 14 ms 101980 KB Output is correct
5 Correct 14 ms 102236 KB Output is correct
6 Correct 16 ms 102236 KB Output is correct
7 Correct 14 ms 102204 KB Output is correct
8 Correct 16 ms 102200 KB Output is correct
9 Correct 14 ms 101976 KB Output is correct
10 Correct 14 ms 102236 KB Output is correct
11 Correct 15 ms 102176 KB Output is correct
12 Correct 14 ms 102236 KB Output is correct
13 Correct 14 ms 102236 KB Output is correct
14 Correct 14 ms 102188 KB Output is correct
15 Incorrect 14 ms 102236 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 101976 KB Output is correct
2 Correct 14 ms 102120 KB Output is correct
3 Correct 14 ms 101980 KB Output is correct
4 Correct 15 ms 101980 KB Output is correct
5 Correct 14 ms 101980 KB Output is correct
6 Correct 14 ms 102236 KB Output is correct
7 Correct 16 ms 102236 KB Output is correct
8 Correct 14 ms 102204 KB Output is correct
9 Correct 16 ms 102200 KB Output is correct
10 Correct 77 ms 116536 KB Output is correct
11 Correct 97 ms 119544 KB Output is correct
12 Correct 95 ms 119120 KB Output is correct
13 Correct 115 ms 120032 KB Output is correct
14 Correct 105 ms 122708 KB Output is correct
15 Correct 14 ms 102236 KB Output is correct
16 Correct 15 ms 102176 KB Output is correct
17 Correct 14 ms 102236 KB Output is correct
18 Correct 14 ms 102236 KB Output is correct
19 Correct 14 ms 102188 KB Output is correct
20 Incorrect 14 ms 102236 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 102120 KB Output is correct
2 Correct 14 ms 101980 KB Output is correct
3 Correct 15 ms 101980 KB Output is correct
4 Correct 14 ms 101980 KB Output is correct
5 Correct 14 ms 102236 KB Output is correct
6 Correct 16 ms 102236 KB Output is correct
7 Correct 14 ms 102204 KB Output is correct
8 Correct 16 ms 102200 KB Output is correct
9 Correct 77 ms 116536 KB Output is correct
10 Correct 97 ms 119544 KB Output is correct
11 Correct 95 ms 119120 KB Output is correct
12 Correct 115 ms 120032 KB Output is correct
13 Correct 105 ms 122708 KB Output is correct
14 Correct 108 ms 116872 KB Output is correct
15 Correct 571 ms 121044 KB Output is correct
16 Correct 447 ms 120656 KB Output is correct
17 Correct 454 ms 121684 KB Output is correct
18 Correct 588 ms 124496 KB Output is correct
19 Correct 566 ms 126992 KB Output is correct
20 Correct 549 ms 127840 KB Output is correct
21 Incorrect 654 ms 127492 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 101976 KB Output is correct
2 Correct 14 ms 102120 KB Output is correct
3 Correct 14 ms 101980 KB Output is correct
4 Correct 15 ms 101980 KB Output is correct
5 Correct 14 ms 101980 KB Output is correct
6 Correct 14 ms 102236 KB Output is correct
7 Correct 16 ms 102236 KB Output is correct
8 Correct 14 ms 102204 KB Output is correct
9 Correct 16 ms 102200 KB Output is correct
10 Correct 77 ms 116536 KB Output is correct
11 Correct 97 ms 119544 KB Output is correct
12 Correct 95 ms 119120 KB Output is correct
13 Correct 115 ms 120032 KB Output is correct
14 Correct 105 ms 122708 KB Output is correct
15 Correct 108 ms 116872 KB Output is correct
16 Correct 571 ms 121044 KB Output is correct
17 Correct 447 ms 120656 KB Output is correct
18 Correct 454 ms 121684 KB Output is correct
19 Correct 588 ms 124496 KB Output is correct
20 Correct 566 ms 126992 KB Output is correct
21 Correct 549 ms 127840 KB Output is correct
22 Incorrect 654 ms 127492 KB Output isn't correct
23 Halted 0 ms 0 KB -