oj.uz

Submission #328051

# Submission time Handle Problem Language Result Execution time Memory
328051 2020-11-15T09:39:19 Z kshitij_sodani Swapping Cities (APIO20_swap) C++14
100 / 100
 868 ms 53968 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second

#include "swap.h"


int n,m;
int val=0;
vector<pair<int,pair<int,int>>> ed;
int par[100001];
int ss[100001];
int tt[100001];
int dd[100001];
multiset<int> xx[100001];
vector<int> comp[100001];
int ans[100001];

int find(int no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
void upd(int x,int y){
	int stt=0;

	if(ss[x]>tt[x]-1){
		stt=1;
	}
	auto ee=xx[x].end();
	ee--;
	if(*ee>=3){
		stt=1;
	}
	if(stt){
		for(auto j:comp[x]){
			if(ans[j]==-1){
				ans[j]=y;
			}
		}
	}
}
int par2[100001];
int find2(int no){
	if(par2[no]==no){
		return no;
	}
	par2[no]=find2(par2[no]);
	return par2[no];
}


vector<pair<int,int>> adj[100001];
int par3[100001][20];
int mi[100001][20];
int lev[100001];
void dfs(int no,int parr=-1,int levv=0){
	lev[no]=levv;
	par3[no][0]=parr;
//	cout<<no<<":"<<endl;
	for(auto j:adj[no]){

		if(j.a==parr){
			continue;
		}
	//	cout<<no<<":"<<j.a<<endl;
		mi[j.a][0]=j.b;
		dfs(j.a,no,levv+1);
	}
}

void init(int nn, int mm,vector<int> aa,vector<int> bb,vector<int> cc) {
	m=mm;
	n=nn;
	for(int i=0;i<m;i++){
		ed.pb({cc[i],{aa[i],bb[i]}});
	}
	sort(ed.begin(),ed.end());
	for(int i=0;i<n;i++){
		par[i]=i;
		ss[i]=0;
		dd[i]=0;
		xx[i].clear();
		tt[i]=1;
		xx[i].insert(0);
		ans[i]=-1;
		adj[i].clear();
		comp[i].pb(i);
	}
	for(auto j:ed){
		int x=find(j.b.a);
		int y=find(j.b.b);
		if(x==y){
			ss[x]+=1;
			auto jj=xx[x].find(dd[j.b.a]);
			xx[x].erase(jj);
			dd[j.b.a]+=1;
			xx[x].insert(dd[j.b.a]);

			jj=xx[x].find(dd[j.b.b]);
			xx[x].erase(jj);
			dd[j.b.b]+=1;
			xx[x].insert(dd[j.b.b]);
			if(ans[x]==-1){
				upd(x,j.a);
			}
		}
		else{
			if(xx[x].size()<xx[y].size()){
				swap(x,y);
			}
			par[y]=x;
			for(auto jj:xx[y]){
				xx[x].insert(jj);
			}
			for(auto jj:comp[y]){
				comp[x].pb(jj);
				if(ans[x]!=-1 and ans[jj]==-1){
					ans[jj]=j.a;
				}
			}
			comp[y].clear();
			xx[y].clear();
			ss[x]+=ss[y]+1;
			tt[x]+=tt[y];
			
			auto jj=xx[x].find(dd[j.b.a]);
			xx[x].erase(jj);
			dd[j.b.a]+=1;
			xx[x].insert(dd[j.b.a]);

			jj=xx[x].find(dd[j.b.b]);
			xx[x].erase(jj);
			dd[j.b.b]+=1;
			xx[x].insert(dd[j.b.b]);
			if(ans[x]==-1){
				upd(x,j.a);
			}
		}
	}
	/*for(int i=0;i<n;i++){
		cout<<ans[i]<<":";
	}
	cout<<endl;*/
	for(int i=0;i<n;i++){
		par2[i]=i;
	}
	for(auto j:ed){
		int xx=find2(j.b.b);
		int yy=find2(j.b.a);
		if(xx!=yy){
			par2[xx]=yy;
		//	cout<<xx<<"   "<<yy<<endl;
			adj[j.b.a].pb({j.b.b,j.a});
			adj[j.b.b].pb({j.b.a,j.a});
		//	cout<<j.b.a<<","<<j.b.b<<endl;
		}
	}
	dfs(0);
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(par3[i][j-1]==-1){
				par3[i][j]=-1;
				continue;
			}
			par3[i][j]=par3[par3[i][j-1]][j-1];
			if(par3[i][j]!=-1){
				mi[i][j]=max(mi[i][j-1],mi[par3[i][j-1]][j-1]);
			}
		}
	}
}

