제출 #318297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
318297		tjdgus4384	경주 (Race) (IOI11_race)	C++14	100 / 100	779 ms	49624 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> v[200001], c[200001], chk1, chk2;
bool visited[200001];
int sz[200001], ans = 1000000000, n, k;
int mindep[1000001], newdep[1000001];

int getSize(int x, int y){
    sz[x] = 1;
    for(int i = 0;i < v[x].size();i++){
        if(v[x][i] != y && !visited[v[x][i]]) sz[x] += getSize(v[x][i], x);
    }
    return sz[x];
}

int getCentroid(int x, int y, int z){
    for(int i = 0;i < v[x].size();i++){
        if(v[x][i] != y && sz[v[x][i]]*2 > z && !visited[v[x][i]]) return getCentroid(v[x][i], x, z);
    }
    return x;
}

void dfs(int x, int y, int dep, int cnt){
    if(dep == k) ans = min(ans, cnt);
    if(dep > k) return;
    if(mindep[k-dep] != 1e9) ans = min(ans, cnt + mindep[k-dep]);
    newdep[dep] = min(newdep[dep], cnt);
    chk1.push_back(dep);
    chk2.push_back(dep);
    for(int i = 0;i < v[x].size();i++){
        if(v[x][i] != y && !visited[v[x][i]]) dfs(v[x][i], x, dep+c[x][i], cnt+1);
    }
}

void dnc(int x){
    int cent = getCentroid(x, -1, getSize(x, -1));
    for(int i = 0;i < v[cent].size();i++){
        if(!visited[v[cent][i]]){
            dfs(v[cent][i], cent, c[cent][i], 1);
            for(int j = 0;j < chk1.size();j++) mindep[chk1[j]] = min(mindep[chk1[j]], newdep[chk1[j]]);
            chk1.clear();
        }
    }
    for(int j = 0;j < chk2.size();j++) mindep[chk2[j]] = newdep[chk2[j]] = 1e9;
    chk2.clear();
    visited[cent] = true;
    for(int i = 0;i < v[cent].size();i++) if(!visited[v[cent][i]]) dnc(v[cent][i]);
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N, k = K;
    for(int i = 0;i < N-1;i++){
        v[H[i][0]].push_back(H[i][1]);
        c[H[i][0]].push_back(L[i]);
        v[H[i][1]].push_back(H[i][0]);
        c[H[i][1]].push_back(L[i]);
    }
    for(int i = 0;i <= K;i++) mindep[i] = newdep[i] = 1e9;
    dnc(0);
    return ans == 1e9 ? -1 : ans;
}

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

race.cpp: In function 'int getSize(int, int)':
race.cpp:11:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i = 0;i < v[x].size();i++){
      |                   ~~^~~~~~~~~~~~~
race.cpp: In function 'int getCentroid(int, int, int)':
race.cpp:18:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i = 0;i < v[x].size();i++){
      |                   ~~^~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 0;i < v[x].size();i++){
      |                   ~~^~~~~~~~~~~~~
race.cpp: In function 'void dnc(int)':
race.cpp:38:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0;i < v[cent].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~
race.cpp:41:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for(int j = 0;j < chk1.size();j++) mindep[chk1[j]] = min(mindep[chk1[j]], newdep[chk1[j]]);
      |                           ~~^~~~~~~~~~~~~
race.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int j = 0;j < chk2.size();j++) mindep[chk2[j]] = newdep[chk2[j]] = 1e9;
      |                   ~~^~~~~~~~~~~~~
race.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 0;i < v[cent].size();i++) if(!visited[v[cent][i]]) dnc(v[cent][i]);
      |                   ~~^~~~~~~~~~~~~~~~

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