oj.uz

Submission #981738

# Submission time Handle Problem Language Result Execution time Memory
981738 2024-05-13T13:59:24 Z vjudge1 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 16596 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) {
	d[xx]++, d[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]});
	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++) merge(gg[i].second.first, gg[i].second.second);
	if (get(x) != get(y)) return 0;
	if (mx[get(x)] < 1) 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 = gg.size() - 1, md;
	while (l <= r) {
		md = (l + r) / 2;
		if (check(md, X, Y)) r = md - 1;
		else l = md + 1;
	}
	if (!check(l, X, Y)) return -1;
  return gg[l].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 2 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4752 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 103 ms 14536 KB Output is correct
10 Correct 208 ms 14884 KB Output is correct
11 Correct 255 ms 14816 KB Output is correct
12 Correct 265 ms 15648 KB Output is correct
13 Correct 213 ms 15460 KB Output is correct
14 Execution timed out 2059 ms 13240 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4752 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 2 ms 4696 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 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 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 3 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 4752 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 103 ms 14536 KB Output is correct
11 Correct 208 ms 14884 KB Output is correct
12 Correct 255 ms 14816 KB Output is correct
13 Correct 265 ms 15648 KB Output is correct
14 Correct 213 ms 15460 KB Output is correct
15 Correct 2 ms 4696 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 2 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4752 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 103 ms 14536 KB Output is correct
10 Correct 208 ms 14884 KB Output is correct
11 Correct 255 ms 14816 KB Output is correct
12 Correct 265 ms 15648 KB Output is correct
13 Correct 213 ms 15460 KB Output is correct
14 Execution timed out 2059 ms 13240 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 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 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 3 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 4752 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 103 ms 14536 KB Output is correct
11 Correct 208 ms 14884 KB Output is correct
12 Correct 255 ms 14816 KB Output is correct
13 Correct 265 ms 15648 KB Output is correct
14 Correct 213 ms 15460 KB Output is correct
15 Execution timed out 2059 ms 13240 KB Time limit exceeded
16 Halted 0 ms 0 KB -