Submission #109741

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
109741	2019-05-07T21:03:22 Z	m3r8	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

#include <stdio.h>
#include <utility>
#include <string.h>
#include <vector>
#define ll long long
#define ii std::pair<int,int>
#define il std::pair<int,std::pair<int,std::pair<int,long long>>>
#define N 200100
#define K 1000000

std::vector<il> adj[N];
int cnt;
int child[N];
int posNxt[N];
ii isDist[K];
ll dist[N];
int nKant[N];
int szSub[N];
ll k;
ll mn;
int trr;

void dfsSub(int v, int p){
  szSub[v] = 0; 
  for(auto &edg: adj[v]){
    int u = edg.first;  
    if(u != p && edg.second.first){
      dfsSub(u,v);  
      szSub[v] += 1;
      szSub[v] += szSub[u];
    };
  };
};
int findCent(int root, int par){
  dfsSub(root, par);  
  int sz = szSub[root] + 1;
  int akt = root;
  int prev = par;
  int mx = 0;
  int nxt = -1;
  while(true){
    nxt = akt;
    mx = sz - szSub[akt] - 1;
    for(auto& edg:adj[akt]){
      if(edg.first != prev && edg.second.first){
        if(mx < szSub[edg.first]+1){
          mx = szSub[edg.first]+1;
          nxt = edg.first;   
        };
      };
    };
    if(mx <= (sz/2)){
      return akt;  
    }
    else{
      prev = akt;
      akt = nxt;  
    };
  };
};
void dfsST(int v, int par, ll cst, int num){
  ll d = cst + dist[par];
  dist[v] = d;
  int knt = nKant[par] +1;
  nKant[v] = knt;
  child[cnt++] = v;
  ll srch = k-d;
  if(srch >= 0 && isDist[srch].first == num){
    if(mn == -1 || mn > isDist[srch].second + knt){
      mn = isDist[srch].second + knt;
    };  
  };
  for(auto &edg:adj[v]){
    if(edg.first != par && edg.second.first){
      dfsST(edg.first,v,cst+edg.second.second.second,num);
    };  
  };
};
void goFromCen(int cen){
  trr++;
  dist[cen] = 0;
  nKant[cen] = 0;
  for(auto &edg: adj[cen]){
    if(edg.second.first){
      edg.second.first = 0;
      adj[edg.first][edg.second.second.first].second.first = 0;
      cnt = 0;
      dfsST(edg.first,cen,edg.second.second.second,trr);
      for(int i = 0;i<cnt;i++){
        if(isDist[dist[child[i]]].first != trr){
          isDist[dist[child[i]]].first = trr;
          isDist[dist[child[i]]].second = nKant[child[i]];
        }else if(isDist[dist[child[i]]].second > nKant[child[i]]){
          isDist[dist[child[i]]].second = nKant[child[i]];
        };  
      };
      edg.second.first = 1;
    };
  };  
  for(auto &edg:adj[cen]){
    if(edg.second.first){
      edg.second.first = 0;
      int nxtC = findCent(edg.first,cen);
      goFromCen(nxtC);
    };  
  };
};
int n;

int main(void){
  scanf("%d %lld",&n,&k);
  int a,b;
  ll cst;
  for(int i = 0;i<n-1;i++){
    scanf("%d %d %lld",&a,&b,&cst);
    a++;
    b++;
    int sa = adj[a].size();
    int sb = adj[b].size();
    adj[a].push_back(il(0,std::pair<int,std::pair<int,long long>>(0,std::pair<int,long long>(0,0))));
    adj[a][sa].first = b;
    adj[a][sa].second.first = 1;
    adj[a][sa].second.second.first = sb;
    adj[a][sa].second.second.second = cst;
    adj[b].push_back(il(0,std::pair<int,std::pair<int,long long>>(0,std::pair<int,long long>(0,0))));
    adj[b][sb].first = a;
    adj[b][sb].second.first = 1;
    adj[b][sb].second.second.first = sa;
    adj[b][sb].second.second.second = cst;
  };
  mn = -1;
  cnt = 0;
  trr = 1;
  int c1 = findCent(1,-1);
  goFromCen(c1);
  printf("%lld\n",mn);
  return 0;
};

Compilation message

race.cpp: In function 'int main()':
race.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %lld",&n,&k);
   ~~~~~^~~~~~~~~~~~~~~~~
race.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %lld",&a,&b,&cst);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccw1N1bi.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccbslrsr.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/ccbslrsr.o: In function `main':
grader.cpp:(.text.startup+0x20): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status