Submission #221287

#	Time	Username	Problem	Language	Result	Execution time	Memory
221287		a_player	Race (IOI11_race)	C++14	0 / 100	350 ms	262148 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

const int nax=2e5+5;
typedef long long ll;

struct node{
  int a,c;
  ll b;
};

vector<node> grafo[nax];
int centres[nax];
int sizes[nax];
int ans=INT_MAX;
int N,K;
map<ll,int> m;
void incl(int n, int a, int d, ll v){
    if(K<v)return;
    if(a!=-1){
    if(m.count(K-v))ans=min(ans,m[K-v]+d);
    if(!m.count(v))m[v]=d;
    else m[v]=min(m[v],d);
    }else{
      m.clear();
    }
    for(auto x:grafo[n]){
      if(!x.c||x.a==a)continue;
      incl(x.a,n,d+1,v+x.b);
    }
}
int findc(int n, int a, int& c, int num){
      int s=0;
      for(auto x:grafo[n]){
        if(!x.c||x.a==a)continue;
            s+=findc(x.a,n,c,num);
      }
      if(abs(s-num/2)<=1)c=n;
      return s+1;
}
int findsize(int n, int a){
  int s=0;
  for(auto x:grafo[n]){
    if(!x.c||x.a==a)continue;
    s+=findsize(x.a,n);
  }
  return s+1;
}
void centroid(int n){
  incl(n,-1,0,0);
  for(int i=0;i<grafo[n].size();i++)grafo[n][i].c=0;
  for(int i=0;i<grafo[n].size();i++)sizes[i]=findsize(grafo[n][i].a,-1);
  for(int i=0;i<grafo[i].size();i++)findc(grafo[n][i].a,-1,centres[i],sizes[i]);
  for(int i=0;i<grafo[n].size();i++)centroid(centres[i]);

}

int best_path(int N, int K, int H[][2], int L[]){
  ::N=N,::K=K;
  for(int i=0;i<N-1;i++){
    grafo[H[i][0]].push_back({H[i][1],1,(ll)L[i]});
    grafo[H[i][1]].push_back({H[i][0],1,(ll)L[i]});
  }
  sizes[0]=findsize(0,-1);
  findc(0,-1,centres[0],sizes[0]);
  centroid(centres[0]);
  return ans;
}

Compilation message (stderr)

race.cpp: In function 'void centroid(int)':
race.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<grafo[n].size();i++)grafo[n][i].c=0;
               ~^~~~~~~~~~~~~~~~
race.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<grafo[n].size();i++)sizes[i]=findsize(grafo[n][i].a,-1);
               ~^~~~~~~~~~~~~~~~
race.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<grafo[i].size();i++)findc(grafo[n][i].a,-1,centres[i],sizes[i]);
               ~^~~~~~~~~~~~~~~~
race.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<grafo[n].size();i++)centroid(centres[i]);
               ~^~~~~~~~~~~~~~~~

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