oj.uz

답안 #401656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401656 2021-05-10T16:10:35 Z hoaphat1 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 8272 KB 
#include<bits/stdc++.h>
 
using namespace std;

struct dsu {
	vector<int> p;
	int n;
	dsu(int n) {
		resize(n);
	}
	dsu() {
	}
	void resize(int _n) {
		n = _n;
		p = vector<int> (n, -1);
	}
	int get(int x) {
		return p[x] < 0 ? x : p[x] = get(p[x]);
	}
	bool unite(int x, int y) {
		x = get(x); y = get(y);
		if (x != y) {
			if (p[x] < p[y]) swap(x, y);
			p[y] += p[x];
			p[x] = y;
			return true;
		}
		return false;
	}
} d;

const int N = 1e5 + 3;
int n, m;
vector<tuple<int,int,int>> edges;
int deg[N];
vector<int> event[N];
bool can[N];

void init(int _n, int _m, vector<int> u, vector<int> v, vector<int> w) {
	n = _n;
	m = _m;
	for (int i = 0; i < m; i++) edges.emplace_back(w[i], u[i], v[i]);
	sort(edges.begin(), edges.end());
	/*d.resize(n);
	for (auto&x : edges) {
		deg[get<1>(x)]++;
		deg[get<2>(x)]++;
		int u = d.get(get<1>(x)), v = d.get(get<2>(x));
		if (u == v) {
			if (!can[u]) {
				event[u].emplace_back(get<0>(x));
				can[u] = true;
			}
		}
		else {
			d.unite(u, v);
			if (u != d.get(u)) swap(u, v);
			
		}
	}*/
}

int getMinimumFuelCapacity(int X, int Y) {
	d.resize(n);
	for (int i = 0; i < n; i++) deg[i] = 0, can[i] = false;
	for (auto&x : edges) {
		++deg[get<1>(x)];
		++deg[get<2>(x)];
		int u = d.get(get<1>(x)), v = d.get(get<2>(x));
		if (u == v) {
			can[u] = true;
		}
		else {
			d.unite(u, v);
			if (deg[get<1>(x)] >= 3 || deg[get<2>(x)] >= 3) {
				can[d.get(u)] = true;
			}
		}
		if (d.get(X) == d.get(Y) && can[d.get(X)]) return get<0>(x);
	}
	return -1;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 42 ms 6136 KB Output is correct
10 Correct 63 ms 6456 KB Output is correct
11 Correct 64 ms 6448 KB Output is correct
12 Correct 76 ms 6588 KB Output is correct
13 Correct 60 ms 6588 KB Output is correct
14 Execution timed out 2086 ms 6264 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Execution timed out 2066 ms 8272 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Incorrect 3 ms 2636 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Correct 42 ms 6136 KB Output is correct
11 Correct 63 ms 6456 KB Output is correct
12 Correct 64 ms 6448 KB Output is correct
13 Correct 76 ms 6588 KB Output is correct
14 Correct 60 ms 6588 KB Output is correct
15 Correct 3 ms 2636 KB Output is correct
16 Incorrect 3 ms 2636 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 42 ms 6136 KB Output is correct
10 Correct 63 ms 6456 KB Output is correct
11 Correct 64 ms 6448 KB Output is correct
12 Correct 76 ms 6588 KB Output is correct
13 Correct 60 ms 6588 KB Output is correct
14 Execution timed out 2086 ms 6264 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Correct 42 ms 6136 KB Output is correct
11 Correct 63 ms 6456 KB Output is correct
12 Correct 64 ms 6448 KB Output is correct
13 Correct 76 ms 6588 KB Output is correct
14 Correct 60 ms 6588 KB Output is correct
15 Execution timed out 2086 ms 6264 KB Time limit exceeded
16 Halted 0 ms 0 KB -