Submission #720133

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

race

#include "race.h"

#define ll long long
const int nu = 3e5+5;
typedef pair<ll, ll> cap;
ll n, k, s[nu], f[nu], ans = 1e9, hh[nu];
bool r[nu];
vector< vector<cap> > g;
multiset<cap> ms;
int dfs(int u, int t)
{
    s[u] = 1;
    for(cap x : g[u])
    {
        int v = x.first;
        if(r[v] || v == t) continue;
        s[u] += dfs(v, u);
    }
    return s[u];
}
int get_centroid(int u, int t, int sum)
{
    for(cap x : g[u])
    {
        int v = x.first;
        if(r[v] || v == t) continue;
        if(s[v]*2 > sum) return get_centroid(v, u, sum);
    }
    return u;
}
void dfs2(int u, int t, int w, int ok)
{
    f[u] = f[t]+w; hh[u] = hh[t]+1;
    if(f[u] > k) return ;
    if(ok == 0)
    {
        cap o = {k-f[u], 0};
        multiset<cap> :: iterator it;
        it = lower_bound(ms.begin(), ms.end(), o);
        if((*it).first == k-f[u])
        ans = min(ans, hh[u]+(*it).second);
    }
    else ms.insert({f[u], hh[u]});
    for(cap x : g[u])
    {
        int v = x.first;
        ll l = x.second;
        if(v == t || r[v]) continue;
        dfs2(v, u, l, ok);
    }
}
void centroid(int u)
{
    int cnt = dfs(u, 0);
    int c = get_centroid(u, 0, cnt);
    r[c] = true;

    ms.insert({0, 0});
    ms.insert({1e15, 0});
    for(cap x : g[c])
    {
        int v = x.first;
        ll l = x.second;
        if(r[v]) continue;
        dfs2(v, 0, l, 0); dfs2(v, 0, l, 1);
    }

    while(!ms.empty()) ms.erase(*ms.begin());
    for(cap x : g[c])
    {
        int v = x.first;
        if(!r[v]) centroid(v);
    }
}
int best_path(int x, int y, int H[][2], int L[])
{
    n = x; k = y;
    g.resize(n+1);
    for(int i = 0; i < n-1; ++i)
    {
        ll u = H[i][0]; ll v = H[i][1]; ll c = L[i];
        u++; v++;
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }
    centroid(1);
    return ans;
}

Compilation message (stderr)

race.cpp:5:9: error: 'pair' does not name a type
    5 | typedef pair<ll, ll> cap;
      |         ^~~~
race.cpp:8:1: error: 'vector' does not name a type
    8 | vector< vector<cap> > g;
      | ^~~~~~
race.cpp:9:1: error: 'multiset' does not name a type
    9 | multiset<cap> ms;
      | ^~~~~~~~
race.cpp: In function 'int dfs(int, int)':
race.cpp:13:9: error: 'cap' was not declared in this scope
   13 |     for(cap x : g[u])
      |         ^~~
race.cpp:19:5: error: expected primary-expression before 'return'
   19 |     return s[u];
      |     ^~~~~~
race.cpp:18:6: error: expected ';' before 'return'
   18 |     }
      |      ^
      |      ;
   19 |     return s[u];
      |     ~~~~~~
race.cpp:19:5: error: expected primary-expression before 'return'
   19 |     return s[u];
      |     ^~~~~~
race.cpp:18:6: error: expected ')' before 'return'
   18 |     }
      |      ^
      |      )
   19 |     return s[u];
      |     ~~~~~~
race.cpp:13:8: note: to match this '('
   13 |     for(cap x : g[u])
      |        ^
race.cpp: In function 'int get_centroid(int, int, int)':
race.cpp:23:9: error: 'cap' was not declared in this scope
   23 |     for(cap x : g[u])
      |         ^~~
race.cpp:29:5: error: expected primary-expression before 'return'
   29 |     return u;
      |     ^~~~~~
race.cpp:28:6: error: expected ';' before 'return'
   28 |     }
      |      ^
      |      ;
   29 |     return u;
      |     ~~~~~~
race.cpp:29:5: error: expected primary-expression before 'return'
   29 |     return u;
      |     ^~~~~~
race.cpp:28:6: error: expected ')' before 'return'
   28 |     }
      |      ^
      |      )
   29 |     return u;
      |     ~~~~~~
race.cpp:23:8: note: to match this '('
   23 |     for(cap x : g[u])
      |        ^
