oj.uz

Submission #553245

# Submission time Handle Problem Language Result Execution time Memory
553245 2022-04-25T08:24:17 Z FatihSolak Swapping Cities (APIO20_swap) C++17
100 / 100
 579 ms 47804 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define N 100005
#define M 200005
using namespace std;
vector<pair<int,int>> par[N];
int sz[N];
vector<int> group[N];
vector<pair<int,pair<int,int>>> groupval[N]; 
int ans[M];
int edgecnt;
void init(int n, int m,vector<int> u, vector<int> v, vector<int> w){
	edgecnt = m;
	vector<pair<int,int>> compress;
	for(int i = 0;i<n;i++){
		par[i].push_back({-1,i});
		group[i].push_back(i);
		groupval[i].push_back({-1,{-1,0}});
	}
	for(int i = 0;i<m;i++){
		compress.push_back({w[i],i});
	}
	sort(compress.begin(),compress.end());
	for(int i = 0;i<m;i++){
		ans[i] = compress[i].first;
		int x = compress[i].second;
		if(  group[par[u[x]].back().second].size() > group[par[v[x]].back().second].size()){
			swap(u[x],v[x]);
		}
		sz[u[x]]++;
		sz[v[x]]++;
		int tmp = par[u[x]].back().second;
		//cout << u[x] << " " << v[x] << endl;
		//cout << par[u[x]].back().second << "  a " << par[v[x]].back().second << endl;
		if(par[u[x]].back().second ==  par[v[x]].back().second){
			pair<int,pair<int,int>> nw = {i,{groupval[par[v[x]].back().second].back().second.first + 1,max({groupval[par[v[x]].back().second].back().second.second, groupval[tmp].back().second.second,sz[u[x]],sz[v[x]]})}};
			//cout << nw.second.first << " b " << nw.second.second << endl;
			groupval[par[v[x]].back().second].push_back(nw);
			continue;
		}
		for(auto c:group[tmp]){
			par[c].push_back({i,par[v[x]].back().second});
			group[par[v[x]].back().second].push_back(c);
		}
		pair<int,pair<int,int>> nw = {i,{groupval[par[v[x]].back().second].back().second.first + groupval[tmp].back().second.first + 1,max({groupval[par[v[x]].back().second].back().second.second, groupval[tmp].back().second.second,sz[u[x]],sz[v[x]]})}};
		//cout << nw.second.first << " b " << nw.second.second << endl;
		group[tmp].clear();
		groupval[par[v[x]].back().second].push_back(nw);
		//cout << "hey" << endl;
		//return;
	}
}
bool ck(int x,int y,int val){
	int groupx = prev(lower_bound(par[x].begin(),par[x].end(),make_pair(val+1,-1)))->second;
	int groupy = prev(lower_bound(par[y].begin(),par[y].end(),make_pair(val+1,-1)))->second;
	if(groupx != groupy)
		return 0;
	pair<int,int> tmp = prev(lower_bound(groupval[groupx].begin(),groupval[groupx].end(),make_pair(val+1,make_pair(-1,-1))))->second;
	return (tmp.first > -1) || (tmp.second > 2);
}
int getMinimumFuelCapacity(int x, int y) {
	int l = 0,r = edgecnt;
	while(l < r){
		int m = (l + r)/2;
		if(ck(x,y,m)){
			r = m;
		}
		else l = m+1;
	}
	if(r == edgecnt)return -1;
	return ans[l];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7296 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7356 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 5 ms 7496 KB Output is correct
7 Correct 6 ms 7492 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 186 ms 29580 KB Output is correct
10 Correct 196 ms 34048 KB Output is correct
11 Correct 215 ms 33548 KB Output is correct
12 Correct 276 ms 35096 KB Output is correct
13 Correct 116 ms 26932 KB Output is correct
14 Correct 169 ms 29624 KB Output is correct
15 Correct 426 ms 38432 KB Output is correct
16 Correct 393 ms 37512 KB Output is correct
17 Correct 424 ms 39324 KB Output is correct
18 Correct 311 ms 30780 KB Output is correct
19 Correct 130 ms 16600 KB Output is correct
20 Correct 393 ms 38860 KB Output is correct
21 Correct 392 ms 38248 KB Output is correct
22 Correct 403 ms 40096 KB Output is correct
23 Correct 373 ms 31716 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7296 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 371 ms 27832 KB Output is correct
4 Correct 373 ms 28444 KB Output is correct
5 Correct 447 ms 28388 KB Output is correct
6 Correct 344 ms 28328 KB Output is correct
7 Correct 449 ms 28564 KB Output is correct
8 Correct 349 ms 27800 KB Output is correct
9 Correct 368 ms 28236 KB Output is correct
10 Correct 411 ms 27852 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7296 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7356 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 5 ms 7496 KB Output is correct
7 Correct 6 ms 7492 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 5 ms 7508 KB Output is correct
11 Correct 5 ms 7508 KB Output is correct
12 Correct 5 ms 7492 KB Output is correct
13 Correct 5 ms 7508 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7508 KB Output is correct
16 Correct 5 ms 7500 KB Output is correct
17 Correct 5 ms 7508 KB Output is correct
18 Correct 5 ms 7496 KB Output is correct
19 Correct 5 ms 7496 KB Output is correct
20 Correct 6 ms 7496 KB Output is correct
21 Correct 5 ms 7508 KB Output is correct
22 Correct 5 ms 7496 KB Output is correct
23 Correct 5 ms 7496 KB Output is correct
24 Correct 6 ms 7636 KB Output is correct
25 Correct 5 ms 7536 KB Output is correct
26 Correct 5 ms 7636 KB Output is correct
27 Correct 5 ms 7508 KB Output is correct
28 Correct 5 ms 7624 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 5 ms 7296 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7356 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7508 KB Output is correct
7 Correct 5 ms 7496 KB Output is correct
8 Correct 6 ms 7492 KB Output is correct
9 Correct 5 ms 7508 KB Output is correct
10 Correct 186 ms 29580 KB Output is correct
11 Correct 196 ms 34048 KB Output is correct
12 Correct 215 ms 33548 KB Output is correct
13 Correct 276 ms 35096 KB Output is correct
14 Correct 116 ms 26932 KB Output is correct
15 Correct 5 ms 7508 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct
17 Correct 5 ms 7492 KB Output is correct
18 Correct 5 ms 7508 KB Output is correct
19 Correct 5 ms 7500 KB Output is correct
20 Correct 5 ms 7508 KB Output is correct
21 Correct 5 ms 7500 KB Output is correct
22 Correct 5 ms 7508 KB Output is correct
23 Correct 5 ms 7496 KB Output is correct
24 Correct 5 ms 7496 KB Output is correct
25 Correct 6 ms 7496 KB Output is correct
26 Correct 5 ms 7508 KB Output is correct
27 Correct 5 ms 7496 KB Output is correct
28 Correct 5 ms 7496 KB Output is correct
29 Correct 6 ms 7636 KB Output is correct
30 Correct 5 ms 7536 KB Output is correct
31 Correct 5 ms 7636 KB Output is correct
32 Correct 5 ms 7508 KB Output is correct
33 Correct 5 ms 7624 KB Output is correct
34 Correct 17 ms 10580 KB Output is correct
35 Correct 261 ms 34668 KB Output is correct
36 Correct 219 ms 34492 KB Output is correct
37 Correct 209 ms 34076 KB Output is correct
38 Correct 234 ms 33036 KB Output is correct
39 Correct 194 ms 32536 KB Output is correct
40 Correct 158 ms 30156 KB Output is correct
41 Correct 229 ms 35616 KB Output is correct
42 Correct 259 ms 35320 KB Output is correct
43 Correct 105 ms 25816 KB Output is correct
44 Correct 188 ms 32812 KB Output is correct
45 Correct 149 ms 29368 KB Output is correct
46 Correct 249 ms 34472 KB Output is correct
47 Correct 179 ms 30832 KB Output is correct
48 Correct 148 ms 28296 KB Output is correct
49 Correct 73 ms 20320 KB Output is correct
50 Correct 67 ms 16960 KB Output is correct
51 Correct 154 ms 25728 KB Output is correct
52 Correct 243 ms 38844 KB Output is correct
53 Correct 251 ms 35004 KB Output is correct
54 Correct 292 ms 43444 KB Output is correct
55 Correct 115 ms 26200 KB Output is correct
56 Correct 236 ms 33916 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7296 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7356 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 5 ms 7496 KB Output is correct
7 Correct 6 ms 7492 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 186 ms 29580 KB Output is correct
10 Correct 196 ms 34048 KB Output is correct
11 Correct 215 ms 33548 KB Output is correct
12 Correct 276 ms 35096 KB Output is correct
13 Correct 116 ms 26932 KB Output is correct
14 Correct 169 ms 29624 KB Output is correct
15 Correct 426 ms 38432 KB Output is correct
16 Correct 393 ms 37512 KB Output is correct
17 Correct 424 ms 39324 KB Output is correct
18 Correct 311 ms 30780 KB Output is correct
19 Correct 371 ms 27832 KB Output is correct
20 Correct 373 ms 28444 KB Output is correct
21 Correct 447 ms 28388 KB Output is correct
22 Correct 344 ms 28328 KB Output is correct
23 Correct 449 ms 28564 KB Output is correct
24 Correct 349 ms 27800 KB Output is correct
25 Correct 368 ms 28236 KB Output is correct
26 Correct 411 ms 27852 KB Output is correct
27 Correct 5 ms 7508 KB Output is correct
28 Correct 5 ms 7508 KB Output is correct
29 Correct 5 ms 7492 KB Output is correct
30 Correct 5 ms 7508 KB Output is correct
31 Correct 5 ms 7500 KB Output is correct
32 Correct 5 ms 7508 KB Output is correct
33 Correct 5 ms 7500 KB Output is correct
34 Correct 5 ms 7508 KB Output is correct
35 Correct 5 ms 7496 KB Output is correct
36 Correct 17 ms 10580 KB Output is correct
37 Correct 261 ms 34668 KB Output is correct
38 Correct 219 ms 34492 KB Output is correct
39 Correct 209 ms 34076 KB Output is correct
40 Correct 234 ms 33036 KB Output is correct
41 Correct 194 ms 32536 KB Output is correct
42 Correct 158 ms 30156 KB Output is correct
43 Correct 229 ms 35616 KB Output is correct
44 Correct 259 ms 35320 KB Output is correct
45 Correct 105 ms 25816 KB Output is correct
46 Correct 188 ms 32812 KB Output is correct
47 Correct 37 ms 10832 KB Output is correct
48 Correct 384 ms 38992 KB Output is correct
49 Correct 441 ms 38264 KB Output is correct
50 Correct 388 ms 38096 KB Output is correct
51 Correct 403 ms 37556 KB Output is correct
52 Correct 395 ms 35532 KB Output is correct
53 Correct 294 ms 29464 KB Output is correct
54 Correct 394 ms 39728 KB Output is correct
55 Correct 403 ms 39568 KB Output is correct
56 Correct 355 ms 30764 KB Output is correct
57 Correct 392 ms 37056 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 5 ms 7296 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7356 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7508 KB Output is correct
7 Correct 5 ms 7496 KB Output is correct
8 Correct 6 ms 7492 KB Output is correct
9 Correct 5 ms 7508 KB Output is correct
10 Correct 186 ms 29580 KB Output is correct
11 Correct 196 ms 34048 KB Output is correct
12 Correct 215 ms 33548 KB Output is correct
13 Correct 276 ms 35096 KB Output is correct
14 Correct 116 ms 26932 KB Output is correct
15 Correct 169 ms 29624 KB Output is correct
16 Correct 426 ms 38432 KB Output is correct
17 Correct 393 ms 37512 KB Output is correct
18 Correct 424 ms 39324 KB Output is correct
19 Correct 311 ms 30780 KB Output is correct
20 Correct 371 ms 27832 KB Output is correct
21 Correct 373 ms 28444 KB Output is correct
22 Correct 447 ms 28388 KB Output is correct
23 Correct 344 ms 28328 KB Output is correct
24 Correct 449 ms 28564 KB Output is correct
25 Correct 349 ms 27800 KB Output is correct
26 Correct 368 ms 28236 KB Output is correct
27 Correct 411 ms 27852 KB Output is correct
28 Correct 5 ms 7508 KB Output is correct
29 Correct 5 ms 7508 KB Output is correct
30 Correct 5 ms 7492 KB Output is correct
31 Correct 5 ms 7508 KB Output is correct
32 Correct 5 ms 7500 KB Output is correct
33 Correct 5 ms 7508 KB Output is correct
34 Correct 5 ms 7500 KB Output is correct
35 Correct 5 ms 7508 KB Output is correct
36 Correct 5 ms 7496 KB Output is correct
37 Correct 17 ms 10580 KB Output is correct
38 Correct 261 ms 34668 KB Output is correct
39 Correct 219 ms 34492 KB Output is correct
40 Correct 209 ms 34076 KB Output is correct
41 Correct 234 ms 33036 KB Output is correct
42 Correct 194 ms 32536 KB Output is correct
43 Correct 158 ms 30156 KB Output is correct
44 Correct 229 ms 35616 KB Output is correct
45 Correct 259 ms 35320 KB Output is correct
46 Correct 105 ms 25816 KB Output is correct
47 Correct 188 ms 32812 KB Output is correct
48 Correct 37 ms 10832 KB Output is correct
49 Correct 384 ms 38992 KB Output is correct
50 Correct 441 ms 38264 KB Output is correct
51 Correct 388 ms 38096 KB Output is correct
52 Correct 403 ms 37556 KB Output is correct
53 Correct 395 ms 35532 KB Output is correct
54 Correct 294 ms 29464 KB Output is correct
55 Correct 394 ms 39728 KB Output is correct
56 Correct 403 ms 39568 KB Output is correct
57 Correct 355 ms 30764 KB Output is correct
58 Correct 392 ms 37056 KB Output is correct
59 Correct 130 ms 16600 KB Output is correct
60 Correct 393 ms 38860 KB Output is correct
61 Correct 392 ms 38248 KB Output is correct
62 Correct 403 ms 40096 KB Output is correct
63 Correct 373 ms 31716 KB Output is correct
64 Correct 5 ms 7496 KB Output is correct
65 Correct 6 ms 7496 KB Output is correct
66 Correct 5 ms 7508 KB Output is correct
67 Correct 5 ms 7496 KB Output is correct
68 Correct 5 ms 7496 KB Output is correct
69 Correct 6 ms 7636 KB Output is correct
70 Correct 5 ms 7536 KB Output is correct
71 Correct 5 ms 7636 KB Output is correct
72 Correct 5 ms 7508 KB Output is correct
73 Correct 5 ms 7624 KB Output is correct
74 Correct 149 ms 29368 KB Output is correct
75 Correct 249 ms 34472 KB Output is correct
76 Correct 179 ms 30832 KB Output is correct
77 Correct 148 ms 28296 KB Output is correct
78 Correct 73 ms 20320 KB Output is correct
79 Correct 67 ms 16960 KB Output is correct
80 Correct 154 ms 25728 KB Output is correct
81 Correct 243 ms 38844 KB Output is correct
82 Correct 251 ms 35004 KB Output is correct
83 Correct 292 ms 43444 KB Output is correct
84 Correct 115 ms 26200 KB Output is correct
85 Correct 236 ms 33916 KB Output is correct
86 Correct 142 ms 16104 KB Output is correct
87 Correct 379 ms 37888 KB Output is correct
88 Correct 478 ms 37976 KB Output is correct
89 Correct 433 ms 31184 KB Output is correct
90 Correct 342 ms 24224 KB Output is correct
91 Correct 381 ms 25200 KB Output is correct
92 Correct 417 ms 29240 KB Output is correct
93 Correct 534 ms 41776 KB Output is correct
94 Correct 579 ms 39356 KB Output is correct
95 Correct 470 ms 47804 KB Output is correct
96 Correct 328 ms 30632 KB Output is correct
97 Correct 482 ms 35008 KB Output is correct