oj.uz

Submission #676528

# Submission time Handle Problem Language Result Execution time Memory
676528 2022-12-31T07:46:06 Z NothingXD Swapping Cities (APIO20_swap) C++14
43 / 100
 342 ms 56788 KB 
#include "swap.h"

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
/*typedef __uint128_t L;
struct FastMod {
	ull b, m;
	FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
	ull reduce(ull a) {
		ull q = (ull)((L(m) * a) >> 64);
		ull r = a - q * b; // can be proven that 0 <= r < 2*b
		return r >= b ? r - b : r;
	}
};
FastMod FM(2);*/
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e5 + 10;
const int lg = 20;

int n, m, a[maxn], dsu[maxn], d[maxn], leaf[maxn], par[maxn][lg], h[maxn], vercnt;
bool cycle[maxn], ok[maxn];
vector<int> g[maxn];

int getdsu(int v){
	return (dsu[v] == -1? v: dsu[v] = getdsu(dsu[v]));
}

void merge(int u, int v, int w){
	int U = getdsu(u), V = getdsu(v);
	if (U == V){
		vercnt++;
		cycle[vercnt] = true;
		dsu[U] = vercnt;
		g[vercnt].push_back(U);
		leaf[vercnt] = leaf[U];
	}
	else{
		vercnt++;
		dsu[U] = dsu[V] = vercnt;
		g[vercnt].push_back(U);
		g[vercnt].push_back(V);
		leaf[vercnt] = leaf[U] + leaf[V];
		cycle[vercnt] = (cycle[U] || cycle[V]);
	}
	if (d[u] == 1) leaf[vercnt]--;
	if (d[v] == 1) leaf[vercnt]--;
	d[u]++;
	d[v]++;
	ok[vercnt] = (cycle[vercnt] || (leaf[vercnt] > 2));
	a[vercnt] = w;
}

void dfs(int v, int p = -1){
	if (!ok[v]){
		if (p == -1) a[v] = -1;
		else a[v] = a[p];
	}
	par[v][0] = p;
	for (int i = 1; i < lg; i++){
		if (par[v][i-1] != -1) par[v][i] = par[par[v][i-1]][i-1];
	}
	for (auto u: g[v]){
		h[u] = h[v] + 1;
		dfs(u, v);
	}
}

int getpar(int v, int x){
	for (int i = 0; i < lg; i++) if ((x >> i) & 1) v = par[v][i];
	return v;
}

int lca(int u, int v){
	if (h[v] > h[u]) swap(u, v);
	u = getpar(u, h[u]-h[v]);
	if (u == v) return u;
	for (int i = lg-1; ~i; i--){
		if (par[v][i] != par[u][i]){
			v = par[v][i];
			u = par[u][i];
		}
	}
	return par[v][0];
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	memset(dsu, -1, sizeof dsu);
	memset(par, -1, sizeof par);
	n = N, m = M;
	for (int i = 1; i <= n; i++) leaf[i] = 1;
	vector<pair<int,pii>> edge;
	for (int i = 0; i < m; i++) edge.push_back({W[i], {U[i], V[i]}});
	sort(all(edge));
	vercnt = n;
	for (auto [w, x]: edge){
		merge(x.F, x.S, w);
	}
	dfs(vercnt);
}

