Submission #1142261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142261		dragdam	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include "race.h"

#define int long long
const int MAXN = 2e5+5;
const int inf = 2e9;


int n, r;
vector<array<int,2>> g[MAXN];
int ans;
map<int,int> m[MAXN];
array<int,2> o[MAXN];

void dfs(int x, int p){
    for(auto k : g[x]){
        if(k[0]==p) continue;
        dfs(k[0],x);
    }
    for(auto [k,w] : g[x]){
        if(k==p) continue;
        o[k][0] += w;
        o[k][1] += 1;
        if(m[k].size() > m[x].size()){
            swap(m[k], m[x]);
            swap(o[k], o[x]);
        }
        m[x][w-o[x][0]] = 1-o[x][1];
        for(pair<int,int> p : m[k]){
            if(m[x].find(r-p.first-o[x][0]-o[k][0])!=m[x].end()){
                ans = min(ans, p.second+m[x][r-p.first-o[x][0]-o[k][0]]) + o[k][1] + o[x][1];
            }
            p.first = p.first+o[k][0]-o[x][0];
            m[x][p.first] = min(p.second+1+o[k][1], (m[x][p.first] ? m[x][p.first] : inf));
        }
    }
    if(m[x].find(r-o[x][0])!=m[x].end()) ans = min(ans, m[x][r-o[x][0]] + o[x][1]);
    //cout << x << ' ' << o[x][0] << ' ' << o[x][1] << '\n';
    //for(auto p : m[x]) cout << p.first << ' ' << p.second << '\n'; cout << '\n';
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N; r = K;
    ans = inf;
    for(int i = 0; i < n; ++i){
        g[i].clear();
        m[i].clear();
        o[i] = {0,0};
    }
    for(int i = 0; i < n-1; ++i){
        int x = H[i][0], y = H[i][1], w = L[i];
        g[x].push_back({y,w});
        g[y].push_back({x,w});
    }
    dfs(0,0);
    return (ans==inf ? -1 : ans);
}

Compilation message (stderr)

race.cpp:9:1: error: 'vector' does not name a type
    9 | vector<array<int,2>> g[MAXN];
      | ^~~~~~
race.cpp:11:1: error: 'map' does not name a type
   11 | map<int,int> m[MAXN];
      | ^~~
race.cpp:12:1: error: 'array' does not name a type
   12 | array<int,2> o[MAXN];
      | ^~~~~
race.cpp: In function 'void dfs(long long int, long long int)':
race.cpp:15:18: error: 'g' was not declared in this scope
   15 |     for(auto k : g[x]){
      |                  ^
race.cpp:19:22: error: 'g' was not declared in this scope
   19 |     for(auto [k,w] : g[x]){
      |                      ^
race.cpp:21:9: error: 'o' was not declared in this scope
   21 |         o[k][0] += w;
      |         ^
race.cpp:23:12: error: 'm' was not declared in this scope
   23 |         if(m[k].size() > m[x].size()){
      |            ^
race.cpp:24:13: error: 'swap' was not declared in this scope
   24 |             swap(m[k], m[x]);
      |             ^~~~
race.cpp:27:9: error: 'm' was not declared in this scope
   27 |         m[x][w-o[x][0]] = 1-o[x][1];
      |         ^
race.cpp:28:13: error: 'pair' was not declared in this scope
   28 |         for(pair<int,int> p : m[k]){
      |             ^~~~
race.cpp:3:13: error: expected primary-expression before 'long'
    3 | #define int long long
      |             ^~~~
race.cpp:28:18: note: in expansion of macro 'int'
   28 |         for(pair<int,int> p : m[k]){
      |                  ^~~
race.cpp:35:5: error: expected primary-expression before '}' token
   35 |     }
      |     ^
race.cpp:34:10: error: expected ';' before '}' token
   34 |         }
      |          ^
      |          ;
   35 |     }
      |     ~     
race.cpp:35:5: error: expected primary-expression before '}' token
   35 |     }
      |     ^
race.cpp:34:10: error: expected ')' before '}' token
   34 |         }
      |          ^
      |          )
   35 |     }
      |     ~     
race.cpp:28:12: note: to match this '('
   28 |         for(pair<int,int> p : m[k]){
      |            ^
race.cpp:35:5: error: expected primary-expression before '}' token
   35 |     }
      |     ^
race.cpp:36:8: error: 'm' was not declared in this scope
   36 |     if(m[x].find(r-o[x][0])!=m[x].end()) ans = min(ans, m[x][r-o[x][0]] + o[x][1]);
      |        ^
race.cpp:36:20: error: 'o' was not declared in this scope
   36 |     if(m[x].find(r-o[x][0])!=m[x].end()) ans = min(ans, m[x][r-o[x][0]] + o[x][1]);
      |                    ^
race.cpp:36:48: error: 'min' was not declared in this scope
   36 |     if(m[x].find(r-o[x][0])!=m[x].end()) ans = min(ans, m[x][r-o[x][0]] + o[x][1]);
      |                                                ^~~
race.cpp: In function 'long long int best_path(long long int, long long int, long long int (*)[2], long long int*)':
race.cpp:45:9: error: 'g' was not declared in this scope
   45 |         g[i].clear();
      |         ^
race.cpp:46:9: error: 'm' was not declared in this scope
   46 |         m[i].clear();
      |         ^
race.cpp:47:9: error: 'o' was not declared in this scope
   47 |         o[i] = {0,0};
      |         ^
race.cpp:51:9: error: 'g' was not declared in this scope
   51 |         g[x].push_back({y,w});
      |         ^