제출 #857743

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857743		tigran	경주 (Race) (IOI11_race)	C++17	100 / 100	1258 ms	56416 KiB

race

#include <bits/stdc++.h>
#define pb push_back
#include "race.h"
#define endl "\n"
#define fastio cin.tie(0); ios_base::sync_with_stdio(false);
typedef long long ll;
using namespace std;
 
const int mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
 
vector<pair<int, int> > adj[MAXN];
vector<int> sub(MAXN), vis(MAXN);
 
inline void subtreecalc(int node, int par){
  sub[node] = 1;
  for(auto itr: adj[node]){
    if(itr.first != par && !vis[itr.first]){
        subtreecalc(itr.first, node);
        sub[node] += sub[itr.first];
    }
  }
}
 
inline int find_centroid(int node, int par, int sz){
  for(auto itr: adj[node]){
    if(vis[itr.first] || itr.first == par) continue;
    if(sub[itr.first] > sz/2) return find_centroid(itr.first, node, sz);
  }
 
  return node;
}
 
inline void dfs(int node, int par, int depth, int len, map<int, int> &mpp){
  if(vis[node]) return;
  if(!mpp[depth]) mpp[depth] = len;
  else mpp[depth] = min(mpp[depth], len);
 
  for(auto itr: adj[node]){
    if(vis[itr.first] || itr.first == par) continue;
    dfs(itr.first, node, depth + itr.second, len + 1, mpp);
  }
}
 
bool compare(pair<int, int> p1, pair<int, int> p2){
  return (sub[p1.first] > sub[p2.first]);
}
 
int best_path(int N, int K, int H[][2], int L[]){
  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]});
  }
  int ans = 1e9;
  vector<int> roots, new_roots;
  roots.pb(0);
  int cnt = 0;
 
 while(cnt < N){
  for(auto i: roots) subtreecalc(i, i);
 
  for(auto i: roots){
    int ct = find_centroid(i, i, sub[i]);
    sort(adj[ct].begin(), adj[ct].end(), compare);
    int ind = 0;
    map<int, int> pre, now;
    while(ind < adj[ct].size()){
        if(vis[adj[ct][ind].first]){
            ind++;
            continue;
        }
        dfs(adj[ct][ind].first, ct, adj[ct][ind].second, 1, now);
        for(auto itr: now){
            if(pre[K - itr.first]) ans = min(ans, pre[K - itr.first] + now[itr.first]);
            if(itr.first == K) ans = min(ans, itr.second);
        }
        for(auto itr: now){
            if(!pre[itr.first] && itr.first != 0) pre[itr.first] = itr.second;
            else pre[itr.first] = min(pre[itr.first], now[itr.first]);
        }
        now.clear();
        ind++;
    }
 
    vis[ct] = 1;
    for(auto itr: adj[ct]){
        if(!vis[itr.first]) new_roots.pb(itr.first);
    }
    cnt++;
  }
  roots = new_roots;
  new_roots.clear();
 }
 
  if(ans == 1e9) return -1;
  else return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     while(ind < adj[ct].size()){
      |           ~~~~^~~~~~~~~~~~~~~~

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