oj.uz

Submission #981822

# Submission time Handle Problem Language Result Execution time Memory
981822 2024-05-13T15:24:40 Z vjudge1 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 20236 KB 
#include "swap.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
long long n, m, i, j, sz[100001], p[100001], d[100001], mx[100001], szm[100001];
vector<pair<long long, long long>> g[100001];
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]);
	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];
}

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]}});
	}
	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) {
	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:38: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]
   38 |  if (md < 0 || md >= gg.size()) return 0;
      |                ~~~^~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4720 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4704 KB Output is correct
7 Correct 2 ms 4696 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 107 ms 16204 KB Output is correct
10 Correct 210 ms 17144 KB Output is correct
11 Correct 250 ms 16820 KB Output is correct
12 Correct 268 ms 18096 KB Output is correct
13 Correct 197 ms 17512 KB Output is correct
14 Execution timed out 2039 ms 15108 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4720 KB Output is correct
3 Execution timed out 2084 ms 20236 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4720 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4704 KB Output is correct
7 Correct 2 ms 4696 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 1 ms 4696 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct
11 Incorrect 2 ms 4700 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4720 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4704 KB Output is correct
8 Correct 2 ms 4696 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 107 ms 16204 KB Output is correct
11 Correct 210 ms 17144 KB Output is correct
12 Correct 250 ms 16820 KB Output is correct
13 Correct 268 ms 18096 KB Output is correct
14 Correct 197 ms 17512 KB Output is correct
15 Correct 2 ms 4700 KB Output is correct
16 Incorrect 2 ms 4700 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4720 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4704 KB Output is correct
7 Correct 2 ms 4696 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 107 ms 16204 KB Output is correct
10 Correct 210 ms 17144 KB Output is correct
11 Correct 250 ms 16820 KB Output is correct
12 Correct 268 ms 18096 KB Output is correct
13 Correct 197 ms 17512 KB Output is correct
14 Execution timed out 2039 ms 15108 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4720 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4704 KB Output is correct
8 Correct 2 ms 4696 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 107 ms 16204 KB Output is correct
11 Correct 210 ms 17144 KB Output is correct
12 Correct 250 ms 16820 KB Output is correct
13 Correct 268 ms 18096 KB Output is correct
14 Correct 197 ms 17512 KB Output is correct
15 Execution timed out 2039 ms 15108 KB Time limit exceeded
16 Halted 0 ms 0 KB -