Submission #952273

#	Time	Username	Problem	Language	Result	Execution time	Memory
952273		bunhadasou	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define PB push_back
#define EB emplace_back
#define bit(n,i) ((n>>i)&1)
#define ll long long
#define sz(a) (int)a.size()
#define all(x) x.begin(),x.end()
#define TASK "cf"

using namespace std;

const int maxn=2e5+5;
map<int,int>dp[maxn];
int n,k;
vector<pair<int,int>>adj[maxn];
int el[maxn],ew[maxn];
int ans;
//dp[u][i]: so canh nho nhat tao thanh trong so i tai u

void mini(int &a,int b){
    if (a>b) a=b;
}

void dfs(int u,int p) {
    dp[u][0]=el[u]=ew[u]=0;
    for (auto v:adj[u]) {
        if (v.fi!=p) {
            dfs(v.fi,u);
            if (dp[u].size()>dp[v.fi].size()){
                for (auto x:dp[v.fi]){
                    int cur_wei=x.fi+ew[v.fi]+v.se;
                    int cur_len=x.se+el[v.fi]+1;
                    int add=k-cur_wei-ew[u];
                    if (dp[u][add])mini(ans,dp[u][add]+el[u]+cur_len);
                }
                for (auto x:dp[v.fi]){
                    int cur_wei=x.fi+ew[v.fi]+v.se;
                    int cur_len=x.se+el[v.fi]+1;
                    int add_wei=cur_wei-ew[u];
                    int add_len=cur_len-el[u];
                    if (dp[u][add_wei]) mini(dp[u][add_wei],add_len);
                    else dp[u][add_wei]=add_len;
                }
                dp[v.fi].clear();
            }
            else {
                for (auto x:dp[u]){
                    int cur_wei=x.fi+ew[v.fi]+v.se;
                    int cur_len=x.se+el[v.fi]+1;
                    int add=k-cur_wei-ew[v.fi];
                    if (dp[u][add])mini(ans,dp[u][add]+el[u]+cur_len);
                }
                for (auto x:dp[u]){
                    int cur_wei=x.fi+ew[v.fi]+v.se;
                    int cur_len=x.se+el[v.fi]+1;
                    int add_wei=cur_wei-ew[v.fi];
                    int add_len=cur_len-el[v.fi];
                    if (dp[v.fi][add_wei]) mini(dp[v.fi][add_wei],add_len);
                    else dp[v.fi][add_wei]=add_len;
                }
                swap(dp[u],dp[v.fi]);
                swap(el[u],el[v.fi]);
                swap(ew[u],ew[v.fi]);
                dp[v.fi].clear();
            }
        }
    }
}


int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>n>>k;
    ans=n;
    for (int i=1;i<n;i++) {
        int x,y,z;cin>>x>>y>>z;
        adj[x].PB(mp(y,z));
        adj[y].PB(mp(x,z));
    }
    dfs(1,-1);
    if (ans==n) cout<<-1<<"\n";else cout<<ans<<"\n";

    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccf67MQz.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccOuKAuy.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccOuKAuy.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