Submission #1082141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082141		CELD_07	Race (IOI11_race)	C++17	100 / 100	238 ms	41184 KiB

race

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
#define endl "\n"
#define inf LLONG_MAX
#define vll vector<ll>
#define sd second
#define ft first
#define al(x) x.begin(),x.end()
#define alr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
vector<vector<pair<ll, ll>>> adj;
vector<ll> v;
vector<bool>visited;
inline ll dfs(ll n, ll p){
v[n]=1;
for(auto& [y, w]: adj[n]){
    if(y==p || visited[y]==1)continue;
    v[n]+=dfs(y, n);
}
return v[n];
}
inline ll _find(ll n, ll n1, ll p){
for(auto& [y, w]: adj[n]){
    if(y==p)continue;
    if(v[y]>n1/2 && !visited[y])return _find(y, n1, n);
}
return n;
}
map<ll, ll> m;
vector<ll> v3;
vector<pair<ll, ll>> v2;
ll cnt=0, lim, cnt1=0, cnt3=0, res=LLONG_MAX;
inline void dfs1(ll n, ll p){
   // cout<<n<<" "<<cnt3<<" "<<cnt<<endl;
    if(cnt<=lim)v2.push_back({cnt, cnt3});
    if(cnt<=lim && v3[lim-cnt]!=LLONG_MAX)res=min(res, cnt3+v3[lim-cnt]);
for(auto& [y, w]: adj[n]){
    if(y==p || visited[y])continue;
    cnt+=w;
    cnt3++;
    dfs1(y, n);
    cnt-=w;
    cnt3--;
}
}
ll cnt2=0;
inline void centroid(ll n){
dfs(n, n);
ll o=_find(n, v[n], n);
visited[o]=1;
v2.clear();
ll i=0;
//cout<<o<<endl;
for(auto& [y, w]: adj[o]){
    if(visited[y])continue;
    cnt3++;
    cnt+=w;
    dfs1(y, o);
    cnt3--;
    cnt-=w;
    for(; i<v2.size(); i++){v3[v2[i].ft]=min(v3[v2[i].ft], v2[i].sd);if(v2[i].ft==lim)res=min(res, v2[i].sd);}
}
for(auto& [y1, w]: v2)v3[y1]=LLONG_MAX;
for(auto& [y, w]: adj[o]){
    if(visited[y])continue;
    centroid(y);
}
}
int best_path(int N, int K, int H[][2], int L[]){
    ll a, b, c, d, e, f;
    a=N;
    b=K;
    lim=b;
    adj.clear();
    v.clear();
    v3.clear();
    visited.clear();
    adj.resize(a+1);
    v.resize(a+1);
    v3.assign(lim+1, LLONG_MAX);
    visited.assign(a+1, 0);
    for(int i=0; i<a-1; i++){
        c=H[i][1];
        d=H[i][0];
        e=L[i];
        adj[c].push_back({d, e});
        adj[d].push_back({c, e});
    }
    centroid(1);
    return (res==LLONG_MAX?-1:res);
}

Compilation message (stderr)

race.cpp: In function 'void centroid(long long int)':
race.cpp:66:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(; i<v2.size(); i++){v3[v2[i].ft]=min(v3[v2[i].ft], v2[i].sd);if(v2[i].ft==lim)res=min(res, v2[i].sd);}
      |           ~^~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:75:23: warning: unused variable 'f' [-Wunused-variable]
   75 |     ll a, b, c, d, e, f;
      |                       ^

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57