Submission #1360958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1360958		eyadooz	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

// #include<bits/stdc++.h>
#include "race.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define endl '\n'
int k, cn=0, sub[200005], ans=INT_MAX, pref[200005], depth[200005];
vector<pii> adj[200005];
bool deleted[200005];
map<int, int> mn;
void dfs(int x, int p=-1) 
{
    cn++;
    sub[x]=1;
    for(auto[i, _] : adj[x]) 
    {
        if(!deleted[i]&&i!=p) {dfs(i, x);sub[x]+=sub[i];}
    }
}
int centr(int x, int p=-1) 
{
    for(auto[i, _] : adj[x]) 
    {
        if(i!=p&&!deleted[i]&&sub[i]>cn/2) return centr(i, x);
    }
    return x;
}
void init(int x, int p=-1) 
{
    for(auto[i, w] : adj[x]) 
    {
        if(i==p||deleted[i]) continue;
        pref[i]=pref[x]+w;
        depth[i]=depth[x]+1;
        init(i, x);
    }
}
void query(int x, int p=-1) 
{
    if(pref[x]==k) ans=min(ans, depth[x]);
    if(mn.count(k-pref[x])) ans=min(ans, mn[k-pref[x]]+depth[x]);
    for(auto[i, _]:adj[x]) 
    {
        if(i!=p&&!deleted[i]) query(i, x);
    }
}
void update(int x, int p=-1) 
{
    if(!mn.count(pref[x])) mn[pref[x]]=depth[x];
    else mn[pref[x]]=min(mn[pref[x]], depth[x]);
    for(auto[i, _]:adj[x]) 
    {
        if(i!=p&&!deleted[i]) update(i, x);
    }
}
void solve(int x) 
{
    mn.clear();
    mn[0]=0;
    pref[x]=0;
    depth[x]=0;
    init(x);
    for(auto[i, _] : adj[x]) 
    {
        if(deleted[i]) continue;
        query(i);
        update(i);
    }
}
void decompose(int v) 
{
    cn=0;
    dfs(v);
    int cen=centr(v);
    solve(cen);
    deleted[cen]=1;
    for(auto[i, _] : adj[cen]) 
    {
        if(!deleted[i]) decompose(i);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    k=K;
    for(int i = 0;i < N-1;i++) 
    {
        auto[x, y]=H[i];
        auto w=L[i];
        adj[x].pb({y, w});
        adj[y].pb({x, w});
    }
    decompose(0);
    return (ans==INT_MAX?-1:ans);
}
// int main()
// {
//     cin.tie(0) -> sync_with_stdio(0);

//     // int h[2][2];
//     // h[0][0]=0;
//     // h[1][0]=1;
//     // // h[2][0]=1;


//     // h[0][1]=1;
//     // h[1][1]=2;
//     // // h[2][1]=3;
//     // int l[2];
//     // l[0]=1;
//     // l[1]=1;
//     // // l[2]=4;
//     int H[4][2] = {{0,1},{1,2},{2,3},{3,4}};
//     int L[4] = {1,1,1,1};
//     cout << best_path(5, 3, H, L);    
// }

Compilation message (stderr)

race.cpp:7:9: error: 'pair' does not name a type
    7 | typedef pair<int, int> pii;
      |         ^~~~
race.cpp:8:9: error: 'pair' does not name a type
    8 | typedef pair<ll, ll> pll;
      |         ^~~~
race.cpp:14:31: error: 'INT_MAX' was not declared in this scope
   14 | int k, cn=0, sub[200005], ans=INT_MAX, pref[200005], depth[200005];
      |                               ^~~~~~~
race.cpp:3:1: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
    2 | #include "race.h"
  +++ |+#include <climits>
    3 | 
race.cpp:15:8: error: 'pii' was not declared in this scope
   15 | vector<pii> adj[200005];
      |        ^~~
race.cpp:15:8: error: 'pii' was not declared in this scope
race.cpp:15:8: error: 'pii' was not declared in this scope
race.cpp:15:8: error: 'pii' was not declared in this scope
race.cpp:15:8: error: 'pii' was not declared in this scope
race.cpp:15:8: error: 'pii' was not declared in this scope
race.cpp:15:8: error: 'pii' was not declared in this scope
race.cpp:15:8: error: 'pii' was not declared in this scope
race.cpp:15:8: error: 'pii' was not declared in this scope
race.cpp:15:1: error: 'vector' does not name a type
   15 | vector<pii> adj[200005];
      | ^~~~~~
race.cpp:17:1: error: 'map' does not name a type
   17 | map<int, int> mn;
      | ^~~
race.cpp: In function 'void dfs(int, int)':
race.cpp:22:22: error: 'adj' was not declared in this scope
   22 |     for(auto[i, _] : adj[x])
      |                      ^~~
race.cpp: In function 'int centr(int, int)':
race.cpp:29:22: error: 'adj' was not declared in this scope
   29 |     for(auto[i, _] : adj[x])
      |                      ^~~
race.cpp: In function 'void init(int, int)':
race.cpp:37:22: error: 'adj' was not declared in this scope
   37 |     for(auto[i, w] : adj[x])
      |                      ^~~
race.cpp:40:9: error: 'pref' was not declared in this scope
   40 |         pref[i]=pref[x]+w;
      |         ^~~~
race.cpp:41:9: error: 'depth' was not declared in this scope
   41 |         depth[i]=depth[x]+1;
      |         ^~~~~
race.cpp: In function 'void query(int, int)':
race.cpp:47:8: error: 'pref' was not declared in this scope
   47 |     if(pref[x]==k) ans=min(ans, depth[x]);
      |        ^~~~
race.cpp:47:33: error: 'depth' was not declared in this scope
   47 |     if(pref[x]==k) ans=min(ans, depth[x]);
      |                                 ^~~~~
race.cpp:47:24: error: 'min' was not declared in this scope
   47 |     if(pref[x]==k) ans=min(ans, depth[x]);
      |                        ^~~
race.cpp:48:8: error: 'mn' was not declared in this scope; did you mean 'cn'?
   48 |     if(mn.count(k-pref[x])) ans=min(ans, mn[k-pref[x]]+depth[x]);
      |        ^~
      |        cn
race.cpp:48:19: error: 'pref' was not declared in this scope
   48 |     if(mn.count(k-pref[x])) ans=min(ans, mn[k-pref[x]]+depth[x]);
      |                   ^~~~
race.cpp:48:56: error: 'depth' was not declared in this scope
   48 |     if(mn.count(k-pref[x])) ans=min(ans, mn[k-pref[x]]+depth[x]);
      |                                                        ^~~~~
race.cpp:48:33: error: 'min' was not declared in this scope
   48 |     if(mn.count(k-pref[x])) ans=min(ans, mn[k-pref[x]]+depth[x]);
      |                                 ^~~
race.cpp:49:20: error: 'adj' was not declared in this scope
   49 |     for(auto[i, _]:adj[x])
      |                    ^~~
race.cpp: In function 'void update(int, int)':
race.cpp:56:9: error: 'mn' was not declared in this scope; did you mean 'cn'?
   56 |     if(!mn.count(pref[x])) mn[pref[x]]=depth[x];
      |         ^~
      |         cn
race.cpp:56:18: error: 'pref' was not declared in this scope
   56 |     if(!mn.count(pref[x])) mn[pref[x]]=depth[x];
      |                  ^~~~
race.cpp:56:40: error: 'depth' was not declared in this scope
   56 |     if(!mn.count(pref[x])) mn[pref[x]]=depth[x];
      |                                        ^~~~~
race.cpp:57:39: error: 'depth' was not declared in this scope
   57 |     else mn[pref[x]]=min(mn[pref[x]], depth[x]);
      |                                       ^~~~~
race.cpp:57:22: error: 'min' was not declared in this scope
   57 |     else mn[pref[x]]=min(mn[pref[x]], depth[x]);
      |                      ^~~
race.cpp:58:20: error: 'adj' was not declared in this scope
   58 |     for(auto[i, _]:adj[x])
      |                    ^~~
race.cpp: In function 'void solve(int)':
race.cpp:65:5: error: 'mn' was not declared in this scope; did you mean 'cn'?
   65 |     mn.clear();
      |     ^~
      |     cn
race.cpp:67:5: error: 'pref' was not declared in this scope
   67 |     pref[x]=0;
      |     ^~~~
race.cpp:68:5: error: 'depth' was not declared in this scope
   68 |     depth[x]=0;
      |     ^~~~~
race.cpp:70:22: error: 'adj' was not declared in this scope
   70 |     for(auto[i, _] : adj[x])
      |                      ^~~
race.cpp: In function 'void decompose(int)':
race.cpp:84:22: error: 'adj' was not declared in this scope
   84 |     for(auto[i, _] : adj[cen])
      |                      ^~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:96:9: error: 'adj' was not declared in this scope
   96 |         adj[x].pb({y, w});
      |         ^~~
race.cpp:100:18: error: 'INT_MAX' was not declared in this scope
  100 |     return (ans==INT_MAX?-1:ans);
      |                  ^~~~~~~
race.cpp:100:18: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?