Submission #593231

#	Time	Username	Problem	Language	Result	Execution time	Memory
593231		chirathnirodha	Race (IOI11_race)	C++17	9 / 100	3059 ms	13600 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second 
#define P push
#define I insert
typedef long long ll;
const ll INF=10000000000000;
const int maxn=200000;
ll n,k;
int ans=INT32_MAX;
vector<pair<ll,ll> > v[maxn];
int parent[maxn];
int subsiz[maxn];
int len[maxn];
ll dist[maxn];
int dfs(int x,set<int> s){
  subsiz[x]=1;
  for(int i=0;i<v[x].size();i++){
    int y=v[x][i].F;
    if(parent[x]==y || s.count(y))continue;
    parent[y]=x;
    dist[y]=dist[x]+v[x][i].S;
    len[y]=len[x]+1;
    subsiz[x]+=dfs(y,s);
  }
  return subsiz[x];
}
int find_centroid(int x,int parsub,set<int> s,int gsiz){
  pair<ll,int> p={-1,-1};
  for(int i=0;i<v[x].size();i++){
    int y=v[x][i].F;
    if(parent[x]==y || s.count(y))continue;
    if(p.F<subsiz[y])p={subsiz[y],y};
  }
  if(p.F<=gsiz/2)return x;
  else return find_centroid(p.S,subsiz[x]+parsub-p.F,s,gsiz);
}
map<ll,int> func(int x,int prcen,set<int> s){
  parent[x]=prcen;len[x]=1;dist[x]=0;
  dfs(x,s);
  int cen=find_centroid(x,0,s,subsiz[x]);
  ll cenpar=parent[cen],cenparlen;
  map<ll,int> mp,mp1;mp[0]=1;
 
  s.I(cen);
 
  ll y,disty;
  for(int i=0;i<v[cen].size();i++){
    y=v[cen][i].F;
    disty=v[cen][i].S;
 	
    if(y==cenpar){
      cenparlen=disty;
      continue;
    }
 	if(s.count(y))continue;
    mp1=func(y,cen,s);
    for(auto itr=mp1.begin();itr!=mp1.end();itr++){
      pair<int,int> p=*itr;
      if(mp.count(k-p.F-disty)==0)continue;
      ans=min(ans,mp[k-p.F-disty]+p.S);
    }
    for(auto itr=mp1.begin();itr!=mp1.end();itr++){
      pair<int,int> p=*itr;
      if(mp.count(p.F+disty)==0)mp[p.F+disty]=p.S+1;
      else mp[p.F+disty]=min(mp[p.F+disty],p.S+1);
    }
  }
  map<ll,int> nmap;
  if(x==cen){
    for(auto itr=mp.begin();itr!=mp.end();itr++){
      pair<ll,int> p=*itr;
      if(nmap.count(p.F+dist[cen])==0)nmap[p.F+dist[cen]]=p.S;
      else nmap[p.F+dist[cen]]=min(nmap[p.F+dist[cen]],p.S);
    }
    nmap[0]=1;
    return nmap;
  }
  y=cenpar;disty=cenparlen;
  mp1=func(y,cen,s);
  for(auto itr=mp1.begin();itr!=mp1.end();itr++){
    pair<int,int> p=*itr;
    if(mp.count(k-p.F-disty)==0)continue;
    ans=min(ans,mp[k-p.F-disty]+p.S);
  }
  queue<int> q;q.P(x);
  parent[x]=prcen;len[x]=1;dist[x]=0;
  while(!q.empty()){
    int c=q.front();q.pop();
    if(c==cen)continue;
    for(int i=0;i<v[c].size();i++){
      y=v[c][i].F;
      disty=v[c][i].S;
      if(parent[c]==y)continue;
      parent[y]=c;
      len[y]=len[c]+1;
      dist[y]=dist[c]+disty;
      if(nmap.count(dist[y])==0)nmap[dist[y]]=len[y];
      else nmap[dist[y]]=min(nmap[dist[y]],len[y]);
      q.P(y);
    }
  }
  for(auto itr=mp.begin();itr!=mp.end();itr++){
    pair<ll,int> p=*itr;
    if(nmap.count(p.F+dist[cen])==0)nmap[p.F+dist[cen]]=p.S+len[cen]-1;
    else nmap[p.F+dist[cen]]=min(nmap[p.F+dist[cen]],p.S+len[cen]-1);
  }
  nmap[0]=1;
  return nmap;
}
int best_path(int N, int K, int h[][2], int l[]){
  n=(ll)N;k=(ll)K;
  for(int i=0;i<n-1;i++){
    v[h[i][0]].PB(MP(h[i][1],(ll)l[i]));
    v[h[i][1]].PB(MP(h[i][0],(ll)l[i]));
  }
  set<int> s;
  func(0,0,s);
  if(ans>n)return -1;
  return ans-1;
}

Compilation message (stderr)

race.cpp: In function 'int dfs(int, std::set<int>)':
race.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(int i=0;i<v[x].size();i++){
      |               ~^~~~~~~~~~~~
race.cpp: In function 'int find_centroid(int, int, std::set<int>, int)':
race.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i=0;i<v[x].size();i++){
      |               ~^~~~~~~~~~~~
race.cpp: In function 'std::map<long long int, int> func(int, int, std::set<int>)':
race.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0;i<v[cen].size();i++){
      |               ~^~~~~~~~~~~~~~
race.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i=0;i<v[c].size();i++){
      |                 ~^~~~~~~~~~~~
race.cpp:87:22: warning: 'cenparlen' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |     if(mp.count(k-p.F-disty)==0)continue;
      |                 ~~~~~^~~~~~

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