oj.uz

Submission #981735

# Submission time Handle Problem Language Result Execution time Memory
981735 2024-05-13T13:57:43 Z vjudge1 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 13240 KB 
#include "swap.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int n, m, i, j, sz[100001], p[100001], d[100001], mx[100001], szm[100001];
vector<pair<int, int>> g[100001];
vector<pair<int, pair<int, int>>> gg;

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

void merge(int xx, int yy) {
	d[xx]++, d[yy]++;
	int 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 (int 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(int md, int x, int y) {
	if (md < 0 || md >= gg.size()) return 0;
	for (int i = 0; i <= n; i++) sz[i] = 1, p[i] = i, d[i] = mx[i] = szm[i] = 0;
	for (int 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) {
	int 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(int, int, int)':
swap.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, 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 4700 KB Output is correct
2 Correct 2 ms 4696 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 4700 KB Output is correct
7 Correct 2 ms 4696 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 94 ms 10516 KB Output is correct
10 Correct 204 ms 11152 KB Output is correct
11 Correct 235 ms 11004 KB Output is correct
12 Correct 264 ms 11284 KB Output is correct
13 Correct 198 ms 11284 KB Output is correct
14 Execution timed out 2073 ms 10440 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 4700 KB Output is correct
2 Correct 2 ms 4696 KB Output is correct
3 Execution timed out 2041 ms 13240 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 4700 KB Output is correct
2 Correct 2 ms 4696 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 4700 KB Output is correct
7 Correct 2 ms 4696 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 1 ms 4700 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 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 2 ms 4696 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 4700 KB Output is correct
8 Correct 2 ms 4696 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 94 ms 10516 KB Output is correct
11 Correct 204 ms 11152 KB Output is correct
12 Correct 235 ms 11004 KB Output is correct
13 Correct 264 ms 11284 KB Output is correct
14 Correct 198 ms 11284 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 4700 KB Output is correct
2 Correct 2 ms 4696 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 4700 KB Output is correct
7 Correct 2 ms 4696 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 94 ms 10516 KB Output is correct
10 Correct 204 ms 11152 KB Output is correct
11 Correct 235 ms 11004 KB Output is correct
12 Correct 264 ms 11284 KB Output is correct
13 Correct 198 ms 11284 KB Output is correct
14 Execution timed out 2073 ms 10440 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 1 ms 4700 KB Output is correct
3 Correct 2 ms 4696 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 4700 KB Output is correct
8 Correct 2 ms 4696 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 94 ms 10516 KB Output is correct
11 Correct 204 ms 11152 KB Output is correct
12 Correct 235 ms 11004 KB Output is correct
13 Correct 264 ms 11284 KB Output is correct
14 Correct 198 ms 11284 KB Output is correct
15 Execution timed out 2073 ms 10440 KB Time limit exceeded
16 Halted 0 ms 0 KB -