oj.uz

답안 #396467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
396467 2021-04-30T02:21:43 Z Kevin_Zhang_TW 자매 도시 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -