Submission #527736

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

race

#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>
using namespace std;
 
#define ll long long
 
struct centroid_tree{
    vector<vector<pair<int, int>>> adj;
    vector<bool> vis;
    vector<int> par, sz;
    vector<ll> cnt;
    unordered_map<int, int> paths;
    int N, K, answer;
 
    void init(int _N, int len){
        int N = _N; K = len;
        adj = vector<vector<pair<int, int>>>(N+2, vector<pair<int, int>>());
        vis = vector<bool>(N+2);
        par = vector<int>(N+2);
        sz  = vector<int>(N+2);
        answer = 1e9;
    }
 
    void edge(int u, int v, int w){
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }
 
    int get_size(int cur, int p = -1){
        sz[cur] = 1;
        for(pair<int, int> ch : adj[cur]){
            if(ch.first != p && !vis[ch.first]){
                sz[cur] += get_size(ch.first, cur);
            }
        }
        return sz[cur];
    }
 
    int find_centroid(int cur, int p, int total){
        for(pair<int, int> ch : adj[cur]){
            if(sz[ch.first] > total/2 && ch.first != p && !vis[ch.first]){
                return find_centroid(ch.first, cur, total);
            }
        }
        return cur;
    }
 
    void calc(int cur, int p, int depth, int step, int flag){
        if(depth > K)return;
        if(flag){
            if(!paths.count(depth)){
                paths[depth] = step;
            }
            else{
                paths[depth] = min(paths[depth], step);
            }
        }
        else{
            if(paths.count(K - depth)){
                answer = min(answer, step + paths[K - depth]);
            }
        }
        for(pair<int, int> ch : adj[cur]){
            if(ch.first != p && !vis[ch.first]){
                calc(ch.first, cur, depth + ch.second, step + 1, flag);
            }
        }
    }
 
    void build(int cur = 1, int p = -1){
        get_size(cur);
        int cen = find_centroid(cur, p, sz[cur]);
        vis[cen] = 1;
        par[cen] = p;
 
        paths[0] = 0;
        for(pair<int, int> ch : adj[cen]){
            if(!vis[ch.first]){
                calc(ch.first, cen, ch.second, 1, 0);
                calc(ch.first, cen, ch.second, 1, 1);
            }
        }
        paths.clear();
 
        for(pair<int, int> ch : adj[cen]){
            if(!vis[ch.first]){
                build(ch.first, cen);
            }
        }
    }
};
 
centroid_tree CT;
 
int best_path(int N, int K, int H[][2], int L[]){
    CT.init(N, K);
    for(int i = 0; i < N-1; ++i){
        int u = H[i][0] + 1, v = H[i][1] + 1;
        CT.edge(u, v, L[i]);
    }
 
    CT.build();
 
    int answer = CT.answer;
 
    return (answer == 1e9 ? -1 : answer);
}

Compilation message (stderr)

race.cpp:22:5: error: 'unordered_map' does not name a type
   22 |     unordered_map<int, int> paths;
      |     ^~~~~~~~~~~~~
race.cpp: In member function 'void centroid_tree::calc(int, int, int, int, int)':
race.cpp:61:17: error: 'paths' was not declared in this scope
   61 |             if(!paths.count(depth)){
      |                 ^~~~~
race.cpp:69:16: error: 'paths' was not declared in this scope
   69 |             if(paths.count(K - depth)){
      |                ^~~~~
race.cpp: In member function 'void centroid_tree::build(int, int)':
race.cpp:86:9: error: 'paths' was not declared in this scope
   86 |         paths[0] = 0;
      |         ^~~~~