oj.uz

Submission #396467

# Submission time Handle Problem Language Result Execution time Memory
396467 2021-04-30T02:21:43 Z Kevin_Zhang_TW Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 5792 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) {
		return F(a) == F(b) && 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 204 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 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 41 ms 3776 KB Output is correct
10 Correct 60 ms 4156 KB Output is correct
11 Correct 62 ms 4084 KB Output is correct
12 Correct 65 ms 4284 KB Output is correct
13 Correct 59 ms 4280 KB Output is correct
14 Execution timed out 2072 ms 3908 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 2095 ms 5792 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 204 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 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 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 204 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 204 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 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 41 ms 3776 KB Output is correct
11 Correct 60 ms 4156 KB Output is correct
12 Correct 62 ms 4084 KB Output is correct
13 Correct 65 ms 4284 KB Output is correct
14 Correct 59 ms 4280 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 204 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 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 41 ms 3776 KB Output is correct
10 Correct 60 ms 4156 KB Output is correct
11 Correct 62 ms 4084 KB Output is correct
12 Correct 65 ms 4284 KB Output is correct
13 Correct 59 ms 4280 KB Output is correct
14 Execution timed out 2072 ms 3908 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 204 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 204 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 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 41 ms 3776 KB Output is correct
11 Correct 60 ms 4156 KB Output is correct
12 Correct 62 ms 4084 KB Output is correct
13 Correct 65 ms 4284 KB Output is correct
14 Correct 59 ms 4280 KB Output is correct
15 Execution timed out 2072 ms 3908 KB Time limit exceeded
16 Halted 0 ms 0 KB -