oj.uz

Submission #966049

# Submission time Handle Problem Language Result Execution time Memory
966049 2024-04-19T10:00:17 Z pcc Swapping Cities (APIO20_swap) C++17
100 / 100
 312 ms 100768 KB 
#include "swap.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 4e5+10;

vector<int> v;
int N,M;
vector<pair<int,pii>> edges;
vector<int> tree[mxn];
int dp[mxn][20];
int par[mxn][20];
pii val[mxn];
int dep[mxn];
int rt;

namespace INIT{
	int deg[mxn];
	struct DSU{
		bool chn[mxn];
		int cnt[mxn][2];
		int head[mxn];
		int sz[mxn],dsu[mxn];
		void init(int n){
			for(int i = 0;i<=n;i++){
				dsu[i] = i,sz[i] = 1;
				chn[i] = true;
				cnt[i][0] = 1;
				head[i] = i;
			}
		}
		int root(int k){
			return k == dsu[k]?k:dsu[k] = root(dsu[k]);
		}

		void upd(int now){
			int r = root(now);
			if(deg[now]<2){
				cnt[r][deg[now]]--;
				deg[now]++;
				if(deg[now]<2)cnt[r][deg[now]]++;
			}
			else{
				chn[r] = false;
			}
			return;
		}

		void check(int r){
			r = root(r);
			if(cnt[r][1]>2)chn[r] = false;
			return;
		}

		void onion(int a,int b){
			int ra = root(a),rb = root(b);
			if(ra == rb){
				chn[ra] = false;
				return;
			}
			if(sz[ra]<sz[rb]){
				swap(a,b);
				swap(ra,rb);
			}
			if(!chn[ra]||!chn[rb])chn[ra] = false;
			sz[ra] += sz[rb];
			dsu[rb] = ra;
			for(int i = 0;i<2;i++)cnt[ra][i] += cnt[rb][i];
			upd(a);
			upd(b);
			check(ra);
			return;
		}
	};

	DSU dsu;

	void dfs(int now){
		dp[now][0] = val[now].sc;
		for(int i = 1;i<20;i++){
			par[now][i] = par[par[now][i-1]][i-1];
			dp[now][i] = dp[par[now][i-1]][i-1];
		}
		for(auto nxt:tree[now]){
			//cout<<now<<","<<nxt<<endl;
			dep[nxt] = dep[now]+1;
			par[nxt][0] = now;
			dfs(nxt);
		}
		return;
	}

	void GO(){
		dsu.init(N-1);
		for(int i = N;i<mxn;i++)dsu.dsu[i] = i,dsu.sz[i] = 1;
		for(int i = 0;i<N;i++)val[i].sc = 1;
		int pt = N-1;
		for(int i = 0;i<edges.size();i++){
			auto [a,b] = edges[i].sc;
			int ra = dsu.root(a),rb = dsu.root(b);
			int w = edges[i].fs;
			pt++;
			val[pt].fs = w;
			tree[pt].push_back(dsu.head[ra]);
			if(ra != rb)tree[pt].push_back(dsu.head[rb]);
			dsu.onion(a,b);
			dsu.head[dsu.root(a)] = pt;
			//cout<<pt<<' '<<dsu.root(a)<<':'<<dsu.chn[dsu.root(a)]<<endl;
			val[pt].sc = dsu.chn[dsu.root(a)];
		}
		rt = pt;
		par[rt][0] = rt;
		//for(int i = 0;i<=rt;i++)cout<<i<<":"<<val[i].sc<<endl;
		dfs(rt);
		return;
	}
}

void init(int NN, int MM,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	N = NN,M = MM;
	for(int i = 0;i<M;i++){
		edges.push_back(make_pair(W[i],pii(U[i],V[i])));
	}
	sort(edges.begin(),edges.end());
	INIT::GO();
}

int getans(int s,int t){
	if(dep[s]<dep[t])swap(s,t);
	int d = dep[s]-dep[t];
	for(int i = 19;i>=0;i--){
		if(d&(1<<i))s = par[s][i];
	}
	for(int i = 19;i>=0;i--){
		if(par[s][i] != par[t][i])s = par[s][i],t = par[t][i];
	}
	if(s != t)s = t = par[s][0];
	for(int i = 19;i>=0;i--){
		if(dp[s][i])s = par[s][i];
	}
	if(val[s].sc)s = par[s][0];
	if(val[s].sc)return -1;
	else return val[s].fs;
}

int getMinimumFuelCapacity(int s, int t) {
	return getans(s,t);
}

Compilation message

