#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i>=(k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
typedef long long ll;
const int INF = (int)1e9 + 7;
const ll INFF = (ll)1e18;
int n, m;
vector<vector<array<int, 2>>> merge_history;// ked sa mensi mergne do vacsieho, zapamatam si ze mensi -> merge vacsi; max logn krat sa potom nieco mergne; usortim podla casov;
// when comp became good
vector<int> good_history;
struct dsu{
vector<int> p;
vector<bool> good;
vector<int> deg;
int counter = -1;
dsu(int n){
deg.resize(n, 0);
p.resize(n, -1);
good.resize(n, false);
}
int find(int x){
return (p[x] < 0 ? x : p[x] = find(p[x]));
}
bool same_set(int u, int v){
return find(u) == find(v);
}
bool join(int u, int v){
counter++;
deg[u]++; deg[v]++;
bool dgood = ((deg[u] > 2 || deg[v] > 2) ? true : false);
u = find(u);
v = find(v);
if(u == v){
if(!good[u]){
good_history[u] = counter;
good[u] = true;
}
return false;
}
if(-p[u] < -p[v])
swap(u, v);
if(!good[u] && (dgood || good[v])){
good[u] = true;
good_history[u] = counter;
}
p[u] += p[v]; p[v] = u;
merge_history[v].pb({counter, u});
return true;
}
};
vector<array<int, 3>> edges;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N; m = M;
good_history.resize(n, -1);
merge_history.resize(n);
REP(i, m){
edges.pb({W[i], U[i], V[i]});
}
sort(edges.begin(), edges.end());
dsu d(n);
int id = 0;
for(auto e : edges){
d.join(e[1], e[2]);
}
}
int getMinimumFuelCapacity(int u, int v) {
int nres;
if(m == n - 1){
nres = -1;
}
else{
nres = edges.back()[0];
}
int ans = INF;
int curr_time = 0;
bool fn = false;
while(true){
array<int, 2> tm = {curr_time, -1};
auto it = lower_bound(merge_history[u].begin(), merge_history[u].end(), tm);
auto it2 = lower_bound(merge_history[v].begin(), merge_history[v].end(), tm);
int tf = INF;
int ts = INF;
if(it != merge_history[u].end())
tf = (*it)[0];
if(it2 != merge_history[v].end())
ts = (*it2)[0];
if(tf == ts && tf == INF)
break;
if(tf < ts){
curr_time = tf + 1;
u = (*it)[1];
}
else{
curr_time = ts + 1;
v = (*it2)[1];
}
if(u == v){
if(good_history[u] != -1){
fn = true;
ans = min(ans, max(edges[good_history[u]][0], edges[curr_time - 1][0]));
}
}
}
if(ans == INF){
assert((nres == -1 && fn));
}
if(ans == INF)
return -1;
return ans;
}
Compilation message
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:67:9: warning: unused variable 'id' [-Wunused-variable]
67 | int id = 0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
