Submission #479626

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

race

#include <bits/stdc++.h>
//#include "race.h"

#define pii     pair<int, int>
#define fi      first
#define se      second
#define pb      push_back

using namespace std;

const int MX=200007, INF=1e9+7;

vector<pii> adj[MX];
map<int, pii> ada[MX];
int N, K, ret=INF;

void add(int i, int j, int x){
    if(ada[i].count(j)){
        pii now=ada[i][j];
        if(now.se>x)
            now.se=x;
        if(now.fi>now.se)
            swap(now.fi, now.se);
        ada[i][j]=now;
    }else{
        ada[i][j]={x, INF};
    }
}
void DFS(int par, int wpar, int x){
    ada[x][0]={0, INF};
    for(auto i:adj[x]){

        int v=i.fi, w=i.se;
        if(v==par)
            continue;

        DFS(x, w, v);
        if(ada[x].size()<ada[v].size())
            swap(ada[x], ada[v]);

        for(auto j:ada[v]){
            int tot=j.fi, sisa=K-tot;
            pii cnt=j.se;
                //cout << "worst " << tot << ' ' << cnt.fi << ' ' << cnt.se << endl;
            if(tot>K)
                continue;
            if(ada[x].count(sisa)){
                ret=min(ret, ada[x][sisa].fi+ada[v][tot].fi);
            }

            add(x, tot, cnt.fi);
            add(x, tot, cnt.se);
        }
    }
    if(!x)
        return;
    for(auto i=ada[x].rbegin(); i!=ada[x].rend(); i++){

        pair<int, pii> tmp=*i;

        if(tmp.fi+wpar<=K){
            tmp.se.fi++;
            tmp.se.se++;
            ada[x][tmp.fi+wpar]=tmp.se;
        }
        if(tmp.fi){
            ada[x].erase(tmp.fi);
        }else
            ada[x][tmp.fi]={0, INF};
        }
}

int best_path(int n, int k, int H[][2], int L[]){
    N=n, K=k;
    for(int i=0, u, v, w; i<N-1; i++){
        u=H[i][0], v=H[i][1], w=L[i];
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    DFS(0, 0, 0);
    return (ret>=INF?-1:ret);
}

#define MAX_N 500000

static int H[MAX_N][2];
static int L[MAX_N];
static int solution;

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;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cczdSmye.o: in function `read_input()':
race.cpp:(.text+0x280): multiple definition of `read_input()'; /tmp/ccFsvBxg.o:grader.cpp:(.text+0x0): first defined here
/usr/bin/ld: /tmp/cczdSmye.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccFsvBxg.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status