제출 #1143847

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

race

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<bool>vis;
vector<map<ll,ll>>nodes;
vector<pair<ll,ll>>to_add; // lz propagation for subtrees
vector<vector<pair<ll,ll>>>g;
ll n,k;
ll cur_ans = -1;
void merge(ll node1, pair<ll,ll>b){
    ll node2 = b.first;
    ll val = b.second;
    pair<ll,ll>change = {0,0};
    if(nodes[node2].size()>nodes[node1].size()){
        swap(nodes[node1],nodes[node2]);
        swap(to_add[node1],to_add[node2]);
        to_add[node1].first+=val;
        to_add[node1].second++;

        change.first+=val;
        change.second++;
    }else{
        to_add[node2].first+=val;
        to_add[node2].second++;
    }
    // add current node to to_add[node1]

    pair<ll,ll>cur_node_val = make_pair(val-to_add[node2].first,1-to_add[node2].second);

    // check good answer for current node
    pair<ll,ll>cur_node_check = cur_node_val;

    cur_node_check.first+=change.first;
    cur_node_check.second+=change.second;

    cur_node_check.first+=to_add[node2].first;
    cur_node_check.second+=to_add[node2].second;

    cur_node_check.first-=to_add[node1].first;
    cur_node_check.second-=to_add[node1].second;

    //cout << "SEARCHING " << cur_node_check.first << " " << cur_node_check.second << " " << to_add[node1].first << " " << to_add[node1].second<< endl;
    if(nodes[node1].find(k-cur_node_check.first)!=nodes[node1].end()){
        if(cur_ans==-1)cur_ans = cur_node_check.second+nodes[node1][k-cur_node_check.first];
        else cur_ans=min(cur_ans,cur_node_check.second+nodes[node1][k-cur_node_check.first]);
    }

    // check good answers
    for(pair<ll,ll>it : nodes[node2]){
        it.first+=to_add[node2].first;
        it.second+=to_add[node2].second;

        it.first-=to_add[node1].first;
        it.second-=to_add[node1].second;

        //cout << "SEARCHING " << it.first << " " << it.second << " " << to_add[node1].first << " " << to_add[node1].second<< endl;
        if(nodes[node1].find(k-it.first)!=nodes[node1].end()){
            if(cur_ans==-1)cur_ans = it.second+nodes[node1][k-it.first];
            else cur_ans=min(cur_ans,it.second+nodes[node1][k-it.first]);
        }
    }

    // add current node
    if(nodes[node2].find(cur_node_val.first)==nodes[node2].end())nodes[node2][cur_node_val.first]=cur_node_val.second;
    else nodes[node2][cur_node_val.first]=min(cur_node_val.second,nodes[node2][cur_node_val.first]);

    // remake nodes[node2]
    for(pair<ll,ll> it : nodes[node2]){
        it.first+=to_add[node2].first;
        it.second+=to_add[node2].second;

        it.first-=to_add[node1].first;
        it.second-=to_add[node1].second;
        
        // add to current node
        if(nodes[node1].find(it.first)==nodes[node1].end())nodes[node1][it.first]=it.second;
        else nodes[node1][it.first]=min(it.second,nodes[node1][it.first]);
    }
}


void dfs(ll u){
    if(vis[u])return;
    vis[u]=true;
    for(auto it : g[u]){
        if(!vis[it.first]){
            dfs(it.first);
            merge(u,it);

            
            //cout << u << ":  ";
            //for(auto it2 : nodes[u]){
            //    cout << "("<<it2.first << ", " << it2.second << ")" << " ";
            //}cout << "--- " << to_add[u].first << ", " << to_add[u].second << endl;
        }
    }

    return;
}

ll best_path(ll N, ll K,ll H[][2], ll L[]){
    nodes.resize(N+2);
    vis.resize(N+2,0);
    to_add.resize(N+2,{0,0});
    g.resize(N+2);
    n=N,k=K;
    cur_ans = -1;
    for(ll i=0;i<N-1;i++){
        g[H[i][0]].push_back({H[i][1],L[i]});
        g[H[i][1]].push_back({H[i][0],L[i]});
    }ll root = 0;
    for(ll i=0;i<N;i++){
        if(g[root].size()>g[i].size())root=i;
    }dfs(root);// g[root].size()==1 siempre

    nodes.clear();
    vis.clear();
    g.clear();
    to_add.clear();
    return cur_ans;
}

/*
ll main(){
    ll t;
    cin >> t;
    while(t--){

        ll n,k;
        cin >> n >> k;
        ll H[n][2];
        ll L[n];
        for(ll i=0;i<n-1;i++){
            for(ll j=0;j<2;j++){
                cin >> H[i][j];
            }
        }
        for(ll i=0;i<n-1;i++)cin >> L[i];
        cout << best_path(n,k,H,L) << endl;
    }
    return 0;
}*/

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

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