int getMinimumFuelCapacity(int ac, int bc) {
	int aa=ac;
	int bb=bc;
	if(ans[aa]==-1 or ans[bb]==-1){
		return -1;
	}
	int tot=max(ans[aa],ans[bb]);
	if(lev[aa]>lev[bb]){
		swap(aa,bb);
	}
	int dif=lev[bb]-lev[aa];
	for(int j=0;j<19;j++){
		if((1<<j)&dif){
			tot=max(tot,mi[bb][j]);
			bb=par3[bb][j];
		}
	}
	if(bb==aa){
		return tot;
	}
	for(int j=19;j>=0;j--){
		if(par3[aa][j]!=par3[bb][j]){
			tot=max(tot,max(mi[aa][j],mi[bb][j]));
			aa=par3[aa][j];
			bb=par3[bb][j];
		}
	}
	tot=max(tot,max(mi[aa][0],mi[bb][0]));



	return tot;
	//return ac;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 7 ms 9964 KB Output is correct
5 Correct 8 ms 10236 KB Output is correct
6 Correct 8 ms 10092 KB Output is correct
7 Correct 8 ms 10092 KB Output is correct
8 Correct 8 ms 10220 KB Output is correct
9 Correct 325 ms 41184 KB Output is correct
10 Correct 423 ms 49172 KB Output is correct
11 Correct 419 ms 48196 KB Output is correct
12 Correct 463 ms 50400 KB Output is correct
13 Correct 307 ms 50144 KB Output is correct
14 Correct 334 ms 40800 KB Output is correct
15 Correct 498 ms 51052 KB Output is correct
16 Correct 489 ms 48564 KB Output is correct
17 Correct 521 ms 53968 KB Output is correct
18 Correct 378 ms 50888 KB Output is correct
19 Correct 119 ms 20012 KB Output is correct
20 Correct 710 ms 51892 KB Output is correct
21 Correct 710 ms 49932 KB Output is correct
22 Correct 744 ms 53448 KB Output is correct
23 Correct 560 ms 51912 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 313 ms 45060 KB Output is correct
4 Correct 325 ms 46664 KB Output is correct
5 Correct 314 ms 45688 KB Output is correct
6 Correct 323 ms 46480 KB Output is correct
7 Correct 317 ms 46176 KB Output is correct
8 Correct 318 ms 44816 KB Output is correct
9 Correct 319 ms 45896 KB Output is correct
10 Correct 325 ms 44628 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 6 ms 9708 KB Output is correct
5 Correct 7 ms 9964 KB Output is correct
6 Correct 8 ms 10236 KB Output is correct
7 Correct 8 ms 10092 KB Output is correct
8 Correct 8 ms 10092 KB Output is correct
9 Correct 8 ms 10220 KB Output is correct
10 Correct 7 ms 10092 KB Output is correct
11 Correct 8 ms 10092 KB Output is correct
12 Correct 10 ms 10092 KB Output is correct
13 Correct 8 ms 10220 KB Output is correct
14 Correct 8 ms 10092 KB Output is correct
15 Correct 8 ms 10092 KB Output is correct
16 Correct 8 ms 10092 KB Output is correct
17 Correct 8 ms 10220 KB Output is correct
18 Correct 8 ms 10092 KB Output is correct
19 Correct 8 ms 9964 KB Output is correct
20 Correct 8 ms 10092 KB Output is correct
21 Correct 8 ms 10092 KB Output is correct
22 Correct 8 ms 9836 KB Output is correct
23 Correct 8 ms 9964 KB Output is correct
24 Correct 9 ms 10092 KB Output is correct
25 Correct 8 ms 10092 KB Output is correct
26 Correct 9 ms 10220 KB Output is correct
27 Correct 7 ms 10092 KB Output is correct
28 Correct 9 ms 10092 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 6 ms 9708 KB Output is correct
5 Correct 7 ms 9964 KB Output is correct
6 Correct 8 ms 10236 KB Output is correct
7 Correct 8 ms 10092 KB Output is correct
8 Correct 8 ms 10092 KB Output is correct
9 Correct 8 ms 10220 KB Output is correct
10 Correct 325 ms 41184 KB Output is correct
11 Correct 423 ms 49172 KB Output is correct
12 Correct 419 ms 48196 KB Output is correct
13 Correct 463 ms 50400 KB Output is correct
14 Correct 307 ms 50144 KB Output is correct
15 Correct 7 ms 10092 KB Output is correct
16 Correct 8 ms 10092 KB Output is correct
17 Correct 10 ms 10092 KB Output is correct
18 Correct 8 ms 10220 KB Output is correct
19 Correct 8 ms 10092 KB Output is correct
20 Correct 8 ms 10092 KB Output is correct
21 Correct 8 ms 10092 KB Output is correct
22 Correct 8 ms 10220 KB Output is correct
23 Correct 8 ms 10092 KB Output is correct
24 Correct 33 ms 14508 KB Output is correct
25 Correct 451 ms 50016 KB Output is correct
26 Correct 440 ms 47968 KB Output is correct
27 Correct 422 ms 46176 KB Output is correct
28 Correct 394 ms 45024 KB Output is correct
29 Correct 394 ms 44640 KB Output is correct
30 Correct 359 ms 41568 KB Output is correct
31 Correct 452 ms 48736 KB Output is correct
32 Correct 471 ms 49888 KB Output is correct
33 Correct 296 ms 48736 KB Output is correct
34 Correct 433 ms 45152 KB Output is correct
35 Correct 8 ms 9964 KB Output is correct
36 Correct 8 ms 10092 KB Output is correct
37 Correct 8 ms 10092 KB Output is correct
38 Correct 8 ms 9836 KB Output is correct
39 Correct 8 ms 9964 KB Output is correct
40 Correct 9 ms 10092 KB Output is correct
41 Correct 8 ms 10092 KB Output is correct
42 Correct 9 ms 10220 KB Output is correct
43 Correct 7 ms 10092 KB Output is correct
44 Correct 9 ms 10092 KB Output is correct
45 Correct 345 ms 39004 KB Output is correct
46 Correct 427 ms 47072 KB Output is correct
47 Correct 354 ms 44256 KB Output is correct
48 Correct 317 ms 43360 KB Output is correct
49 Correct 149 ms 16608 KB Output is correct
50 Correct 143 ms 16352 KB Output is correct
51 Correct 285 ms 33880 KB Output is correct
52 Correct 477 ms 48732 KB Output is correct
53 Correct 433 ms 47324 KB Output is correct
54 Correct 582 ms 52304 KB Output is correct
55 Correct 298 ms 49760 KB Output is correct
56 Correct 436 ms 46428 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 7 ms 9964 KB Output is correct
5 Correct 8 ms 10236 KB Output is correct
6 Correct 8 ms 10092 KB Output is correct
7 Correct 8 ms 10092 KB Output is correct
8 Correct 8 ms 10220 KB Output is correct
9 Correct 325 ms 41184 KB Output is correct
10 Correct 423 ms 49172 KB Output is correct
11 Correct 419 ms 48196 KB Output is correct
12 Correct 463 ms 50400 KB Output is correct
13 Correct 307 ms 50144 KB Output is correct
14 Correct 334 ms 40800 KB Output is correct
15 Correct 498 ms 51052 KB Output is correct
16 Correct 489 ms 48564 KB Output is correct
17 Correct 521 ms 53968 KB Output is correct
18 Correct 378 ms 50888 KB Output is correct
19 Correct 313 ms 45060 KB Output is correct
20 Correct 325 ms 46664 KB Output is correct
21 Correct 314 ms 45688 KB Output is correct
22 Correct 323 ms 46480 KB Output is correct
23 Correct 317 ms 46176 KB Output is correct
24 Correct 318 ms 44816 KB Output is correct
25 Correct 319 ms 45896 KB Output is correct
26 Correct 325 ms 44628 KB Output is correct
27 Correct 7 ms 10092 KB Output is correct
28 Correct 8 ms 10092 KB Output is correct
29 Correct 10 ms 10092 KB Output is correct
30 Correct 8 ms 10220 KB Output is correct
31 Correct 8 ms 10092 KB Output is correct
32 Correct 8 ms 10092 KB Output is correct
33 Correct 8 ms 10092 KB Output is correct
34 Correct 8 ms 10220 KB Output is correct
35 Correct 8 ms 10092 KB Output is correct
36 Correct 33 ms 14508 KB Output is correct
37 Correct 451 ms 50016 KB Output is correct
38 Correct 440 ms 47968 KB Output is correct
39 Correct 422 ms 46176 KB Output is correct
40 Correct 394 ms 45024 KB Output is correct
41 Correct 394 ms 44640 KB Output is correct
42 Correct 359 ms 41568 KB Output is correct
43 Correct 452 ms 48736 KB Output is correct
44 Correct 471 ms 49888 KB Output is correct
45 Correct 296 ms 48736 KB Output is correct
46 Correct 433 ms 45152 KB Output is correct
47 Correct 41 ms 14508 KB Output is correct
48 Correct 720 ms 51244 KB Output is correct
49 Correct 706 ms 49548 KB Output is correct
50 Correct 706 ms 48840 KB Output is correct
51 Correct 673 ms 48248 KB Output is correct
52 Correct 581 ms 45364 KB Output is correct
53 Correct 394 ms 36820 KB Output is correct
54 Correct 735 ms 51040 KB Output is correct
55 Correct 726 ms 52040 KB Output is correct
56 Correct 552 ms 52040 KB Output is correct
57 Correct 590 ms 48200 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 6 ms 9708 KB Output is correct
5 Correct 7 ms 9964 KB Output is correct
6 Correct 8 ms 10236 KB Output is correct
7 Correct 8 ms 10092 KB Output is correct
8 Correct 8 ms 10092 KB Output is correct
9 Correct 8 ms 10220 KB Output is correct
10 Correct 325 ms 41184 KB Output is correct
11 Correct 423 ms 49172 KB Output is correct
12 Correct 419 ms 48196 KB Output is correct
13 Correct 463 ms 50400 KB Output is correct
14 Correct 307 ms 50144 KB Output is correct
15 Correct 334 ms 40800 KB Output is correct
16 Correct 498 ms 51052 KB Output is correct
17 Correct 489 ms 48564 KB Output is correct
18 Correct 521 ms 53968 KB Output is correct
19 Correct 378 ms 50888 KB Output is correct
20 Correct 313 ms 45060 KB Output is correct
21 Correct 325 ms 46664 KB Output is correct
22 Correct 314 ms 45688 KB Output is correct
23 Correct 323 ms 46480 KB Output is correct
24 Correct 317 ms 46176 KB Output is correct
25 Correct 318 ms 44816 KB Output is correct
26 Correct 319 ms 45896 KB Output is correct
27 Correct 325 ms 44628 KB Output is correct
28 Correct 7 ms 10092 KB Output is correct
29 Correct 8 ms 10092 KB Output is correct
30 Correct 10 ms 10092 KB Output is correct
31 Correct 8 ms 10220 KB Output is correct
32 Correct 8 ms 10092 KB Output is correct
33 Correct 8 ms 10092 KB Output is correct
34 Correct 8 ms 10092 KB Output is correct
35 Correct 8 ms 10220 KB Output is correct
36 Correct 8 ms 10092 KB Output is correct
37 Correct 33 ms 14508 KB Output is correct
38 Correct 451 ms 50016 KB Output is correct
39 Correct 440 ms 47968 KB Output is correct
40 Correct 422 ms 46176 KB Output is correct
41 Correct 394 ms 45024 KB Output is correct
42 Correct 394 ms 44640 KB Output is correct
43 Correct 359 ms 41568 KB Output is correct
44 Correct 452 ms 48736 KB Output is correct
45 Correct 471 ms 49888 KB Output is correct
46 Correct 296 ms 48736 KB Output is correct
47 Correct 433 ms 45152 KB Output is correct
48 Correct 41 ms 14508 KB Output is correct
49 Correct 720 ms 51244 KB Output is correct
50 Correct 706 ms 49548 KB Output is correct
51 Correct 706 ms 48840 KB Output is correct
52 Correct 673 ms 48248 KB Output is correct
53 Correct 581 ms 45364 KB Output is correct
54 Correct 394 ms 36820 KB Output is correct
55 Correct 735 ms 51040 KB Output is correct
56 Correct 726 ms 52040 KB Output is correct
57 Correct 552 ms 52040 KB Output is correct
58 Correct 590 ms 48200 KB Output is correct
59 Correct 119 ms 20012 KB Output is correct
60 Correct 710 ms 51892 KB Output is correct
61 Correct 710 ms 49932 KB Output is correct
62 Correct 744 ms 53448 KB Output is correct
63 Correct 560 ms 51912 KB Output is correct
64 Correct 8 ms 9964 KB Output is correct
65 Correct 8 ms 10092 KB Output is correct
66 Correct 8 ms 10092 KB Output is correct
67 Correct 8 ms 9836 KB Output is correct
68 Correct 8 ms 9964 KB Output is correct
69 Correct 9 ms 10092 KB Output is correct
70 Correct 8 ms 10092 KB Output is correct
71 Correct 9 ms 10220 KB Output is correct
72 Correct 7 ms 10092 KB Output is correct
73 Correct 9 ms 10092 KB Output is correct
74 Correct 345 ms 39004 KB Output is correct
75 Correct 427 ms 47072 KB Output is correct
76 Correct 354 ms 44256 KB Output is correct
77 Correct 317 ms 43360 KB Output is correct
78 Correct 149 ms 16608 KB Output is correct
79 Correct 143 ms 16352 KB Output is correct
80 Correct 285 ms 33880 KB Output is correct
81 Correct 477 ms 48732 KB Output is correct
82 Correct 433 ms 47324 KB Output is correct
83 Correct 582 ms 52304 KB Output is correct
84 Correct 298 ms 49760 KB Output is correct
85 Correct 436 ms 46428 KB Output is correct
86 Correct 135 ms 21656 KB Output is correct
87 Correct 689 ms 48892 KB Output is correct
88 Correct 696 ms 49352 KB Output is correct
89 Correct 454 ms 44180 KB Output is correct
90 Correct 263 ms 18400 KB Output is correct
91 Correct 289 ms 20988 KB Output is correct
92 Correct 435 ms 36848 KB Output is correct
93 Correct 739 ms 51256 KB Output is correct
94 Correct 639 ms 49628 KB Output is correct
95 Correct 868 ms 53852 KB Output is correct
96 Correct 573 ms 50268 KB Output is correct
97 Correct 572 ms 48128 KB Output is correct