race.cpp: In function 'void dfs2(int, int, int, int)':
race.cpp:37:9: error: 'cap' was not declared in this scope
   37 |         cap o = {k-f[u], 0};
      |         ^~~
race.cpp:38:9: error: 'multiset' was not declared in this scope
   38 |         multiset<cap> :: iterator it;
      |         ^~~~~~~~
race.cpp:38:26: error: '::iterator' has not been declared
   38 |         multiset<cap> :: iterator it;
      |                          ^~~~~~~~
race.cpp:39:9: error: 'it' was not declared in this scope; did you mean 't'?
   39 |         it = lower_bound(ms.begin(), ms.end(), o);
      |         ^~
      |         t
race.cpp:39:26: error: 'ms' was not declared in this scope; did you mean 's'?
   39 |         it = lower_bound(ms.begin(), ms.end(), o);
      |                          ^~
      |                          s
race.cpp:39:48: error: 'o' was not declared in this scope
   39 |         it = lower_bound(ms.begin(), ms.end(), o);
      |                                                ^
race.cpp:39:14: error: 'lower_bound' was not declared in this scope
   39 |         it = lower_bound(ms.begin(), ms.end(), o);
      |              ^~~~~~~~~~~
race.cpp:41:15: error: 'min' was not declared in this scope
   41 |         ans = min(ans, hh[u]+(*it).second);
      |               ^~~
race.cpp:43:10: error: 'ms' was not declared in this scope; did you mean 's'?
   43 |     else ms.insert({f[u], hh[u]});
      |          ^~
      |          s
race.cpp:44:9: error: 'cap' was not declared in this scope
   44 |     for(cap x : g[u])
      |         ^~~
race.cpp:51:1: error: expected primary-expression before '}' token
   51 | }
      | ^
race.cpp:50:6: error: expected ';' before '}' token
   50 |     }
      |      ^
      |      ;
   51 | }
      | ~     
race.cpp:51:1: error: expected primary-expression before '}' token
   51 | }
      | ^
race.cpp:50:6: error: expected ')' before '}' token
   50 |     }
      |      ^
      |      )
   51 | }
      | ~     
race.cpp:44:8: note: to match this '('
   44 |     for(cap x : g[u])
      |        ^
race.cpp:51:1: error: expected primary-expression before '}' token
   51 | }
      | ^
race.cpp: In function 'void centroid(int)':
race.cpp:58:5: error: 'ms' was not declared in this scope; did you mean 's'?
   58 |     ms.insert({0, 0});
      |     ^~
      |     s
race.cpp:60:9: error: 'cap' was not declared in this scope
   60 |     for(cap x : g[c])
      |         ^~~
race.cpp:68:5: error: expected primary-expression before 'while'
   68 |     while(!ms.empty()) ms.erase(*ms.begin());
      |     ^~~~~
race.cpp:66:6: error: expected ';' before 'while'
   66 |     }
      |      ^
      |      ;
   67 | 
   68 |     while(!ms.empty()) ms.erase(*ms.begin());
      |     ~~~~~
race.cpp:68:5: error: expected primary-expression before 'while'
   68 |     while(!ms.empty()) ms.erase(*ms.begin());
      |     ^~~~~
race.cpp:66:6: error: expected ')' before 'while'
   66 |     }
      |      ^
      |      )
   67 | 
   68 |     while(!ms.empty()) ms.erase(*ms.begin());
      |     ~~~~~
race.cpp:60:8: note: to match this '('
   60 |     for(cap x : g[c])
      |        ^
race.cpp:69:9: error: 'cap' was not declared in this scope
   69 |     for(cap x : g[c])
      |         ^~~
race.cpp:74:1: error: expected primary-expression before '}' token
   74 | }
      | ^
race.cpp:73:6: error: expected ';' before '}' token
   73 |     }
      |      ^
      |      ;
   74 | }
      | ~     
race.cpp:74:1: error: expected primary-expression before '}' token
   74 | }
      | ^
race.cpp:73:6: error: expected ')' before '}' token
   73 |     }
      |      ^
      |      )
   74 | }
      | ~     
race.cpp:69:8: note: to match this '('
   69 |     for(cap x : g[c])
      |        ^
race.cpp:74:1: error: expected primary-expression before '}' token
   74 | }
      | ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:78:5: error: 'g' was not declared in this scope
   78 |     g.resize(n+1);
      |     ^