oj.uz

Submission #981894

# Submission time Handle Problem Language Result Execution time Memory
981894 2024-05-13T16:09:27 Z vjudge1 Swapping Cities (APIO20_swap) C++17
43 / 100
 2000 ms 34260 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];
int mxx;
bool st1;
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;
	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]});
		gg.push_back({W[i], {U[i], V[i]}});
		mxx = max(mxx, W[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;
	}
	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:48: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]
   48 |  if (md < 0 || md >= gg.size()) return 0;
      |                ~~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6760 KB Output is correct
3 Correct 2 ms 6772 KB Output is correct
4 Correct 2 ms 6752 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 38 ms 16776 KB Output is correct
10 Correct 50 ms 18436 KB Output is correct
11 Correct 47 ms 18928 KB Output is correct
12 Correct 52 ms 18700 KB Output is correct
13 Correct 48 ms 18704 KB Output is correct
14 Correct 43 ms 18496 KB Output is correct
15 Correct 89 ms 22388 KB Output is correct
16 Correct 88 ms 22452 KB Output is correct
17 Correct 111 ms 22796 KB Output is correct
18 Correct 89 ms 23404 KB Output is correct
19 Correct 44 ms 13712 KB Output is correct
20 Correct 88 ms 24196 KB Output is correct
21 Correct 93 ms 23840 KB Output is correct
22 Correct 95 ms 24168 KB Output is correct
23 Correct 100 ms 24972 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6760 KB Output is correct
3 Execution timed out 2096 ms 27092 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6760 KB Output is correct
3 Correct 2 ms 6772 KB Output is correct
4 Correct 2 ms 6752 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 12888 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 13052 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 4 ms 13148 KB Output is correct
15 Correct 3 ms 12900 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 3 ms 12900 KB Output is correct
18 Correct 3 ms 12892 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 12892 KB Output is correct
22 Correct 3 ms 13132 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 13148 KB Output is correct
26 Correct 4 ms 13148 KB Output is correct
27 Correct 3 ms 12892 KB Output is correct
28 Correct 4 ms 13148 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6760 KB Output is correct
4 Correct 2 ms 6772 KB Output is correct
5 Correct 2 ms 6752 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 38 ms 16776 KB Output is correct
11 Correct 50 ms 18436 KB Output is correct
12 Correct 47 ms 18928 KB Output is correct
13 Correct 52 ms 18700 KB Output is correct
14 Correct 48 ms 18704 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 3 ms 13052 KB Output is correct
18 Correct 3 ms 12892 KB Output is correct
19 Correct 4 ms 13148 KB Output is correct
20 Correct 3 ms 12900 KB Output is correct
21 Correct 3 ms 12892 KB Output is correct
22 Correct 3 ms 12900 KB Output is correct
23 Correct 3 ms 12892 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 12892 KB Output is correct
27 Correct 3 ms 13132 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 13148 KB Output is correct
31 Correct 4 ms 13148 KB Output is correct
32 Correct 3 ms 12892 KB Output is correct
33 Correct 4 ms 13148 KB Output is correct
34 Correct 13 ms 14488 KB Output is correct
35 Correct 358 ms 23436 KB Output is correct
36 Correct 334 ms 23340 KB Output is correct
37 Correct 363 ms 23400 KB Output is correct
38 Correct 320 ms 23360 KB Output is correct
39 Correct 342 ms 23312 KB Output is correct
40 Correct 314 ms 23376 KB Output is correct
41 Correct 353 ms 24320 KB Output is correct
42 Correct 378 ms 24020 KB Output is correct
43 Correct 208 ms 23948 KB Output is correct
44 Correct 368 ms 24456 KB Output is correct
45 Correct 334 ms 30672 KB Output is correct
46 Correct 359 ms 23404 KB Output is correct
47 Correct 371 ms 23528 KB Output is correct
48 Correct 332 ms 24536 KB Output is correct
49 Correct 80 ms 32948 KB Output is correct
50 Correct 70 ms 26056 KB Output is correct
51 Correct 261 ms 26832 KB Output is correct
52 Correct 395 ms 32652 KB Output is correct
53 Correct 353 ms 33728 KB Output is correct
54 Correct 427 ms 34260 KB Output is correct
55 Correct 210 ms 23912 KB Output is correct
56 Correct 410 ms 31732 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6760 KB Output is correct
3 Correct 2 ms 6772 KB Output is correct
4 Correct 2 ms 6752 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 38 ms 16776 KB Output is correct
10 Correct 50 ms 18436 KB Output is correct
11 Correct 47 ms 18928 KB Output is correct
12 Correct 52 ms 18700 KB Output is correct
13 Correct 48 ms 18704 KB Output is correct
14 Correct 43 ms 18496 KB Output is correct
15 Correct 89 ms 22388 KB Output is correct
16 Correct 88 ms 22452 KB Output is correct
17 Correct 111 ms 22796 KB Output is correct
18 Correct 89 ms 23404 KB Output is correct
19 Execution timed out 2096 ms 27092 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6760 KB Output is correct
4 Correct 2 ms 6772 KB Output is correct
5 Correct 2 ms 6752 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 38 ms 16776 KB Output is correct
11 Correct 50 ms 18436 KB Output is correct
12 Correct 47 ms 18928 KB Output is correct
13 Correct 52 ms 18700 KB Output is correct
14 Correct 48 ms 18704 KB Output is correct
15 Correct 43 ms 18496 KB Output is correct
16 Correct 89 ms 22388 KB Output is correct
17 Correct 88 ms 22452 KB Output is correct
18 Correct 111 ms 22796 KB Output is correct
19 Correct 89 ms 23404 KB Output is correct
20 Execution timed out 2096 ms 27092 KB Time limit exceeded
21 Halted 0 ms 0 KB -