swap.cpp: In function 'void INIT::GO()':
swap.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int i = 0;i<edges.size();i++){
      |                 ~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27228 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 5 ms 29276 KB Output is correct
5 Correct 6 ms 29360 KB Output is correct
6 Correct 6 ms 29336 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct
8 Correct 6 ms 29428 KB Output is correct
9 Correct 95 ms 57564 KB Output is correct
10 Correct 112 ms 65224 KB Output is correct
11 Correct 120 ms 65208 KB Output is correct
12 Correct 119 ms 65744 KB Output is correct
13 Correct 110 ms 68832 KB Output is correct
14 Correct 98 ms 57736 KB Output is correct
15 Correct 207 ms 69316 KB Output is correct
16 Correct 204 ms 68732 KB Output is correct
17 Correct 213 ms 69588 KB Output is correct
18 Correct 288 ms 72860 KB Output is correct
19 Correct 81 ms 40128 KB Output is correct
20 Correct 196 ms 70372 KB Output is correct
21 Correct 231 ms 70272 KB Output is correct
22 Correct 210 ms 70948 KB Output is correct
23 Correct 277 ms 74160 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27228 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 247 ms 76124 KB Output is correct
4 Correct 223 ms 76492 KB Output is correct
5 Correct 270 ms 76340 KB Output is correct
6 Correct 211 ms 76336 KB Output is correct
7 Correct 254 ms 76612 KB Output is correct
8 Correct 218 ms 75948 KB Output is correct
9 Correct 218 ms 76360 KB Output is correct
10 Correct 229 ms 75856 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27228 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 5 ms 29276 KB Output is correct
5 Correct 6 ms 29360 KB Output is correct
6 Correct 6 ms 29336 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct
8 Correct 6 ms 29428 KB Output is correct
9 Correct 5 ms 27224 KB Output is correct
10 Correct 6 ms 29276 KB Output is correct
11 Correct 6 ms 29276 KB Output is correct
12 Correct 6 ms 29276 KB Output is correct
13 Correct 5 ms 29276 KB Output is correct
14 Correct 6 ms 29276 KB Output is correct
15 Correct 6 ms 29276 KB Output is correct
16 Correct 5 ms 29276 KB Output is correct
17 Correct 5 ms 29276 KB Output is correct
18 Correct 5 ms 29276 KB Output is correct
19 Correct 6 ms 29276 KB Output is correct
20 Correct 5 ms 29276 KB Output is correct
21 Correct 5 ms 29276 KB Output is correct
22 Correct 6 ms 29532 KB Output is correct
23 Correct 6 ms 29276 KB Output is correct
24 Correct 6 ms 29320 KB Output is correct
25 Correct 7 ms 29328 KB Output is correct
26 Correct 6 ms 29532 KB Output is correct
27 Correct 5 ms 29276 KB Output is correct
28 Correct 6 ms 29532 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 8 ms 27228 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 5 ms 29276 KB Output is correct
6 Correct 6 ms 29360 KB Output is correct
7 Correct 6 ms 29336 KB Output is correct
8 Correct 6 ms 29276 KB Output is correct
9 Correct 6 ms 29428 KB Output is correct
10 Correct 95 ms 57564 KB Output is correct
11 Correct 112 ms 65224 KB Output is correct
12 Correct 120 ms 65208 KB Output is correct
13 Correct 119 ms 65744 KB Output is correct
14 Correct 110 ms 68832 KB Output is correct
15 Correct 6 ms 29276 KB Output is correct
16 Correct 6 ms 29276 KB Output is correct
17 Correct 6 ms 29276 KB Output is correct
18 Correct 5 ms 29276 KB Output is correct
19 Correct 6 ms 29276 KB Output is correct
20 Correct 6 ms 29276 KB Output is correct
21 Correct 5 ms 29276 KB Output is correct
22 Correct 5 ms 29276 KB Output is correct
23 Correct 5 ms 29276 KB Output is correct
24 Correct 6 ms 29276 KB Output is correct
25 Correct 5 ms 29276 KB Output is correct
26 Correct 5 ms 29276 KB Output is correct
27 Correct 6 ms 29532 KB Output is correct
28 Correct 6 ms 29276 KB Output is correct
29 Correct 6 ms 29320 KB Output is correct
30 Correct 7 ms 29328 KB Output is correct
31 Correct 6 ms 29532 KB Output is correct
32 Correct 5 ms 29276 KB Output is correct
33 Correct 6 ms 29532 KB Output is correct
34 Correct 15 ms 34588 KB Output is correct
35 Correct 115 ms 65196 KB Output is correct
36 Correct 115 ms 64968 KB Output is correct
37 Correct 114 ms 64708 KB Output is correct
38 Correct 118 ms 65328 KB Output is correct
39 Correct 111 ms 65072 KB Output is correct
40 Correct 103 ms 62268 KB Output is correct
41 Correct 114 ms 65732 KB Output is correct
42 Correct 110 ms 64732 KB Output is correct
43 Correct 103 ms 69320 KB Output is correct
44 Correct 119 ms 65304 KB Output is correct
45 Correct 131 ms 80596 KB Output is correct
46 Correct 112 ms 65444 KB Output is correct
47 Correct 115 ms 65480 KB Output is correct
48 Correct 147 ms 70856 KB Output is correct
49 Correct 92 ms 76476 KB Output is correct
50 Correct 77 ms 65476 KB Output is correct
51 Correct 116 ms 73156 KB Output is correct
52 Correct 151 ms 84648 KB Output is correct
53 Correct 182 ms 87676 KB Output is correct
54 Correct 174 ms 96192 KB Output is correct
55 Correct 105 ms 69060 KB Output is correct
56 Correct 168 ms 90664 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27228 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 5 ms 29276 KB Output is correct
5 Correct 6 ms 29360 KB Output is correct
6 Correct 6 ms 29336 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct
8 Correct 6 ms 29428 KB Output is correct
9 Correct 95 ms 57564 KB Output is correct
10 Correct 112 ms 65224 KB Output is correct
11 Correct 120 ms 65208 KB Output is correct
12 Correct 119 ms 65744 KB Output is correct
13 Correct 110 ms 68832 KB Output is correct
14 Correct 98 ms 57736 KB Output is correct
15 Correct 207 ms 69316 KB Output is correct
16 Correct 204 ms 68732 KB Output is correct
17 Correct 213 ms 69588 KB Output is correct
18 Correct 288 ms 72860 KB Output is correct
19 Correct 247 ms 76124 KB Output is correct
20 Correct 223 ms 76492 KB Output is correct
21 Correct 270 ms 76340 KB Output is correct
22 Correct 211 ms 76336 KB Output is correct
23 Correct 254 ms 76612 KB Output is correct
24 Correct 218 ms 75948 KB Output is correct
25 Correct 218 ms 76360 KB Output is correct
26 Correct 229 ms 75856 KB Output is correct
27 Correct 6 ms 29276 KB Output is correct
28 Correct 6 ms 29276 KB Output is correct
29 Correct 6 ms 29276 KB Output is correct
30 Correct 5 ms 29276 KB Output is correct
31 Correct 6 ms 29276 KB Output is correct
32 Correct 6 ms 29276 KB Output is correct
33 Correct 5 ms 29276 KB Output is correct
34 Correct 5 ms 29276 KB Output is correct
35 Correct 5 ms 29276 KB Output is correct
36 Correct 15 ms 34588 KB Output is correct
37 Correct 115 ms 65196 KB Output is correct
38 Correct 115 ms 64968 KB Output is correct
39 Correct 114 ms 64708 KB Output is correct
40 Correct 118 ms 65328 KB Output is correct
41 Correct 111 ms 65072 KB Output is correct
42 Correct 103 ms 62268 KB Output is correct
43 Correct 114 ms 65732 KB Output is correct
44 Correct 110 ms 64732 KB Output is correct
45 Correct 103 ms 69320 KB Output is correct
46 Correct 119 ms 65304 KB Output is correct
47 Correct 25 ms 32796 KB Output is correct
48 Correct 223 ms 70188 KB Output is correct
49 Correct 199 ms 70152 KB Output is correct
50 Correct 205 ms 70424 KB Output is correct
51 Correct 193 ms 69664 KB Output is correct
52 Correct 191 ms 69700 KB Output is correct
53 Correct 162 ms 60120 KB Output is correct
54 Correct 209 ms 70700 KB Output is correct
55 Correct 205 ms 70188 KB Output is correct
56 Correct 250 ms 73364 KB Output is correct
57 Correct 207 ms 71124 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 8 ms 27228 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 5 ms 29276 KB Output is correct
6 Correct 6 ms 29360 KB Output is correct
7 Correct 6 ms 29336 KB Output is correct
8 Correct 6 ms 29276 KB Output is correct
9 Correct 6 ms 29428 KB Output is correct
10 Correct 95 ms 57564 KB Output is correct
11 Correct 112 ms 65224 KB Output is correct
12 Correct 120 ms 65208 KB Output is correct
13 Correct 119 ms 65744 KB Output is correct
14 Correct 110 ms 68832 KB Output is correct
15 Correct 98 ms 57736 KB Output is correct
16 Correct 207 ms 69316 KB Output is correct
17 Correct 204 ms 68732 KB Output is correct
18 Correct 213 ms 69588 KB Output is correct
19 Correct 288 ms 72860 KB Output is correct
20 Correct 247 ms 76124 KB Output is correct
21 Correct 223 ms 76492 KB Output is correct
22 Correct 270 ms 76340 KB Output is correct
23 Correct 211 ms 76336 KB Output is correct
24 Correct 254 ms 76612 KB Output is correct
25 Correct 218 ms 75948 KB Output is correct
26 Correct 218 ms 76360 KB Output is correct
27 Correct 229 ms 75856 KB Output is correct
28 Correct 6 ms 29276 KB Output is correct
29 Correct 6 ms 29276 KB Output is correct
30 Correct 6 ms 29276 KB Output is correct
31 Correct 5 ms 29276 KB Output is correct
32 Correct 6 ms 29276 KB Output is correct
33 Correct 6 ms 29276 KB Output is correct
34 Correct 5 ms 29276 KB Output is correct
35 Correct 5 ms 29276 KB Output is correct
36 Correct 5 ms 29276 KB Output is correct
37 Correct 15 ms 34588 KB Output is correct
38 Correct 115 ms 65196 KB Output is correct
39 Correct 115 ms 64968 KB Output is correct
40 Correct 114 ms 64708 KB Output is correct
41 Correct 118 ms 65328 KB Output is correct
42 Correct 111 ms 65072 KB Output is correct
43 Correct 103 ms 62268 KB Output is correct
44 Correct 114 ms 65732 KB Output is correct
45 Correct 110 ms 64732 KB Output is correct
46 Correct 103 ms 69320 KB Output is correct
47 Correct 119 ms 65304 KB Output is correct
48 Correct 25 ms 32796 KB Output is correct
49 Correct 223 ms 70188 KB Output is correct
50 Correct 199 ms 70152 KB Output is correct
51 Correct 205 ms 70424 KB Output is correct
52 Correct 193 ms 69664 KB Output is correct
53 Correct 191 ms 69700 KB Output is correct
54 Correct 162 ms 60120 KB Output is correct
55 Correct 209 ms 70700 KB Output is correct
56 Correct 205 ms 70188 KB Output is correct
57 Correct 250 ms 73364 KB Output is correct
58 Correct 207 ms 71124 KB Output is correct
59 Correct 81 ms 40128 KB Output is correct
60 Correct 196 ms 70372 KB Output is correct
61 Correct 231 ms 70272 KB Output is correct
62 Correct 210 ms 70948 KB Output is correct
63 Correct 277 ms 74160 KB Output is correct
64 Correct 6 ms 29276 KB Output is correct
65 Correct 5 ms 29276 KB Output is correct
66 Correct 5 ms 29276 KB Output is correct
67 Correct 6 ms 29532 KB Output is correct
68 Correct 6 ms 29276 KB Output is correct
69 Correct 6 ms 29320 KB Output is correct
70 Correct 7 ms 29328 KB Output is correct
71 Correct 6 ms 29532 KB Output is correct
72 Correct 5 ms 29276 KB Output is correct
73 Correct 6 ms 29532 KB Output is correct
74 Correct 131 ms 80596 KB Output is correct
75 Correct 112 ms 65444 KB Output is correct
76 Correct 115 ms 65480 KB Output is correct
77 Correct 147 ms 70856 KB Output is correct
78 Correct 92 ms 76476 KB Output is correct
79 Correct 77 ms 65476 KB Output is correct
80 Correct 116 ms 73156 KB Output is correct
81 Correct 151 ms 84648 KB Output is correct
82 Correct 182 ms 87676 KB Output is correct
83 Correct 174 ms 96192 KB Output is correct
84 Correct 105 ms 69060 KB Output is correct
85 Correct 168 ms 90664 KB Output is correct
86 Correct 70 ms 48768 KB Output is correct
87 Correct 200 ms 70212 KB Output is correct
88 Correct 205 ms 70204 KB Output is correct
89 Correct 251 ms 73272 KB Output is correct
90 Correct 177 ms 82484 KB Output is correct
91 Correct 175 ms 79936 KB Output is correct
92 Correct 253 ms 77348 KB Output is correct
93 Correct 268 ms 90312 KB Output is correct
94 Correct 312 ms 93316 KB Output is correct
95 Correct 281 ms 100768 KB Output is correct
96 Correct 257 ms 73664 KB Output is correct
97 Correct 286 ms 85376 KB Output is correct