Submission #953366

#	Time	Username	Problem	Language	Result	Execution time	Memory
953366		sopaconk	Race (IOI11_race)	C++17	0 / 100	154 ms	262144 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

vector<int> dis;
vector<int> sz;
vector<int> par;
vector<vector<pair<int,int>>> adj;
vector<bool> vis;

int ans=1e6;
int need;
void szdfs(int node, int parent){
  par[node]=parent;
  sz[node]=1;
  for(int i=0; i<adj[node].size(); ++i){
    int x= adj[node][i].first;
    if(vis[x] || node==parent) continue;
    szdfs(x, node);
    sz[node]+=sz[x];
  }
}




int Centroid (int node, int siz){
  for(int i=0; i<adj[node].size(); ++i){
    int x= adj[node][i].first;
    if(par[x]!=node || vis[x]) continue;
    if(sz[x] > siz/2){
      return Centroid ( x, siz);
    }  
  }
  return node;
}

queue<pair<int,int>>q;
void distances (int node, int d, int c){

  for(int i=0; i<adj[node].size(); ++i){
    int x=adj[node][i].first;
    int y=adj[node][i].second;
    d+=y;
    if(d<=need){
      if(dis[need-d]!=0){
        ans=min(ans, dis[need-d]+c);
      }
    }
    q.push({d, c});
    distances(x, d, c+1);
  }
}


void Centroid_desc (int node){
    szdfs(node, -1);
    int root= Centroid ( node, sz[node]);
    for(int i=0; i<adj[root].size(); ++i){
      distances(adj[root][i].first, adj[root][i].second, 1);
      while(!q.empty()){
        dis[q.front().first]=min(dis[q.front().first], q.front().second);
        q.pop();
      }
    }
    if(dis[need]!=0){
      ans=min(ans, dis[need]);
    }
    vis[root]=1;
    for(int i=0; i<adj[root].size(); ++i){
      Centroid_desc(adj[root][i].first);
    }
}






int best_path(int N, int K, int H[][2], int L[])
{
  dis.resize(K+5);
  sz.resize(N);
  par.resize(N);
  adj.resize(N);
  vis.resize(N);
  for(int i=0; i<N-1; ++i){
    adj[H[i][0]].pb({H[i][1], L[i]});
    adj[H[i][1]].pb({H[i][0],L[i]});
  }
  need=K;
  Centroid_desc(0);
  return ans;
}

Compilation message (stderr)

race.cpp: In function 'void szdfs(int, int)':
race.cpp:17:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for(int i=0; i<adj[node].size(); ++i){
      |                ~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int Centroid(int, int)':
race.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int i=0; i<adj[node].size(); ++i){
      |                ~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void distances(int, int, int)':
race.cpp:42:17: 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<adj[node].size(); ++i){
      |                ~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void Centroid_desc(int)':
race.cpp:60:19: 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<adj[root].size(); ++i){
      |                  ~^~~~~~~~~~~~~~~~~
race.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i=0; i<adj[root].size(); ++i){
      |                  ~^~~~~~~~~~~~~~~~~

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