# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1054421 | Kipras | Spring cleaning (CEOI20_cleaning) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#include "swap.h"
const ll maxN = 1e5+10;
ll par[maxN], timeP[maxN], cycle[maxN], sz[maxN];
ll n, m;
vector<ll> adj[maxN];
vector<pair<ll, pair<ll, ll>>> edges;
ll find(ll node, ll t) {
if(timeP[node]<=t) {
return find(par[node], t);
}
return node;
}
void unite(ll a, ll b, ll t, bool is){
a = find(a, t);
b = find(b, t);
if(a==b){
cycle[a]=t;
cycle[b]=t;
return;
}
if(sz[a]>sz[b]) {
swap(a, b);
}
if(cycle[a]==0&&cycle[b]!=0)
cycle[a]=cycle[b];
else if(cycle[b]==0&&cycle[a]!=0)
cycle[b]=cycle[a];
if(is) {
if(cycle[a]==0)cycle[a]=t;
if(cycle[b]==0)cycle[b]=t;
}
sz[b]+=sz[a];
par[a]=b;
timeP[a]=t;
}
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.push_back({W[i], {U[i], V[i]}});
}
for(int i = 1; i <= n; i++) {
par[i]=i;
sz[i]=1;
}
sort(edges.begin(), edges.end());
for(auto i : edges) {
ll v = i.second.first, u = i.second.second;
ll w = i.first;
adj[v].push_back(u);
adj[u].push_back(v);
bool is = 0;
if(adj[v].size()>2||adj[u].size()>2)is=1;
unite(v, u, w, is);
}
}
int getMinimumFuelCapacity(int X, int Y) {
ll l = 0, h = 1e18;
while(l < h && l < 1e10) {
ll m = (l+h)/2;
ll v1 = find(X, m), v2 = find(Y, m);
if(v1==v2&&cycle[v1]<=m) {
h=l;
}else l = h+1;
}
if(h>1e10) {
return -1;
}else return l;
}