답안 #568802

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
568802 2022-05-26T08:22:09 Z _karan_gandhi 자매 도시 (APIO20_swap) C++17
0 / 100
2000 ms 15516 KB
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }

struct DSU { // Sorry UFDS
	vector<int> p, s, degree;
	vector<bool> swappable;
	int components;

	void init(int n) {
		p = vector<int>(n);
		iota(all(p), 0);
		s = vector<int>(n, 1);
		swappable = vector<bool>(n, 0);
		degree = vector<int>(n, 0);
		components = n;
	}

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

	void unite(int a, int b) {
		degree[a]++;
		degree[b]++;
		bool _swappable = 0;
		if (degree[a] >= 3 || degree[b] >= 3) _swappable = 1;

		a = get(a);
		b = get(b);

		if (a == b) {
			swappable[a] = 1;
			return;
		}

		if (s[a] > s[b]) swap(a, b);


		p[a] = b;
		s[b] += s[a];
		swappable[a] = (swappable[a] | swappable[b] | _swappable);
		components--;
	}

	bool same_set(int a, int b) {
		return get(a) == get(b);
	}

	int size(int x) {
		return s[get(x)];
	}
};

int n, m;
vector<vector<pair<int, int>>> adj;
vector<pair<int, pair<int, int>>> edges;
int inf = 1e9 + 7;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N;
	m = M;
	adj.resize(n);

	for (int i = 0; i < m; i++) {
		adj[U[i]].emplace_back(V[i], W[i]);
		adj[V[i]].emplace_back(U[i], W[i]);
		edges.emplace_back(W[i], make_pair(U[i], V[i]));
	}

	sort(all(edges));
}

int getMinimumFuelCapacity(int x, int y) {
	int ptr = 0;
	DSU dsu;
	dsu.init(n);
	// cout << pl(x) << pl(y) << endl;
	while ( (!dsu.same_set(x, y) || 
			(!dsu.swappable[dsu.get(x)])) && 
			 // !dsu.swappable[dsu.get(y)])) && 
			 ptr < m) {
		
		// cout << pl(ptr) << pl(dsu.swappable) << pl(dsu.p) << pl(dsu.degree) << endl;
		// cout << pl(edges[ptr]) << endl;
		dsu.unite(edges[ptr].second.first, edges[ptr].second.second);
		ptr++;
	}
	// cout << pl(ptr) << pl(dsu.swappable) << pl(dsu.p) << pl(dsu.degree) << endl;

	if ((!dsu.same_set(x, y) || (!dsu.swappable[dsu.get(x)]))) return -1;
	// if (ptr == m && !dsu.swappable[dsu) return -1;

	return edges[ptr - 1].first;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 78 ms 9492 KB Output is correct
10 Correct 109 ms 11000 KB Output is correct
11 Correct 88 ms 10888 KB Output is correct
12 Correct 86 ms 11428 KB Output is correct
13 Correct 100 ms 11376 KB Output is correct
14 Execution timed out 2051 ms 9844 KB Time limit exceeded
15 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 2074 ms 15516 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Incorrect 2 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 78 ms 9492 KB Output is correct
11 Correct 109 ms 11000 KB Output is correct
12 Correct 88 ms 10888 KB Output is correct
13 Correct 86 ms 11428 KB Output is correct
14 Correct 100 ms 11376 KB Output is correct
15 Incorrect 2 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 78 ms 9492 KB Output is correct
10 Correct 109 ms 11000 KB Output is correct
11 Correct 88 ms 10888 KB Output is correct
12 Correct 86 ms 11428 KB Output is correct
13 Correct 100 ms 11376 KB Output is correct
14 Execution timed out 2051 ms 9844 KB Time limit exceeded
15 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 78 ms 9492 KB Output is correct
11 Correct 109 ms 11000 KB Output is correct
12 Correct 88 ms 10888 KB Output is correct
13 Correct 86 ms 11428 KB Output is correct
14 Correct 100 ms 11376 KB Output is correct
15 Execution timed out 2051 ms 9844 KB Time limit exceeded
16 Halted 0 ms 0 KB -