Submission #680896

#	Time	Username	Problem	Language	Result	Execution time	Memory
680896		1075508020060209tc	Race (IOI11_race)	C++14	100 / 100	684 ms	36864 KiB

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
//#define int long long
int n;int k;
vector<pair<int,int>>e[200005];
int dp[1000006];
int sz[200005];
int iscen[200005];
int dfssz(int nw,int pa){
int ret=1;
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i].first;
    if(v==pa||iscen[v]){continue;}
    ret+=dfssz(v,nw);
}
sz[nw]=ret;
return ret;
}

void dfscen(int nw,int pa,int nd,int &pl){
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i].first;
    if(v==pa||iscen[v]){continue;}
    dfscen(v,nw,nd,pl);
}
if(pl==0&&sz[nw]>nd/2){
    pl=nw;
}
}
int ans=1e8;
void dfs(int nw,int pa,int dis,int d,int ad){
if(dis<=k&&ad==0){
    ans=min(ans,d+dp[k-dis]);
}
if(ad==1){
    if(dis<=k){dp[dis]=min(dp[dis],d);}
}
if(ad==-1){
    if(dis<=k){dp[dis]=1e7;}
}
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i].first;int w=e[nw][i].second;
    if(iscen[v]||v==pa){continue;}
    dfs(v,nw,dis+w,d+1,ad);
}
}


void solve(int rt){
int cen=0;
dfscen(rt,0,dfssz(rt,0),cen);
dp[0]=0;
for(int i=0;i<e[cen].size();i++){
    int v=e[cen][i].first;int w=e[cen][i].second;
    if(iscen[v]){continue;}
    dfs(v,cen,w,1,0);
    dfs(v,cen,w,1,1);
}
for(int i=0;i<e[cen].size();i++){
    int v=e[cen][i].first;int w=e[cen][i].second;
    if(iscen[v]){continue;}
    dfs(v,cen,w,1,-1);
}
iscen[cen]=1;
for(int i=0;i<e[cen].size();i++){
    int v=e[cen][i].first;int w=e[cen][i].second;
    if(iscen[v]){continue;}
    solve(v);
}



}

int best_path(int N, int K, int H[][2], int L[]){

n=N;k=K;//cin>>n>>k;

for(int i=0;i<=k;i++){
    dp[i]=1e7;
}

for(int i=0;i<=n-2;i++){
    int a;int b;int c;
    //cin>>a>>b>>c;
    a=H[i][0];b=H[i][1];c=L[i];
    a++;b++;
    e[a].push_back({b,c});
    e[b].push_back({a,c});
}
solve(1);
if(ans<=200000){
    //cout<<ans<<endl;
    return ans;
}else{
    //cout<<-1<<endl;
    return -1;
}


}

Compilation message (stderr)

race.cpp: In function 'int dfssz(int, int)':
race.cpp:12:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
race.cpp: In function 'void dfscen(int, int, int, int&)':
race.cpp:22:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int, int)':
race.cpp:42:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:54:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 | for(int i=0;i<e[cen].size();i++){
      |             ~^~~~~~~~~~~~~~
race.cpp:60:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 | for(int i=0;i<e[cen].size();i++){
      |             ~^~~~~~~~~~~~~~
race.cpp:66:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 | for(int i=0;i<e[cen].size();i++){
      |             ~^~~~~~~~~~~~~~
race.cpp:67:31: warning: unused variable 'w' [-Wunused-variable]
   67 |     int v=e[cen][i].first;int w=e[cen][i].second;
      |                               ^

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