oj.uz

Submission #981908

# Submission time Handle Problem Language Result Execution time Memory
981908 2024-05-13T16:18:01 Z vjudge1 Swapping Cities (APIO20_swap) C++17
43 / 100
 418 ms 32152 KB 
#include "swap.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
long long n, m, i, j, sz[200001], p[200001], d[200001], mx[200001], szm[200001], kek[200001];
multiset<pair<long long, long long>> ms;
int mxx;
bool st1, st2;
vector<pair<long long, long long>> g[200001];
vector<pair<long long, pair<long long, long long>>> gg;

long long get(long long x) {
	return x == p[x] ? x : p[x] = get(p[x]);
}

void merge(long long xx, long long yy) {
	long long x = get(xx), y = get(yy);
	mx[x] = max({mx[x], d[x], d[xx]});
	mx[y] = max({mx[y], d[y], d[yy]});
	mx[x] = max(mx[x], mx[y]);
	mx[y] = max(mx[y], mx[x]);
	szm[x]++;
	if (x == y) return;
	if (sz[x] < sz[y]) swap(x, y);
	p[y] = x;
	sz[x] += sz[y];
	szm[x] += szm[y];
	mx[x] = max(mx[x], mx[y]);
	mx[y] = max(mx[y], mx[x]);
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N, m = M;
	st2 = 1;
	for (long long i = 0; i < M; i++) {
		g[U[i]].push_back({V[i], W[i]});
		g[V[i]].push_back({U[i], W[i]});
		if (U[i]) {
			st2 = 0;
		}
		gg.push_back({W[i], {U[i], V[i]}});
		kek[V[i]] = W[i];
		mxx = max(mxx, W[i]);
	}
	if (st2) {
		for (long long i = 0; i < N; i++) ms.insert({kek[i], i});
	}
	st1 = 1;
	for (long long i = 0; i < N; i++) {
		if (g[i].size() > 2) st1 = 0;
	}
	sort(gg.begin(), gg.end());
}

bool check(long long md, long long x, long long y) {
	if (md < 0 || md >= gg.size()) return 0;
	for (long long i = 0; i < n; i++) sz[i] = 1, p[i] = i, d[i] = mx[i] = szm[i] = 0;
	for (long long i = 0; i <= md; i++) {
		d[gg[i].second.first]++;
		d[gg[i].second.second]++;
		merge(gg[i].second.first, gg[i].second.second);
	}
	if (get(x) != get(y)) return 0;
	if (mx[get(x)] <= 2 && szm[get(x)] < sz[get(x)]) return 0;
	return 1;
}

int getMinimumFuelCapacity(int X, int Y) {
	if (st1) {
		if (n == m) return mxx;
		return -1;
	}
	if (st2) {
		if (ms.size() > 2) {
			ms.erase({kek[X], X});
			ms.erase({kek[Y], Y});
			long long ans = max({kek[X], kek[Y], (*ms.begin()).first});
			ms.insert({kek[X], X});
			ms.insert({kek[Y], Y});
			return ans;
		}
		return -1;
	}
	long long l = 0, r = (int)gg.size(), md, ans = 0;
	while (l <= r) {
		md = (l + r) / 2;
		if (check(md, X, Y)) ans = md, r = md - 1;
		else l = md + 1;
	}
	if (!check(ans, X, Y)) return -1;
  return gg[ans].first;
}

Compilation message

swap.cpp: In function 'bool check(long long int, long long int, long long int)':
swap.cpp:57:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  if (md < 0 || md >= gg.size()) return 0;
      |                ~~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6772 KB Output is correct
