Submission #67977

#	Time	Username	Problem	Language	Result	Execution time	Memory
67977		tamtam	Race (IOI11_race)	C++14	9 / 100	1572 ms	263168 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[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 (stderr)

race.cpp: In function 'void dfsSize(int, int)':
race.cpp:18: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 dfsAdd(int, int, int, int)':
race.cpp:30: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:39: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:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
race.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<comp.size();i++){
                      ~^~~~~~~~~~~~
race.cpp: In function 'void Create(int)':
race.cpp:83:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<v[nod].size();i++){
                      ~^~~~~~~~~~~~~~
race.cpp:103: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: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57