oj.uz

Submission #530470

# Submission time Handle Problem Language Result Execution time Memory
530470 2022-02-25T12:39:48 Z hohohaha Swapping Cities (APIO20_swap) C++17
13 / 100
 139 ms 25356 KB 
#include<bits/stdc++.h>
#include <vector>

using namespace std; 
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); i++)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define sp ' '
#define endl '\n'
//#define int long long

const int maxn = 2e5 + 5, inf = INT_MAX / 2; 

int n, m; 
vector<pair<int, ii> > E; 
int deg[maxn]; 
int fre[maxn];
int rt[maxn];
int dep[maxn]; 
int pe[maxn];  
vi cc[maxn]; 

int getrt(int i) { 
	if(rt[i] < 0) return i; 
	return getrt(rt[i]); 
}
void join(int i, int j, int w) { 
	deg[i]++; 
	deg[j]++;
	bool ok = max(deg[i], deg[j]) >= 3;
	i = getrt(i); j = getrt(j); 
//	cout << w << sp << i << sp <<j << "cc" << endl;
	if(i == j) ok = 1; 
	else {
		if(rt[i] > rt[j]) swap(i, j); 
		rt[i] += rt[j]; 
		rt[j] = i; 
		for(int t: cc[j]) cc[i].eb(t); 
		pe[j] = w; 
		dep[j] = dep[i] + 1; 
	}
	if(ok){ 
		for(int x: cc[i]) fre[x] = w; 
		cc[i].clear(); 
	}
}
int get_lca(int u, int v) { 
	if(dep[u] < dep[v]) swap(u, v); 
	int mx = 0; 
	while(dep[u] > dep[v]) {
		mx = max(mx, pe[u]); 
		u = rt[u]; 
	}
	while(u != v) { 
		mx = max(mx, max(pe[u], pe[v])); 
		u = rt[u]; 
		v = rt[v]; 
	}
	return mx; 
}
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N; 
	m = M;  
	fori(i, 0, m - 1) { 
		int u = U[i] + 1, v = V[i] + 1, w = W[i]; 
		E.eb(make_pair(w, ii(u, v))); 
	}
	sort(begin(E), end(E)); 
	fori(i, 1, n) { 
		fre[i] = inf; 
		rt[i] = -1;  
		pe[i] = -1;
		cc[i].eb(i); 
	}
	for(auto temp: E) { 
		join(temp.se.fi, temp.se.se, temp.fi);
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	int u = X + 1, v = Y + 1; 
//	cout << get_lca(u, v) << endl; 
//	fori(i, 1, n) { 
//		cout << rt[i] << sp << pe[i]  << sp << fre[i] << endl; 
//	}
	int t =  max(get_lca(u, v), min(fre[u], fre[v])); 
	if(t == inf) return -1;
	return t; 
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5004 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4996 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5020 KB Output is correct
9 Correct 57 ms 16840 KB Output is correct
10 Correct 64 ms 18896 KB Output is correct
11 Correct 64 ms 18760 KB Output is correct
12 Correct 64 ms 19600 KB Output is correct
13 Correct 57 ms 17160 KB Output is correct
14 Correct 57 ms 16956 KB Output is correct
15 Correct 130 ms 23532 KB Output is correct
16 Correct 124 ms 22892 KB Output is correct
17 Correct 137 ms 23776 KB Output is correct
18 Correct 107 ms 20868 KB Output is correct
19 Correct 58 ms 12248 KB Output is correct
20 Correct 139 ms 24296 KB Output is correct
21 Correct 123 ms 24180 KB Output is correct
22 Correct 131 ms 25356 KB Output is correct
23 Correct 108 ms 22252 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5004 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 108 ms 19944 KB Output is correct
4 Correct 101 ms 20208 KB Output is correct
5 Correct 106 ms 20464 KB Output is correct
6 Correct 102 ms 20092 KB Output is correct
7 Correct 106 ms 20476 KB Output is correct
8 Correct 99 ms 19960 KB Output is correct
9 Correct 103 ms 20208 KB Output is correct
10 Correct 101 ms 19944 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5004 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4996 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5020 KB Output is correct
9 Correct 2 ms 4996 KB Output is correct
10 Correct 3 ms 5016 KB Output is correct
11 Incorrect 3 ms 5148 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4996 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4996 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 3 ms 5020 KB Output is correct
10 Correct 57 ms 16840 KB Output is correct
11 Correct 64 ms 18896 KB Output is correct
12 Correct 64 ms 18760 KB Output is correct
13 Correct 64 ms 19600 KB Output is correct
14 Correct 57 ms 17160 KB Output is correct
15 Correct 3 ms 5016 KB Output is correct
16 Incorrect 3 ms 5148 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5004 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4996 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5020 KB Output is correct
9 Correct 57 ms 16840 KB Output is correct
10 Correct 64 ms 18896 KB Output is correct
11 Correct 64 ms 18760 KB Output is correct
12 Correct 64 ms 19600 KB Output is correct
13 Correct 57 ms 17160 KB Output is correct
14 Correct 57 ms 16956 KB Output is correct
15 Correct 130 ms 23532 KB Output is correct
16 Correct 124 ms 22892 KB Output is correct
17 Correct 137 ms 23776 KB Output is correct
18 Correct 107 ms 20868 KB Output is correct
19 Correct 108 ms 19944 KB Output is correct
20 Correct 101 ms 20208 KB Output is correct
21 Correct 106 ms 20464 KB Output is correct
22 Correct 102 ms 20092 KB Output is correct
23 Correct 106 ms 20476 KB Output is correct
24 Correct 99 ms 19960 KB Output is correct
25 Correct 103 ms 20208 KB Output is correct
26 Correct 101 ms 19944 KB Output is correct
27 Correct 3 ms 5016 KB Output is correct
28 Incorrect 3 ms 5148 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4996 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4996 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 3 ms 5020 KB Output is correct
10 Correct 57 ms 16840 KB Output is correct
11 Correct 64 ms 18896 KB Output is correct
12 Correct 64 ms 18760 KB Output is correct
13 Correct 64 ms 19600 KB Output is correct
14 Correct 57 ms 17160 KB Output is correct
15 Correct 57 ms 16956 KB Output is correct
16 Correct 130 ms 23532 KB Output is correct
17 Correct 124 ms 22892 KB Output is correct
18 Correct 137 ms 23776 KB Output is correct
19 Correct 107 ms 20868 KB Output is correct
20 Correct 108 ms 19944 KB Output is correct
21 Correct 101 ms 20208 KB Output is correct
22 Correct 106 ms 20464 KB Output is correct
23 Correct 102 ms 20092 KB Output is correct
24 Correct 106 ms 20476 KB Output is correct
25 Correct 99 ms 19960 KB Output is correct
26 Correct 103 ms 20208 KB Output is correct
27 Correct 101 ms 19944 KB Output is correct
28 Correct 3 ms 5016 KB Output is correct
29 Incorrect 3 ms 5148 KB Output isn't correct
30 Halted 0 ms 0 KB -