oj.uz

Submission #403385

# Submission time Handle Problem Language Result Execution time Memory
403385 2021-05-13T06:27:13 Z Magnam_Caritatem Swapping Cities (APIO20_swap) C++17
100 / 100
 408 ms 36376 KB 
/*
	Task	: swap
	Author	: Phumipat C. [MAGCARI]
	Language: C++
	Created	: 13 May 2021 [12:22]
	Algo	: 
	Status	: 
*/
#include<bits/stdc++.h>
#include "swap.h"
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x),end(x)
#define allst(x,y) (x).begin()+y,(x).end()
#define rmdup(x) (x).resize(unique((x).begin(),(x).end())-(x).begin())
#define sz(x) (int)(x).size()
#define decp(x) fixed << setprecision(x)
#define MOD (LL )(1e9+7)
using namespace std;
using LL = long long;
using PII = pair<int ,int >;
using PLL = pair<long long ,long long >;
const int dir4[2][4] = {{1,-1,0,0},{0,0,1,-1}};
const int dir8[2][8] = {{-1,-1,-1,0,1,1,1,0},{-1,0,1,1,-1,0,1,-1}};
LL modN(LL a,LL b,LL c = MOD){
	if(b == 0)	return 1;
	if(b == 1)	return a%c;
	LL now = modN(a,b/2,c);
	if(b&1)	return (((now*now)%c)*(a%c))%c;
	else	return (now*now)%c;
}
struct A{
	int u,v,w;
	bool operator < (const A&o) const{
		return w<o.w;
	}
};
const int mxN = 300010;
vector<A > edges;
int p[mxN],deg[mxN],mx[mxN];
bool hide[mxN];
int fr(int u){
	return (u == p[u])?u:p[u] = fr(p[u]);
}
int LCA[mxN][20],lv[mxN];
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	iota(p,p+N+M,0);
	for(int i=0;i<N+M;i++)
		LCA[i][0] = i;
	for(int i=0;i<M;i++)
		edges.push_back({U[i],V[i],W[i]});
	sort(all(edges));
	int cnt = N;
	for(auto x:edges){
		int ru = fr(x.u),rv = fr(x.v);
		p[ru] = p[rv] = cnt;
		LCA[ru][0] = LCA[rv][0] = cnt;
		deg[x.u]++,deg[x.v]++;
		// Check if this path can hide
		mx[cnt] = x.w;
		if(ru == rv || deg[x.u]>2 || deg[x.v]>2 || hide[ru] || hide[rv])	hide[cnt] = true;
		cnt++;
	}
	for(int i=cnt-1;i>=0;i--){
		for(int j=1;j<=17;j++)
			LCA[i][j] = LCA[LCA[i][j-1]][j-1];
		lv[i] = lv[LCA[i][0]] + 1;
	}
}
int find_LCA(int u,int v){
	if(lv[u]<lv[v])	swap(u,v);
	for(int i=17;i>=0;i--){
		if(lv[LCA[u][i]]<lv[v])	continue;
		u = LCA[u][i];
	}
	if(u == v)	return u;
	for(int i=17;i>=0;i--){
		if(LCA[u][i] == LCA[v][i])	continue;
		u = LCA[u][i],v = LCA[v][i];
	}
	return LCA[u][0];
}
int getMinimumFuelCapacity(int X, int Y) {
	int pa = find_LCA(X,Y);
	if(hide[pa])	return mx[pa];
	for(int i=17;i>=0;i--){
		if(hide[LCA[pa][i]])	continue;
		pa = LCA[pa][i];
	}
	pa = LCA[pa][0];
	return (hide[pa]?mx[pa]:-1);
}
// int main() {
//   int N, M;
//   assert(2 == scanf("%d %d", &N, &M));
  
//   std::vector<int> U(M), V(M), W(M);
//   for (int i = 0; i < M; ++i) {
//     assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
//   }

//   int Q;
//   assert(1 == scanf("%d", &Q));

//   std::vector<int> X(Q), Y(Q);
//   for (int i = 0; i < Q; ++i) {
//     assert(2 == scanf("%d %d", &X[i], &Y[i]));
//   }

//   init(N, M, U, V, W);
  
//   std::vector<int> minimum_fuel_capacities(Q);
//   for (int i = 0; i < Q; ++i) {
//     minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
//   }

//   for (int i = 0; i < Q; ++i) {
//     printf("%d\n", minimum_fuel_capacities[i]);
//   }
  
