제출 #672096

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
672096		vjudge1	경주 (Race) (IOI11_race)	C++17	컴파일 에러	0 ms	0 KiB

race

#include "race.h"

#include<bits/stdc++.h>

#define ll long long
#define pp push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ld long double
#define PI acos(-1)
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define ones(x) __builtin_popcountll(x)
#define int ll

#define Drakon  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;


unsigned long long inf = 1e10;
const double EPS = 1e-6;
const int MOD = 1000000007, N = 200005, LOG = 25, M = 2;

typedef array<array<int, M>, M> matrix;

int gcd(int x, int y) {
    return y ? gcd(y, x % y) : x;
}

int lcm(int a, int b) {
    return (a * b) / __gcd(a, b);
}

int n,k,sz[N];
vector<pair<int,int>>adj[N];
bool vis[N];

void dfs_sz(int u,int p){

    sz[u] = 1;
    for(auto x:adj[u]){
        if(x.first == p || vis[x.first])continue;
        dfs_sz(x.first,u);
        sz[u] += sz[x.first];
    }
}

int dfs_centroid(int u,int p,int s){

    for(auto x:adj[u]){
        if(x.first == p || vis[x.first])continue;
        if(sz[x.first]>s/2)
            return dfs_centroid(x.first,u,s);
    }
    return u;
}

int ans;
int best[1000005];
vector<pair<int,int>>pool;

void dfs(int u,int p,int sum,int dep){
    pool.pp({dep,sum});
    for(auto v:adj[u]){
        if(v.first == p||vis[v.first])continue;
        dfs(v.first,u,sum+v.second,dep+1);
    }
}

void build_centroid(int u,int p){

    dfs_sz(u,p);
    int centroid = dfs_centroid(u,p,sz[u]);
    vis[centroid] = true;
    vector<int>all;
    best[0] = 0;
    all.pp(0);

    for(auto v:adj[centroid]){
        if(vis[v.first])continue;
        pool.clear();
        dfs(v.first,centroid,v.second,1);
        for(auto x:pool){
            all.pp(x.second);
            if(x.second <= k){
                if(~best[k-x.second]){
                    ans = min(ans,x.first+best[k-x.second]);
                }
            }
        }
        for(auto x:pool){
            if(!~best[x.second]){
                best[x.second] = x.first;
            }
            else{
                best[x.second] = min(best[x.second],x.first);
            }
        }
    }

    for (int i = 0; i < all.size(); ++i) {
        best[all[i]] = -1;
    }

    for(auto v:adj[centroid]){
        if(vis[v.first])continue;
        build_centroid(v.first,centroid);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N,k = K;
    for (int i = 0; i < n-1; ++i) {
        int u = H[i][0],v = H[i][1],z = L[i];
        adj[u].pp({v,z});
        adj[v].pp({u,z});
    }
    ans = INT_MAX;
    memset(best,-1,sizeof best);
    build_centroid(0,0);
    if(ans == INT_MAX)
        ans = -1;
    return ans;
}

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

race.cpp: In function 'void build_centroid(long long int, long long int)':
race.cpp:101:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i = 0; i < all.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccdExPPK.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status