제출 #109749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
109749		m3r8	Race (IOI11_race)	C++14	0 / 100	9 ms	5120 KiB

race

#include <stdio.h>
#include <utility>
#include <string.h>
#include <vector>
#include "race.h"
#define ll long long
#define ii std::pair<int,int>
#define il std::pair<int,std::pair<int,std::pair<int,long long>>>
#define MAXN 200100
#define MAXK 1000000

std::vector<il> adj[MAXN];
int cnt;
int child[MAXN];
int posNxt[MAXN];
ii isDist[MAXK];
ll dist[MAXN];
int nKant[MAXN];
int szSub[MAXN];
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,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(dist[child[i]] > k)continue;
        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 best_path(int n1,int k1,int H[][2],int L[]){
  int a,b;
  n = n1;
  k=k1;
  ll cst;
  for(int i = 0;i<n-1;i++){
    a = H[i][0];
    b = H[i][1];
    cst = L[i];
    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(0,-1);
  goFromCen(c1);
  return mn;
  return 0;
};

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