//   return 0;
// }

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 79 ms 17584 KB Output is correct
10 Correct 89 ms 21284 KB Output is correct
11 Correct 94 ms 20984 KB Output is correct
12 Correct 103 ms 22196 KB Output is correct
13 Correct 134 ms 22704 KB Output is correct
14 Correct 96 ms 17704 KB Output is correct
15 Correct 256 ms 23320 KB Output is correct
16 Correct 284 ms 22760 KB Output is correct
17 Correct 276 ms 23972 KB Output is correct
18 Correct 408 ms 24984 KB Output is correct
19 Correct 134 ms 7936 KB Output is correct
20 Correct 260 ms 24740 KB Output is correct
21 Correct 263 ms 23928 KB Output is correct
22 Correct 277 ms 25384 KB Output is correct
23 Correct 377 ms 25944 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 334 ms 23964 KB Output is correct
4 Correct 300 ms 24956 KB Output is correct
5 Correct 305 ms 24608 KB Output is correct
6 Correct 323 ms 24864 KB Output is correct
7 Correct 338 ms 24720 KB Output is correct
8 Correct 318 ms 23960 KB Output is correct
9 Correct 331 ms 24608 KB Output is correct
10 Correct 322 ms 23924 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 568 KB Output is correct
16 Correct 2 ms 572 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 2 ms 572 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 2 ms 588 KB Output is correct
22 Correct 2 ms 588 KB Output is correct
23 Correct 3 ms 460 KB Output is correct
24 Correct 2 ms 604 KB Output is correct
25 Correct 2 ms 672 KB Output is correct
26 Correct 2 ms 716 KB Output is correct
27 Correct 1 ms 460 KB Output is correct
28 Correct 2 ms 588 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 79 ms 17584 KB Output is correct
11 Correct 89 ms 21284 KB Output is correct
12 Correct 94 ms 20984 KB Output is correct
13 Correct 103 ms 22196 KB Output is correct
14 Correct 134 ms 22704 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 568 KB Output is correct
21 Correct 2 ms 572 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 2 ms 572 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 ms 588 KB Output is correct
27 Correct 2 ms 588 KB Output is correct
28 Correct 3 ms 460 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 2 ms 672 KB Output is correct
31 Correct 2 ms 716 KB Output is correct
32 Correct 1 ms 460 KB Output is correct
33 Correct 2 ms 588 KB Output is correct
34 Correct 12 ms 3596 KB Output is correct
35 Correct 99 ms 22320 KB Output is correct
36 Correct 95 ms 22204 KB Output is correct
37 Correct 97 ms 22196 KB Output is correct
38 Correct 96 ms 21948 KB Output is correct
39 Correct 96 ms 21808 KB Output is correct
40 Correct 94 ms 20024 KB Output is correct
41 Correct 99 ms 22204 KB Output is correct
42 Correct 96 ms 22200 KB Output is correct
43 Correct 115 ms 22324 KB Output is correct
44 Correct 110 ms 22288 KB Output is correct
45 Correct 164 ms 26324 KB Output is correct
46 Correct 94 ms 22196 KB Output is correct
47 Correct 94 ms 22176 KB Output is correct
48 Correct 120 ms 23352 KB Output is correct
49 Correct 96 ms 20660 KB Output is correct
50 Correct 80 ms 16484 KB Output is correct
51 Correct 123 ms 22540 KB Output is correct
52 Correct 145 ms 29964 KB Output is correct
53 Correct 198 ms 32196 KB Output is correct
54 Correct 174 ms 34764 KB Output is correct
55 Correct 100 ms 22328 KB Output is correct
56 Correct 192 ms 31488 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 79 ms 17584 KB Output is correct
10 Correct 89 ms 21284 KB Output is correct
11 Correct 94 ms 20984 KB Output is correct
12 Correct 103 ms 22196 KB Output is correct
13 Correct 134 ms 22704 KB Output is correct
14 Correct 96 ms 17704 KB Output is correct
15 Correct 256 ms 23320 KB Output is correct
16 Correct 284 ms 22760 KB Output is correct
17 Correct 276 ms 23972 KB Output is correct
18 Correct 408 ms 24984 KB Output is correct
19 Correct 334 ms 23964 KB Output is correct
20 Correct 300 ms 24956 KB Output is correct
21 Correct 305 ms 24608 KB Output is correct
22 Correct 323 ms 24864 KB Output is correct
23 Correct 338 ms 24720 KB Output is correct
24 Correct 318 ms 23960 KB Output is correct
25 Correct 331 ms 24608 KB Output is correct
26 Correct 322 ms 23924 KB Output is correct
27 Correct 2 ms 460 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 1 ms 460 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 2 ms 568 KB Output is correct
33 Correct 2 ms 572 KB Output is correct
34 Correct 2 ms 460 KB Output is correct
35 Correct 2 ms 572 KB Output is correct
36 Correct 12 ms 3596 KB Output is correct
37 Correct 99 ms 22320 KB Output is correct
38 Correct 95 ms 22204 KB Output is correct
39 Correct 97 ms 22196 KB Output is correct
40 Correct 96 ms 21948 KB Output is correct
41 Correct 96 ms 21808 KB Output is correct
42 Correct 94 ms 20024 KB Output is correct
43 Correct 99 ms 22204 KB Output is correct
44 Correct 96 ms 22200 KB Output is correct
45 Correct 115 ms 22324 KB Output is correct
46 Correct 110 ms 22288 KB Output is correct
47 Correct 22 ms 3724 KB Output is correct
48 Correct 257 ms 24828 KB Output is correct
49 Correct 257 ms 24860 KB Output is correct
50 Correct 246 ms 24848 KB Output is correct
51 Correct 242 ms 24716 KB Output is correct
52 Correct 223 ms 23444 KB Output is correct
53 Correct 200 ms 18460 KB Output is correct
54 Correct 256 ms 25376 KB Output is correct
55 Correct 262 ms 24736 KB Output is correct
56 Correct 364 ms 24872 KB Output is correct
57 Correct 255 ms 25500 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 79 ms 17584 KB Output is correct
11 Correct 89 ms 21284 KB Output is correct
12 Correct 94 ms 20984 KB Output is correct
13 Correct 103 ms 22196 KB Output is correct
14 Correct 134 ms 22704 KB Output is correct
15 Correct 96 ms 17704 KB Output is correct
16 Correct 256 ms 23320 KB Output is correct
17 Correct 284 ms 22760 KB Output is correct
18 Correct 276 ms 23972 KB Output is correct
19 Correct 408 ms 24984 KB Output is correct
20 Correct 334 ms 23964 KB Output is correct
21 Correct 300 ms 24956 KB Output is correct
22 Correct 305 ms 24608 KB Output is correct
23 Correct 323 ms 24864 KB Output is correct
24 Correct 338 ms 24720 KB Output is correct
25 Correct 318 ms 23960 KB Output is correct
26 Correct 331 ms 24608 KB Output is correct
27 Correct 322 ms 23924 KB Output is correct
28 Correct 2 ms 460 KB Output is correct
29 Correct 1 ms 460 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 2 ms 460 KB Output is correct
33 Correct 2 ms 568 KB Output is correct
34 Correct 2 ms 572 KB Output is correct
35 Correct 2 ms 460 KB Output is correct
36 Correct 2 ms 572 KB Output is correct
37 Correct 12 ms 3596 KB Output is correct
38 Correct 99 ms 22320 KB Output is correct
39 Correct 95 ms 22204 KB Output is correct
40 Correct 97 ms 22196 KB Output is correct
41 Correct 96 ms 21948 KB Output is correct
42 Correct 96 ms 21808 KB Output is correct
43 Correct 94 ms 20024 KB Output is correct
44 Correct 99 ms 22204 KB Output is correct
45 Correct 96 ms 22200 KB Output is correct
46 Correct 115 ms 22324 KB Output is correct
47 Correct 110 ms 22288 KB Output is correct
48 Correct 22 ms 3724 KB Output is correct
49 Correct 257 ms 24828 KB Output is correct
50 Correct 257 ms 24860 KB Output is correct
51 Correct 246 ms 24848 KB Output is correct
52 Correct 242 ms 24716 KB Output is correct
53 Correct 223 ms 23444 KB Output is correct
54 Correct 200 ms 18460 KB Output is correct
55 Correct 256 ms 25376 KB Output is correct
56 Correct 262 ms 24736 KB Output is correct
57 Correct 364 ms 24872 KB Output is correct
58 Correct 255 ms 25500 KB Output is correct
59 Correct 134 ms 7936 KB Output is correct
60 Correct 260 ms 24740 KB Output is correct
61 Correct 263 ms 23928 KB Output is correct
62 Correct 277 ms 25384 KB Output is correct
63 Correct 377 ms 25944 KB Output is correct
64 Correct 2 ms 460 KB Output is correct
65 Correct 2 ms 460 KB Output is correct
66 Correct 2 ms 588 KB Output is correct
67 Correct 2 ms 588 KB Output is correct
68 Correct 3 ms 460 KB Output is correct
69 Correct 2 ms 604 KB Output is correct
70 Correct 2 ms 672 KB Output is correct
71 Correct 2 ms 716 KB Output is correct
72 Correct 1 ms 460 KB Output is correct
73 Correct 2 ms 588 KB Output is correct
74 Correct 164 ms 26324 KB Output is correct
75 Correct 94 ms 22196 KB Output is correct
76 Correct 94 ms 22176 KB Output is correct
77 Correct 120 ms 23352 KB Output is correct
78 Correct 96 ms 20660 KB Output is correct
79 Correct 80 ms 16484 KB Output is correct
80 Correct 123 ms 22540 KB Output is correct
81 Correct 145 ms 29964 KB Output is correct
82 Correct 198 ms 32196 KB Output is correct
83 Correct 174 ms 34764 KB Output is correct
84 Correct 100 ms 22328 KB Output is correct
85 Correct 192 ms 31488 KB Output is correct
86 Correct 84 ms 10188 KB Output is correct
87 Correct 241 ms 24864 KB Output is correct
88 Correct 246 ms 24816 KB Output is correct
89 Correct 309 ms 24860 KB Output is correct
90 Correct 218 ms 23820 KB Output is correct
91 Correct 239 ms 22768 KB Output is correct
92 Correct 334 ms 24720 KB Output is correct
93 Correct 307 ms 31900 KB Output is correct
94 Correct 399 ms 34228 KB Output is correct
95 Correct 350 ms 36376 KB Output is correct
96 Correct 356 ms 24992 KB Output is correct
97 Correct 382 ms 29368 KB Output is correct