Submission #67999

#	Time	Username	Problem	Language	Result	Execution time	Memory
67999		tamtam	Race (IOI11_race)	C++14	43 / 100	3053 ms	28168 KiB

race

#include "race.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[1000010];
int P[200010];
//unordered_map<int,int> dep;
int Size[200010];
void dfsSize(int nod,int pt){
    Size[nod]=1;
    P[nod]=pt;
   // 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;
int dfsAdd (int nod,int pt,int d,int d1){
    if (d>k)return 1000000000;
    //dep[d]=min(dep[d],d1);
    int res=dep[k-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;
        res=min(res,dfsAdd(v[nod][i].F,nod,d+v[nod][i].S,d1+1));
    }
    return res;
}

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 rrr=0;
int Solve (int nod){
    rrr++;
    if (rrr>n)assert(0);
    //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;

        res=min(res,dfsAdd(v[nod][i].F,nod,v[nod][i].S,1));
        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;
}
int rr;
void Create (int nod0){
    rr++;
    if (rr>n)assert(0);
    //if (vis[nod0]>)return;
    //vis[nod0]=1;
    //cout <<nod0<<" asdf\n";
    dfsSize(nod0,-1);
    pair<int,int> cen={Size[nod0],nod0};
    //for (int i=0;i<n;i++){
        //cout <<Size[i]<<" ";
    //}cout <<endl;
    int centroid=nod0,mn=1e9;
    int nod=nod0,curmx=0;
    while (1){
        int z=0;
        for (int i=0;i<v[nod].size();i++){
            if (blocked[v[nod][i].F])continue;
            if (v[nod][i].F==P[nod]){
                if (curmx<Size[nod0]-Size[nod])z=v[nod][i].F;
                curmx=max(curmx,Size[nod0]-Size[nod]);
                continue;
            }
            if (curmx<Size[v[nod][i].F])z=v[nod][i].F;
            curmx=max(curmx,Size[v[nod][i].F]);
        }
        if (curmx<mn){
            mn=curmx;
            centroid=nod;
            nod=z;
            curmx=0;
        }else break;
    }
    cen.S=centroid;
    //if (blocked[cen.S])return;
    //cout <<cen.S<<endl;
    blocked[cen.S]=true;
    ans=min(Solve(cen.S),ans);
    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;
    //if (n<80000||n>100000)return 0;

    //if (K<)return 0;

    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 (stderr)

race.cpp: In function 'void dfsSize(int, int)':
race.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
race.cpp: In function 'int dfsAdd(int, int, int, int)':
race.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
race.cpp: In function 'void dfsRem(int, int, int)':
race.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
race.cpp: In function 'int Solve(int)':
race.cpp:55:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
race.cpp: In function 'void Create(int)':
race.cpp:89:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<v[nod].size();i++){
                      ~^~~~~~~~~~~~~~
race.cpp:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[cen.S].size();i++){
                  ~^~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57