| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 722729 | ktkerem | 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.
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
#include "race.h"
typedef long long ll;
typedef long double ld;
typedef __int128 vll;
typedef long long ftyp;
typedef std::complex<ftyp> vec;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define cx real
#define cy imag
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;
const ll limit = 1e12+7;
const ll sus = 2e5+5;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
std::vector<llll> adj[sus];
ll ddc = 0 , dd[sus] , vis[sus] , sub[sus] , ff;
std::map<ll , ll> mp[sus];
ll calsub(ll crt , ll prv){
//std::cout << crt << " " << prv << std::endl;
sub[crt] = 1;
vis[crt] = 1;
for(auto j:adj[crt]){
if(j.fi != prv && vis[j.fi] == 0){
sub[crt]+=calsub(j.fi , crt);
}
}
return sub[crt];
}
ll fndcent(ll crt , ll prv , ll prt){
//std::cout << crt << " " << prv << " " << prt << std::endl;
ll kd = (prt > ff?0:1);
ll p = -1;
for(auto j:adj[crt]){
if(j.fi != prv && dd[j.fi] == 0){
ll i = fndcent(j.fi , crt , sub[crt] - sub[j.fi] + prt);
if(p == -1){
p = i;
}
if(sub[j.fi] > ff){
kd =0;
}
}
}
if(kd){
return crt;
}
return p;
}
void ctf(ll crt , ll prv , ll fpr , ll o , ll p){
//std::cout << crt << " " << prv << " " << fpr << std::endl;
if(mp[p][fpr] == 0){
mp[p][fpr] = o;
}
mp[p][fpr] = std::min(mp[p][fpr] , o);
for(auto j:adj[crt]){
if(j.fi != prv && dd[j.fi] == 0){
ctf(j.fi , crt , fpr + j.sec , o+1 , p);
}
}
}
ll calans(ll crt ,ll k){
ddc++;
//std::cout << crt << " " << k << std::endl;
dd[crt] = 1;
ll jj = 0;
ll x = 0;
for(auto j:adj[crt]){
if(dd[j.fi]==0){
mp[x].clear();
x++;
}
}
for(auto j:adj[crt]){
if(dd[j.fi]==0){
ctf(j.fi , crt , j.sec , 1 , jj++);
}
}
ll ns = limit;
std::map<ll , ll> mpx;
mpx[0] = 0;
for(ll i = 0;x>i;i++){
for(auto j:mp[i]){
if(mpx[k-j.fi] != 0 || k - j.fi == 0){
ns = std::min(mpx[k-j.fi] + j.sec , ns);
}
}
for(auto j:mp[i]){
if(j.fi == 0){
//do nothing
}
else if(mpx[j.fi] == 0){
mpx[j.fi] = j.sec;
}
else{
mpx[j.fi] = std::min(j.sec , mpx[j.fi]);
}
}
}
return ns;
}
ll best_path(ll n , ll k , ll h[][2] ,ll cst[]){
for(ll i = 0 ; n-1>i;i++){
//std::cout << h[i][0] << " " << h[i][1] << " " << cst[i] << std::endl;
adj[h[i][0]].pb({h[i][1] , cst[i]});
adj[h[i][1]].pb({h[i][0] , cst[i]});
}
ll ans = limit;
ddc = 0;
for(ll i = 0 ; n>=i;i++){
dd[i] = 0;
}
while(n > ddc){
for(ll i = 0;n>i;i++){
if(vis[i] == 0){
calsub(i , -1);
ff = sub[i]/2;
ll cento = fndcent(i , -1 , 0);
ans = std::min(calans(cento , k) , ans);
}
}
for(ll i = 0;n>i;i++){
vis[i] = dd[i];
sub[i] = 0;
}
}
if(ans == limit){
return -1;
}
return ans;
}
/*void solve(){
ll n , k;std::cin >> n >> k;
std::cout << n << " " << k << std::endl;
ll alcst[n+5] , hkn[n+5][2];
for(ll i = 0;n-1>i;i++){
for(ll j = 0;2>j;j++){
std::cin >> hkn[i][j];
}
std::cin >> alcst[i];
}
ll ots = best_path(n , k , hkn , alcst);
std::cout << ots << "\n";
return;
}
int main(){
std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("in.txt" , "r" , stdin);
freopen("out.txt" , "w" , stdout);
#endif
ll t = 1;
//std::cin >> t;
while(t--){
solve();
}
}*/