| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 498163 | XII | Race (IOI11_race) | 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>
#include <race.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "IOI11_race"
void Fi(){
if(fopen(PROB".inp", "r")){
freopen(PROB".inp", "r", stdin);
freopen(PROB".out", "w", stdout);
}
}
const int INF = 1e9;
const int N = 2e5 + 1;
const int K = 1e6 + 1;
//int n, k;
using pi = pair<int, int>;
//vector<pi> adj[N];
//multiset<pi> s[N];
int ans = INF;
//void dfs(int u, int p = -1){
// s[u].insert({0, 0});
// for(auto [w, v]: adj[u]) if(v != p){
// dfs(v, u);
// for(auto p: s[v]) if(p.fi + w <= k){
// s[u].insert({p.fi + w, p.se + 1});
// } else break;
// }
// for(auto [w, v]: adj[u]) if(v != p){
// for(auto p: s[v]) if(p.fi + w <= k){
// s[u].erase(s[u].find({p.fi + w, p.se + 1}));
// } else break;
// for(auto p: s[v]) if(p.fi + w <= k){
// auto it = s[u].lower_bound({k - (p.fi + w), -1});
// if(it == s[u].end()) continue;
// if((*it).fi == k - (p.fi + w)){
// ans = min(ans, p.se + 1 + (*it).se);
// }
// } else break;
// for(auto p: s[v]) if(p.fi + w <= k){
// s[u].insert({p.fi + w, p.se + 1});
// } else break;
// }
//}
int sz[N];
set<pi> G[N];
int dfsSize(int u, int p = -1){
sz[u] = 1;
for(auto [w, v]: G[u]) if(v != p){
sz[u] += dfsSize(v, u);
}
return sz[u];
}
int centroid(int u, int p, int n){
for(auto [w, v]: G[u]) if(v != p){
if(sz[v] > n / 2) return centroid(v, u, n);
}
return u;
}
multiset<pi> s[N];
void dfs(int u, int p){
s[u].insert({0, 0});
for(auto [w, v]: G[u]) if(v != p){
dfs(v, u);
for(auto x: s[v]) if(x.fi + w <= k){
s[u].insert({x.fi + w, x.se + 1});
} else break;
s[v].clear();
}
// cout << u << ": ";
// for(auto x: s[u]) cout << "{" << x.fi << ", " << x.se << "} ";
// cout << "\n";
}
int best_path(int N, int K, int H[][2], int L[]){
// n = N, k = K;
// FOR(i, 0, N - 1){
// adj[H[i][0]].eb(L[i], H[i][1]);
// adj[H[i][1]].eb(L[i], H[i][0]);
// }
FOR(i, 0, N - 1){
G[H[i][0]].insert({L[i], H[i][1]});
G[H[i][1]].insert({L[i], H[i][0]});
}
queue<int> qe;
qe.emplace(0);
while(!qe.empty()){
int u = qe.front(); qe.pop();
int n = dfsSize(u);
int c = centroid(u, -1, n);
s[c].insert({0, 0});
for(auto [w, v]: G[c]){
dfs(v, c);
for(auto x: s[v]) if(x.fi + w <= K){
s[c].insert({x.fi + w, x.se + 1});
} else break;
}
for(auto [w, v]: G[c]){
for(auto x: s[v]) if(x.fi + w <= K){
s[c].erase(s[c].find({x.fi + w, x.se + 1}));
} else break;
for(auto x: s[v]) if(x.fi + w <= K){
auto it = s[c].lower_bound({K - (x.fi + w), -1});
if(it == s[c].end()) continue;
ans = min(ans, x.se + 1 + (*it).se);
} else break;
for(auto x: s[v]) if(x.fi + w <= K){
s[c].insert({x.fi + w, x.se + 1});
} else break;
s[v].clear();
}
s[c].clear();
vector<pi> tmp(ALL(G[c]));
for(auto [w, v]: tmp){
G[c].erase({w, v});
G[v].erase({w, c});
qe.emplace(v);
}
}
// dfs(0);
if(ans != INF) return ans;
return -1;
}
//int NN, KK, H[N][2], L[N];
//
//int main(){
// IOS;
// Fi();
// cin >> NN >> KK;
// FOR(i, 0, NN - 1){
// cin >> H[i][0] >> H[i][1];
// }
// FOR(i, 0, NN - 1) cin >> L[i];
// cout << best_path(NN, KK, H, L);
// return 0;
//}