Submission #67975

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
67975	2018-08-15T16:19:23 Z	tamtam	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

#include "grader.h"
#include <bits/stdc++.h>
#include<unordered_map>
#define F first
#define S second
typedef long long ll;
using namespace std;
int n,k;
int ans=1000000000;
vector<pair<int,int> > v[200010];
bool blocked [200010];
//int dep[1000000];
unordered_map<int,int> dep;
int Size[200010];
void dfsSize(int nod,int pt){
    Size[nod]=1;
   // cout <<"=============== "<<nod<<endl;
    for (int i=0;i<v[nod].size();i++){
        if (v[nod][i].F==pt||blocked[v[nod][i].F])continue;
        dfsSize(v[nod][i].F,nod);
        Size[nod]+=Size[v[nod][i].F];
    }
}

vector<pair<int,int> > comp;
void dfsAdd (int nod,int pt,int d,int d1){
    if (d>k)return;
    //dep[d]=min(dep[d],d1);
    comp.push_back({d,d1});
    for (int i=0;i<v[nod].size();i++){
        if (v[nod][i].F==pt||blocked[v[nod][i].F])continue;
        dfsAdd(v[nod][i].F,nod,d+v[nod][i].S,d1+1);
    }
}

void dfsRem(int nod,int pt,int d){
    if (d>k)return;
    dep[d]=1000000000;
    for (int i=0;i<v[nod].size();i++){
        if (v[nod][i].F==pt||blocked[v[nod][i].F])continue;
        dfsRem(v[nod][i].F,nod,d+v[nod][i].S);
    }
}
int Solve (int nod){
    //cout <<nod<<" -------------\n";
    dep[0]=0;
    int res=1000000000;
    for (int i=0;i<v[nod].size();i++){
        if (blocked[v[nod][i].F])continue;

        dfsAdd(v[nod][i].F,nod,v[nod][i].S,1);

        for (int i=0;i<comp.size();i++){
            int d=comp[i].F;
            int d1=comp[i].S;
            res=min(res,dep[k-d]+d1);
        }
        pair<int,int>qwe;
        while (comp.size()>0){
            qwe=comp[comp.size()-1];
            comp.pop_back();
            int d=qwe.F;
            int d1=qwe.S;
            dep[d]=min(dep[d],d1);
        }

        //res=min(res,dfsCount(v[nod][i].F,nod,v[nod][i].S,1));
    }
    dfsRem (nod,-1,0);
    return res;
}

void Create (int nod0){
    //cout <<nod0<<" asdf\n";
    dfsSize(nod0,-1);
    int nod=nod0;
    pair<int,int> cen={Size[nod0],nod0};
    //for (int i=0;i<n;i++){
        //cout <<Size[i]<<" ";
    //}cout <<endl;
    while (1){
        pair<int,int> mx={0,0};
        for (int i=0;i<v[nod].size();i++){
            if (blocked[v[nod][i].F])continue;
            int x=v[nod][i].F;
            int y=Size[x];
            if (y>Size[nod]){
                y=Size[nod0]-Size[nod];
            }
            mx=max(mx,{y,x});
        }
     //   cout <<mx.F<<" "<<mx.S<<endl;
        if (mx.F<cen.F){
            cen=mx;
            continue;
        }else {
            break;
        }
    }
    //cout <<cen.S<<endl;
    ans=min(Solve(cen.S),ans);
    blocked[cen.S]=true;
    for (int i=0;i<v[cen.S].size();i++){
        if (blocked[v[cen.S][i].F])continue;
        Create(v[cen.S][i].F);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    n=N;k=K;
    for (int i=0;i<=K;i++){
        dep[i]=1000000000;
    }
    for (int i=0;i<n-1;i++){
        int x=H[i][0];
        int y=H[i][1];
        //cout <<x<<" - "<<y<<endl;
        v[x].push_back({y,L[i]});
        v[y].push_back({x,L[i]});
    }
    Create (0);
    if (ans==1000000000)return -1;
    return ans;
}

Compilation message

race.cpp:1:10: fatal error: grader.h: No such file or directory
 #include "grader.h"
          ^~~~~~~~~~
compilation terminated.