Submission #639076

#	Time	Username	Problem	Language	Result	Execution time	Memory
639076		Andrey	Race (IOI11_race)	C++14	100 / 100	1422 ms	67232 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;

int n,k,ans = INT_MAX;
vector<pair<int,int>> haha[200001];
vector<int> st(200001);
vector<bool> yeah(200001,true);
int dfs(int a, int t) {
    int sb = 1;
    for(int i = 0; i < haha[a].size(); i++) {
        if(haha[a][i].first != t && yeah[haha[a][i].first]) {
            sb+=dfs(haha[a][i].first,a);
        }
    }
    st[a] = sb;
    return sb;
}

void calc(map<int,int>& wut, int a, int d, int sb, int t) {
    if(wut[k-sb] != 0 || k == sb) {
        ans = min(ans,wut[k-sb]+d);
    }
    for(int i = 0; i < haha[a].size(); i++) {
        if(yeah[haha[a][i].first] && haha[a][i].first != t) {
            calc(wut,haha[a][i].first,d+1,sb+haha[a][i].second,a);
        }
    }
}

void update(map<int,int>& wut, int a, int d, int sb, int t) {
    if(wut[sb] != 0) {
        wut[sb] = min(wut[sb],d);
    }
    else {
        wut[sb] = d;
    }
    for(int i = 0; i < haha[a].size(); i++) {
        if(yeah[haha[a][i].first] && haha[a][i].first != t) {
            update(wut,haha[a][i].first,d+1,sb+haha[a][i].second,a);
        }
    }
}

void dude(int a) {
    dfs(a,-1);
    int c = 0,p = a;
    while(p != -1) {
        c = p;
        p = -1;
        for(int i = 0; i < haha[c].size(); i++) {
            if(yeah[haha[c][i].first] && st[c] > st[haha[c][i].first] && st[haha[c][i].first] > st[a]/2) {
                p = haha[c][i].first;
            }
        }
    }
    map<int,int> wut;
    wut[0] = 0;
    for(int i = 0; i < haha[c].size(); i++) {
        if(yeah[haha[c][i].first]) {
            calc(wut,haha[c][i].first,1,haha[c][i].second,c);
            update(wut,haha[c][i].first,1,haha[c][i].second,c);
        }
    }
    yeah[c] = false;
    for(int i = 0; i < haha[c].size(); i++) {
        if(yeah[haha[c][i].first]) {
            dude(haha[c][i].first);
        }
    }
    yeah[c] = true;
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    k = K;
    for(int i = 0; i < n-1; i++) {
        haha[H[i][0]].push_back({H[i][1],L[i]});
        haha[H[i][1]].push_back({H[i][0],L[i]});
    }
    dude(0);
    if(ans == INT_MAX) {
        ans = -1;
    }
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'int dfs(int, int)':
race.cpp:11:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i = 0; i < haha[a].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'void calc(std::map<int, int>&, int, int, int, int)':
race.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0; i < haha[a].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'void update(std::map<int, int>&, int, int, int, int)':
race.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0; i < haha[a].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'void dude(int)':
race.cpp:51:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int i = 0; i < haha[c].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~
race.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < haha[c].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~
race.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i = 0; i < haha[c].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~

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