oj.uz

Submission #897116

# Submission time Handle Problem Language Result Execution time Memory
897116 2024-01-02T14:58:10 Z LCJLY Swapping Cities (APIO20_swap) C++14
0 / 100
 625 ms 128084 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;
		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 101976 KB Output is correct
2 Correct 15 ms 101980 KB Output is correct
3 Correct 13 ms 102076 KB Output is correct
4 Correct 14 ms 101980 KB Output is correct
5 Correct 14 ms 102236 KB Output is correct
6 Correct 14 ms 102156 KB Output is correct
7 Correct 14 ms 102208 KB Output is correct
8 Correct 14 ms 102272 KB Output is correct
9 Correct 76 ms 116560 KB Output is correct
10 Correct 109 ms 119412 KB Output is correct
11 Correct 97 ms 119316 KB Output is correct
12 Correct 101 ms 120400 KB Output is correct
13 Correct 110 ms 122848 KB Output is correct
14 Correct 110 ms 116864 KB Output is correct
15 Correct 487 ms 121044 KB Output is correct
16 Correct 497 ms 120660 KB Output is correct
17 Correct 493 ms 121608 KB Output is correct
18 Correct 582 ms 124496 KB Output is correct
19 Incorrect 118 ms 109888 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 101976 KB Output is correct
2 Correct 15 ms 101980 KB Output is correct
3 Correct 598 ms 126992 KB Output is correct
4 Correct 532 ms 128084 KB Output is correct
5 Incorrect 625 ms 127376 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 101976 KB Output is correct
2 Correct 15 ms 101980 KB Output is correct
3 Correct 13 ms 102076 KB Output is correct
4 Correct 14 ms 101980 KB Output is correct
5 Correct 14 ms 102236 KB Output is correct
6 Correct 14 ms 102156 KB Output is correct
7 Correct 14 ms 102208 KB Output is correct
8 Correct 14 ms 102272 KB Output is correct
9 Incorrect 13 ms 102120 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 102120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 101976 KB Output is correct
2 Correct 15 ms 101980 KB Output is correct
3 Correct 13 ms 102076 KB Output is correct
4 Correct 14 ms 101980 KB Output is correct
5 Correct 14 ms 102236 KB Output is correct
6 Correct 14 ms 102156 KB Output is correct
7 Correct 14 ms 102208 KB Output is correct
8 Correct 14 ms 102272 KB Output is correct
9 Correct 76 ms 116560 KB Output is correct
10 Correct 109 ms 119412 KB Output is correct
11 Correct 97 ms 119316 KB Output is correct
12 Correct 101 ms 120400 KB Output is correct
13 Correct 110 ms 122848 KB Output is correct
14 Correct 110 ms 116864 KB Output is correct
15 Correct 487 ms 121044 KB Output is correct
16 Correct 497 ms 120660 KB Output is correct
17 Correct 493 ms 121608 KB Output is correct
18 Correct 582 ms 124496 KB Output is correct
19 Correct 598 ms 126992 KB Output is correct
20 Correct 532 ms 128084 KB Output is correct
21 Incorrect 625 ms 127376 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 102120 KB Output isn't correct
2 Halted 0 ms 0 KB -