Submission #1118013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118013		Newtonabc	Race (IOI11_race)	C++14	100 / 100	677 ms	46748 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
const int M=2e5+10;
vector<pair<long long,int> > adj[M];
int n,rem[M],sz[M],dist[M],lvl[M];
set<pair<long long,int> >::iterator it;
set<pair<long long,int> > s;
queue<pair<long long,int> > q;
int ans=INT_MAX,k;
void findsz(int u,int p){
  sz[u]=1;
  for(int i=0;i<adj[u].size();i++){
    int v=adj[u][i].second;
    if(v==p || rem[v]) continue;
    findsz(v,u);
    sz[u]+=sz[v];
  }
}
void findlvl(int u,int p){
  for(int i=0;i<adj[u].size();i++){
    int v=adj[u][i].second;
    if(v==p || rem[v]) continue;
    lvl[v]=lvl[u]+1;
    findlvl(v,u);
  }
}
int getcentroid(int u,int p,int treesz){
  for(int i=0;i<adj[u].size();i++){
    int v=adj[u][i].second;
    if(v==p || rem[v]) continue;
    if(sz[v]*2>treesz) return getcentroid(v,u,treesz);
  }
  return u;
}
void dfs(int u,int p){
  if(dist[u]>k) return;
  for(int i=0;i<adj[u].size();i++){
    if(!lvl[u]) while(!q.empty()) s.insert(mp(k-q.front().first,q.front().second)),q.pop();
    int v=adj[u][i].second;
    long long w=adj[u][i].first;
    if(v==p || rem[v]) continue;
    dist[v]=dist[u]+w;
    it=s.lower_bound(mp(dist[v],0));
    if(it->first==dist[v]) ans=min(ans,it->second+lvl[v]);
    q.push(mp(dist[v],lvl[v]));
    dfs(v,u);
  }
}
void decom(int u){
  findsz(u,u);
  int cen=getcentroid(u,u,sz[u]);
  //cout<<cen <<"\n";
  //for(int i=0;i<n;i++) cout<<dist[i] <<" ";
  s.insert(mp(k,0));
  lvl[cen]=0;
  dist[cen]=0;
  findlvl(cen,cen);
  dfs(cen,cen);
  s.clear();
  while(!q.empty()) q.pop();
  rem[cen]=true;
  for(int i=0;i<adj[cen].size();i++){
    int v=adj[cen][i].second;
    if(rem[v]) continue;
    decom(v);
  }
}
int best_path(int N, int K, int H[][2], int L[]){
  n=N,k=K;
  for(int i=0;i<n-1;i++){
    adj[H[i][0]].push_back(mp(L[i],H[i][1]));
    adj[H[i][1]].push_back(mp(L[i],H[i][0]));
  }
  decom(0);
  if(ans==INT_MAX) return -1;
  return ans;
}

Compilation message (stderr)

race.cpp: In function 'void findsz(int, int)':
race.cpp:14:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
race.cpp: In function 'void findlvl(int, int)':
race.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
race.cpp: In function 'int getcentroid(int, int, int)':
race.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int)':
race.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int i=0;i<adj[u].size();i++){
      |               ~^~~~~~~~~~~~~~
race.cpp: In function 'void decom(int)':
race.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int i=0;i<adj[cen].size();i++){
      |               ~^~~~~~~~~~~~~~~~

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