제출 #1126482

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

race

#include<bits/stdc++.h> 
using namespace std;
 
typedef long long LL;
 
const int maxN = 200010;
vector<pair<int, int>> graph[maxN];
vector<bool> is_removed(maxN, 0);
vector<int> subtree_size(maxN, 0);
vector<int> pathsize(maxN, 0);
vector<int> depth(maxN, 0);
int ans = 1e9;
int k;

// #define MAX_N 500000

// static int N, K;
// static int H[MAX_N][2];
// static int L[MAX_N];
// static int solution;


int get_subtree_size(int node, int parent = -1) {
    subtree_size[node] = 1;
    for (auto child : graph[node]) {
        if (child.first == parent || is_removed[child.first]) { continue; }
        subtree_size[node] += get_subtree_size(child.first, node);
    }
    return subtree_size[node];
}

int get_centroid(int node, int tree_size, int parent = -1) {
    for (auto child : graph[node]) {
        if (child.first == parent || is_removed[child.first]) { continue; }
        if (subtree_size[child.first] * 2 > tree_size) {
            return get_centroid(child.first, tree_size, node);
        }
    }
    return node;
}


void dfs(int v, int parent, map<int, int> &m){
    for(auto u: graph[v]){
        if(u.first!= parent && !is_removed[u.first]){
            //cout<<u.first<<" ";
            pathsize[u.first] = pathsize[v] + u.second;
            depth[u.first] = depth[v] +1;
            if(m.find(pathsize[u.first]) == m.end()) m[pathsize[u.first]] = depth[u.first];
            else m[pathsize[u.first]] = min(depth[u.first], m[pathsize[u.first]]);

            dfs(u.first, v, m);
        }
    }
}

/** Build up the centroid decomposition recursively */
void build_centroid_decomp(int node = 0) {
    int centroid = get_centroid(node, get_subtree_size(node));
    //cout<<centroid<<" -> "<<"\n";
    // do something
    map<int, vector<pair<int, int>> > pathlist;
    for(auto child : graph[centroid]){
        if(!is_removed[child.first]){
            map<int, int> m;
            depth[child.first] = 1;
            pathsize[child.first] = child.second;
            m[pathsize[child.first]] = depth[child.first];
            dfs(child.first, centroid, m);
            //cout<<"x\n";
            for(auto p: m){
                pathlist[p.first].push_back({p.second,child.first});
            }
        }
    }

    auto it = pathlist.begin();
    for(; it != pathlist.end(); it++){
        sort((*it).second.begin(), (*it).second.end());
    }

    for(auto p: pathlist){
        int vertice = (p.second)[0].second;
        int length = (p.second)[0].first;
        //cout<<vertice<<" "<<length<<"\n";
        if(pathlist.find(k - p.first) != pathlist.end()){
            int nextvertice = pathlist[k - p.first][0].second;
            int nextlength = pathlist[k - p.first][0].first;

            if(vertice == nextvertice){
                if(pathlist[k-p.first].size() == 1) continue;
                nextvertice = pathlist[k - p.first][1].second;
                nextlength = pathlist[k - p.first][1].first;
            }

            ans = min(ans, length + nextlength);
        }
    }

    if(pathlist.find(k) != pathlist.end()){
        ans = min(ans, pathlist[k][0].first);
    }

    is_removed[centroid] = true;

    for (auto child : graph[centroid]) {
        if (is_removed[child.first]) { continue; }
        build_centroid_decomp(child.first);
    }
}

// void solve(){
//     int n; cin>>n>>k;
//     for(int i = 1; i<n; i++){
//         int u,v,w ;
//         cin>>u>>v>>w;
//         graph[u].push_back({v, w});
//         graph[v].push_back({u, w});
//     }
    

//     build_centroid_decomp(0);
 
 
//     //cout<<ans<<"\n";
//     printf("%lld\n", ans);
// }

// int best_path(int N, int K, int h[][2], int L[]){
//     ans = 1e9;

//     int n = N;
//     k = K;
//     for(int i = 0; i<n-1; i++){
//         graph[h[i][0]].push_back({h[i][1], L[i]});
//         graph[h[i][1]].push_back({h[i][0], L[i]});
//     }

//     build_centroid_decomp(0);
//     if(ans > 1e8) ans = -1;
//     return ans;
// }


// inline 
// void my_assert(int e) {if (!e) abort();}

// void read_input(){
//   int i;
//   my_assert(2==scanf("%d %d",&N,&K));
//   for(i=0; i<N-1; i++)
//     my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
//   my_assert(1==scanf("%d",&solution));
// }

// int main(){
//   int ans;
//   read_input();
//   ans = best_path(N,K,H,L);
//   if(ans==solution)
//     printf("Correct.\n");
//   else
//     printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

//   return 0;
// }


// signed main(){
//     // ios_base::sync_with_stdio(false);
//     // cin.tie(NULL);
//     // cout.tie(NULL);
 
//     int t=1; //cin>>t;
 
//     while(t--){
//         solve();
//     }
 
// }

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

/usr/bin/ld: /tmp/cc9LWU5y.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