#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 |
- |