oj.uz

Submission #396466

# Submission time Handle Problem Language Result Execution time Memory
396466 2021-04-30T02:07:43 Z Kevin_Zhang_TW Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 8772 KB 
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010, inf = 1e9 + 7;

struct dsu {
	vector<int> g, sz, good;
	dsu(int n) { g.resize(n), sz.resize(n, 1), good.resize(n); iota(AI(g), 0); }
	int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
	void M(int a, int b) {
		a = F(a), b = F(b);
		if (a == b) return good[a] = true, void();
		if (sz[a] < sz[b]) swap(a, b);
		return g[b] = a, sz[a] += sz[b], good[a] |= good[b], void();
	}
	bool qry(int a, int b) {
		if (F(a) != F(b)) return false;
		return good[F(a)];
	}
};
int n, m;
vector<tuple<int,int,int>> alle;

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) {
		alle.pb(W[i], U[i], V[i]);
	}
	sort(AI(alle));
}

int getMinimumFuelCapacity(int X, int Y) {

	dsu D(n);
	for (auto [w, a, b] : alle) {
		D.M(a, b);
		if (D.qry(X, Y)) return w;
	}
	return -1;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 43 ms 5436 KB Output is correct
10 Correct 65 ms 6204 KB Output is correct
11 Correct 67 ms 6128 KB Output is correct
12 Correct 68 ms 6316 KB Output is correct
13 Correct 63 ms 6340 KB Output is correct
14 Execution timed out 2098 ms 5772 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Execution timed out 2083 ms 8772 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Incorrect 1 ms 332 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 43 ms 5436 KB Output is correct
11 Correct 65 ms 6204 KB Output is correct
12 Correct 67 ms 6128 KB Output is correct
13 Correct 68 ms 6316 KB Output is correct
14 Correct 63 ms 6340 KB Output is correct
15 Incorrect 1 ms 332 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 43 ms 5436 KB Output is correct
10 Correct 65 ms 6204 KB Output is correct
11 Correct 67 ms 6128 KB Output is correct
12 Correct 68 ms 6316 KB Output is correct
13 Correct 63 ms 6340 KB Output is correct
14 Execution timed out 2098 ms 5772 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 208 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 43 ms 5436 KB Output is correct
11 Correct 65 ms 6204 KB Output is correct
12 Correct 67 ms 6128 KB Output is correct
13 Correct 68 ms 6316 KB Output is correct
14 Correct 63 ms 6340 KB Output is correct
15 Execution timed out 2098 ms 5772 KB Time limit exceeded
16 Halted 0 ms 0 KB -