Submission #96122

#	Time	Username	Problem	Language	Result	Execution time	Memory
96122		igzi	Race (IOI11_race)	C++17	100 / 100	522 ms	37116 KiB

race

#include <bits/stdc++.h>
#define maxK 1000006
#define maxN 200005

using namespace std;

vector <pair<int,int>> adj[maxN];
vector <int> all;
long long dis[maxK],s[maxN],ans=INT_MAX,k;
bool mar[maxN];

void dfs0(int n,int par){
s[n]=1;
for(int i=0;i<adj[n].size();i++){
int x=adj[n][i].first;
if(x==par || mar[x]) continue;
dfs0(x,n);
s[n]+=s[x];
}
}

int cen(int n,int par,int S){
for(int i=0;i<adj[n].size();i++){
int x=adj[n][i].first;
if(x==par || mar[x]) continue;
if(s[x]>S/2) return cen(x,n,S);
}
return n;
}

void dfs1(int n,int par,long long d,int l){
if(d<=k) all.push_back(d);
if(d<=k) ans=min(ans,dis[k-d]+l);
for(int i=0;i<adj[n].size();i++){
int x=adj[n][i].first;
if(x==par || mar[x]) continue;
dfs1(x,n,d+adj[n][i].second,l+1);
}
}

void dfs2(int n,int par,long long d,int l){
if(d<=k) dis[d]=min(dis[d],(long long)l);
for(int i=0;i<adj[n].size();i++){
int x=adj[n][i].first;
if(x==par || mar[x]) continue;
dfs2(x,n,d+adj[n][i].second,l+1);
}
}

void decompose(int n){
dfs0(n,-1);
int c=cen(n,-1,s[n]);
mar[c]=true;
for(int i=0;i<adj[c].size();i++){
int x=adj[c][i].first;
if(mar[x]) continue;
dfs1(x,c,adj[c][i].second,1);
dfs2(x,c,adj[c][i].second,1);
}
ans=min(ans,dis[k]);
for(int i=0;i<all.size();i++) dis[all[i]]=INT_MAX;
all.clear();
for(int i=0;i<adj[c].size();i++){
int x=adj[c][i].first;
if(mar[x]) continue;
decompose(x);
}
}

int best_path(int n, int K, int H[][2], int L[])
{
    k=K;
    for(int i=0;i<n-1;i++){
        int a=H[i][0],b=H[i][1],c=L[i];
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    for(int i=0;i<=k;i++){
        dis[i]=INT_MAX;
    }
    dis[0]=0;
    decompose(1);
    if(ans==INT_MAX)return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs0(int, int)':
race.cpp:14:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
race.cpp: In function 'int cen(int, int, int)':
race.cpp:23:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs1(int, int, long long int, int)':
race.cpp:34:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs2(int, int, long long int, int)':
race.cpp:43:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
race.cpp: In function 'void decompose(int)':
race.cpp:54:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[c].size();i++){
             ~^~~~~~~~~~~~~~
race.cpp:61:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<all.size();i++) dis[all[i]]=INT_MAX;
             ~^~~~~~~~~~~
race.cpp:63:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[c].size();i++){
             ~^~~~~~~~~~~~~~

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