int getMinimumFuelCapacity(int X, int Y) {
	int v = lca(X, Y);
	return a[v];
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:118:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |  for (auto [w, x]: edge){
      |            ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31956 KB Output is correct
2 Correct 15 ms 31932 KB Output is correct
3 Correct 15 ms 31956 KB Output is correct
4 Correct 15 ms 32084 KB Output is correct
5 Correct 15 ms 32120 KB Output is correct
6 Correct 15 ms 32020 KB Output is correct
7 Correct 15 ms 32084 KB Output is correct
8 Correct 18 ms 32132 KB Output is correct
9 Correct 91 ms 41152 KB Output is correct
10 Correct 119 ms 43256 KB Output is correct
11 Correct 114 ms 42996 KB Output is correct
12 Correct 139 ms 43692 KB Output is correct
13 Correct 104 ms 45996 KB Output is correct
14 Correct 99 ms 41528 KB Output is correct
15 Correct 255 ms 45272 KB Output is correct
16 Correct 233 ms 44900 KB Output is correct
17 Correct 225 ms 45432 KB Output is correct
18 Correct 342 ms 47880 KB Output is correct
19 Correct 84 ms 38804 KB Output is correct
20 Correct 251 ms 45448 KB Output is correct
21 Correct 219 ms 45336 KB Output is correct
22 Correct 227 ms 45968 KB Output is correct
23 Correct 297 ms 48312 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31956 KB Output is correct
2 Correct 15 ms 31932 KB Output is correct
3 Correct 273 ms 49724 KB Output is correct
4 Correct 247 ms 50244 KB Output is correct
5 Correct 287 ms 50164 KB Output is correct
6 Correct 252 ms 50180 KB Output is correct
7 Incorrect 287 ms 50176 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31956 KB Output is correct
2 Correct 15 ms 31932 KB Output is correct
3 Correct 15 ms 31956 KB Output is correct
4 Correct 15 ms 32084 KB Output is correct
5 Correct 15 ms 32120 KB Output is correct
6 Correct 15 ms 32020 KB Output is correct
7 Correct 15 ms 32084 KB Output is correct
8 Correct 18 ms 32132 KB Output is correct
9 Correct 14 ms 31928 KB Output is correct
10 Correct 14 ms 32084 KB Output is correct
11 Correct 15 ms 32084 KB Output is correct
12 Correct 17 ms 32108 KB Output is correct
13 Correct 17 ms 32064 KB Output is correct
14 Correct 14 ms 32084 KB Output is correct
15 Correct 15 ms 32084 KB Output is correct
16 Correct 15 ms 32076 KB Output is correct
17 Correct 17 ms 32064 KB Output is correct
18 Correct 15 ms 32108 KB Output is correct
19 Correct 15 ms 32084 KB Output is correct
20 Correct 15 ms 32144 KB Output is correct
21 Correct 15 ms 32072 KB Output is correct
22 Correct 16 ms 32204 KB Output is correct
23 Correct 14 ms 32084 KB Output is correct
24 Correct 16 ms 32168 KB Output is correct
25 Correct 17 ms 32212 KB Output is correct
26 Correct 15 ms 32240 KB Output is correct
27 Correct 16 ms 32172 KB Output is correct
28 Correct 15 ms 32240 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31928 KB Output is correct
2 Correct 15 ms 31956 KB Output is correct
3 Correct 15 ms 31932 KB Output is correct
4 Correct 15 ms 31956 KB Output is correct
5 Correct 15 ms 32084 KB Output is correct
6 Correct 15 ms 32120 KB Output is correct
7 Correct 15 ms 32020 KB Output is correct
8 Correct 15 ms 32084 KB Output is correct
9 Correct 18 ms 32132 KB Output is correct
10 Correct 91 ms 41152 KB Output is correct
11 Correct 119 ms 43256 KB Output is correct
12 Correct 114 ms 42996 KB Output is correct
13 Correct 139 ms 43692 KB Output is correct
14 Correct 104 ms 45996 KB Output is correct
15 Correct 14 ms 32084 KB Output is correct
16 Correct 15 ms 32084 KB Output is correct
17 Correct 17 ms 32108 KB Output is correct
18 Correct 17 ms 32064 KB Output is correct
19 Correct 14 ms 32084 KB Output is correct
20 Correct 15 ms 32084 KB Output is correct
21 Correct 15 ms 32076 KB Output is correct
22 Correct 17 ms 32064 KB Output is correct
23 Correct 15 ms 32108 KB Output is correct
24 Correct 15 ms 32084 KB Output is correct
25 Correct 15 ms 32144 KB Output is correct
26 Correct 15 ms 32072 KB Output is correct
27 Correct 16 ms 32204 KB Output is correct
28 Correct 14 ms 32084 KB Output is correct
29 Correct 16 ms 32168 KB Output is correct
30 Correct 17 ms 32212 KB Output is correct
31 Correct 15 ms 32240 KB Output is correct
32 Correct 16 ms 32172 KB Output is correct
33 Correct 15 ms 32240 KB Output is correct
34 Correct 27 ms 33548 KB Output is correct
35 Correct 107 ms 43328 KB Output is correct
36 Correct 103 ms 43448 KB Output is correct
37 Correct 107 ms 43436 KB Output is correct
38 Correct 99 ms 43200 KB Output is correct
39 Correct 107 ms 43136 KB Output is correct
40 Correct 124 ms 42304 KB Output is correct
41 Correct 114 ms 43636 KB Output is correct
42 Correct 109 ms 43456 KB Output is correct
43 Correct 93 ms 46468 KB Output is correct
44 Correct 110 ms 43660 KB Output is correct
45 Correct 161 ms 51744 KB Output is correct
46 Correct 112 ms 43440 KB Output is correct
47 Correct 127 ms 43460 KB Output is correct
48 Correct 122 ms 46264 KB Output is correct
49 Correct 104 ms 54332 KB Output is correct
50 Correct 87 ms 49448 KB Output is correct
51 Correct 125 ms 49672 KB Output is correct
52 Correct 158 ms 51640 KB Output is correct
53 Correct 189 ms 52936 KB Output is correct
54 Correct 197 ms 56788 KB Output is correct
55 Correct 103 ms 46248 KB Output is correct
56 Correct 171 ms 54636 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31956 KB Output is correct
2 Correct 15 ms 31932 KB Output is correct
3 Correct 15 ms 31956 KB Output is correct
4 Correct 15 ms 32084 KB Output is correct
5 Correct 15 ms 32120 KB Output is correct
6 Correct 15 ms 32020 KB Output is correct
7 Correct 15 ms 32084 KB Output is correct
8 Correct 18 ms 32132 KB Output is correct
9 Correct 91 ms 41152 KB Output is correct
10 Correct 119 ms 43256 KB Output is correct
11 Correct 114 ms 42996 KB Output is correct
12 Correct 139 ms 43692 KB Output is correct
13 Correct 104 ms 45996 KB Output is correct
14 Correct 99 ms 41528 KB Output is correct
15 Correct 255 ms 45272 KB Output is correct
16 Correct 233 ms 44900 KB Output is correct
17 Correct 225 ms 45432 KB Output is correct
18 Correct 342 ms 47880 KB Output is correct
19 Correct 273 ms 49724 KB Output is correct
20 Correct 247 ms 50244 KB Output is correct
21 Correct 287 ms 50164 KB Output is correct
22 Correct 252 ms 50180 KB Output is correct
23 Incorrect 287 ms 50176 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31928 KB Output is correct
2 Correct 15 ms 31956 KB Output is correct
3 Correct 15 ms 31932 KB Output is correct
4 Correct 15 ms 31956 KB Output is correct
5 Correct 15 ms 32084 KB Output is correct
6 Correct 15 ms 32120 KB Output is correct
7 Correct 15 ms 32020 KB Output is correct
8 Correct 15 ms 32084 KB Output is correct
9 Correct 18 ms 32132 KB Output is correct
10 Correct 91 ms 41152 KB Output is correct
11 Correct 119 ms 43256 KB Output is correct
12 Correct 114 ms 42996 KB Output is correct
13 Correct 139 ms 43692 KB Output is correct
14 Correct 104 ms 45996 KB Output is correct
15 Correct 99 ms 41528 KB Output is correct
16 Correct 255 ms 45272 KB Output is correct
17 Correct 233 ms 44900 KB Output is correct
18 Correct 225 ms 45432 KB Output is correct
19 Correct 342 ms 47880 KB Output is correct
20 Correct 273 ms 49724 KB Output is correct
21 Correct 247 ms 50244 KB Output is correct
22 Correct 287 ms 50164 KB Output is correct
23 Correct 252 ms 50180 KB Output is correct
24 Incorrect 287 ms 50176 KB Output isn't correct
25 Halted 0 ms 0 KB -