8 Correct 2 ms 6836 KB Output is correct
9 Correct 41 ms 15080 KB Output is correct
10 Correct 49 ms 16904 KB Output is correct
11 Correct 49 ms 16000 KB Output is correct
12 Correct 65 ms 16644 KB Output is correct
13 Correct 50 ms 16644 KB Output is correct
14 Correct 44 ms 15348 KB Output is correct
15 Correct 96 ms 18728 KB Output is correct
16 Correct 102 ms 17696 KB Output is correct
17 Correct 91 ms 18540 KB Output is correct
18 Correct 120 ms 18480 KB Output is correct
19 Correct 48 ms 11604 KB Output is correct
20 Correct 89 ms 19348 KB Output is correct
21 Correct 92 ms 20008 KB Output is correct
22 Correct 99 ms 19760 KB Output is correct
23 Correct 100 ms 19724 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 272 ms 24500 KB Output is correct
4 Correct 265 ms 29080 KB Output is correct
5 Incorrect 290 ms 29088 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6772 KB Output is correct
8 Correct 2 ms 6836 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 4 ms 12892 KB Output is correct
13 Correct 4 ms 12892 KB Output is correct
14 Correct 4 ms 12892 KB Output is correct
15 Correct 4 ms 12888 KB Output is correct
16 Correct 4 ms 12892 KB Output is correct
17 Correct 4 ms 12892 KB Output is correct
18 Correct 3 ms 12888 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 3 ms 13076 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 3 ms 12892 KB Output is correct
24 Correct 4 ms 12892 KB Output is correct
25 Correct 4 ms 12892 KB Output is correct
26 Correct 4 ms 12892 KB Output is correct
27 Correct 3 ms 12888 KB Output is correct
28 Correct 4 ms 12888 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6772 KB Output is correct
9 Correct 2 ms 6836 KB Output is correct
10 Correct 41 ms 15080 KB Output is correct
11 Correct 49 ms 16904 KB Output is correct
12 Correct 49 ms 16000 KB Output is correct
13 Correct 65 ms 16644 KB Output is correct
14 Correct 50 ms 16644 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 4 ms 12892 KB Output is correct
18 Correct 4 ms 12892 KB Output is correct
19 Correct 4 ms 12892 KB Output is correct
20 Correct 4 ms 12888 KB Output is correct
21 Correct 4 ms 12892 KB Output is correct
22 Correct 4 ms 12892 KB Output is correct
23 Correct 3 ms 12888 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12892 KB Output is correct
26 Correct 3 ms 13076 KB Output is correct
27 Correct 3 ms 12892 KB Output is correct
28 Correct 3 ms 12892 KB Output is correct
29 Correct 4 ms 12892 KB Output is correct
30 Correct 4 ms 12892 KB Output is correct
31 Correct 4 ms 12892 KB Output is correct
32 Correct 3 ms 12888 KB Output is correct
33 Correct 4 ms 12888 KB Output is correct
34 Correct 12 ms 14232 KB Output is correct
35 Correct 355 ms 22484 KB Output is correct
36 Correct 378 ms 22632 KB Output is correct
37 Correct 335 ms 22452 KB Output is correct
38 Correct 338 ms 22332 KB Output is correct
39 Correct 343 ms 22300 KB Output is correct
40 Correct 310 ms 21632 KB Output is correct
41 Correct 371 ms 22468 KB Output is correct
42 Correct 369 ms 22464 KB Output is correct
43 Correct 190 ms 22468 KB Output is correct
44 Correct 365 ms 22536 KB Output is correct
45 Correct 293 ms 26684 KB Output is correct
46 Correct 364 ms 22380 KB Output is correct
47 Correct 336 ms 23176 KB Output is correct
48 Correct 322 ms 23272 KB Output is correct
49 Correct 69 ms 28860 KB Output is correct
50 Correct 66 ms 23868 KB Output is correct
51 Correct 210 ms 24624 KB Output is correct
52 Correct 417 ms 29576 KB Output is correct
53 Correct 357 ms 31132 KB Output is correct
54 Correct 418 ms 32152 KB Output is correct
55 Correct 245 ms 22372 KB Output is correct
56 Correct 416 ms 29964 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6772 KB Output is correct
8 Correct 2 ms 6836 KB Output is correct
9 Correct 41 ms 15080 KB Output is correct
10 Correct 49 ms 16904 KB Output is correct
11 Correct 49 ms 16000 KB Output is correct
12 Correct 65 ms 16644 KB Output is correct
13 Correct 50 ms 16644 KB Output is correct
14 Correct 44 ms 15348 KB Output is correct
15 Correct 96 ms 18728 KB Output is correct
16 Correct 102 ms 17696 KB Output is correct
17 Correct 91 ms 18540 KB Output is correct
18 Correct 120 ms 18480 KB Output is correct
19 Correct 272 ms 24500 KB Output is correct
20 Correct 265 ms 29080 KB Output is correct
21 Incorrect 290 ms 29088 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6772 KB Output is correct
9 Correct 2 ms 6836 KB Output is correct
10 Correct 41 ms 15080 KB Output is correct
11 Correct 49 ms 16904 KB Output is correct
12 Correct 49 ms 16000 KB Output is correct
13 Correct 65 ms 16644 KB Output is correct
14 Correct 50 ms 16644 KB Output is correct
15 Correct 44 ms 15348 KB Output is correct
16 Correct 96 ms 18728 KB Output is correct
17 Correct 102 ms 17696 KB Output is correct
18 Correct 91 ms 18540 KB Output is correct
19 Correct 120 ms 18480 KB Output is correct
20 Correct 272 ms 24500 KB Output is correct
21 Correct 265 ms 29080 KB Output is correct
22 Incorrect 290 ms 29088 KB Output isn't correct
23 Halted 0 ms 0 KB -