Submission #672380

#	Time	Username	Problem	Language	Result	Execution time	Memory
672380		vjudge1	경주 (Race) (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include "race.h"


typedef long long ll;


const int N = 2e5 + 10;

bool vis[N];
int sz[N], k;
map<ll, int> mn;
ll ans = LLONG_MAX;
vector<pair<int, ll>> G[N];

int dfsSZ(int node, int par = -1)
{
    sz[node] = 1;
    for(auto &[ch, w]: G[node])
    {
        if(ch == par || vis[node])
            continue;
        sz[node] += dfsSZ(ch, node);
    }
    return sz[node];
}

int getCentroid(int node, int par, int &n)
{
    for(auto &[ch, w]: G[node])
    {
        if(ch == par || vis[ch])
            continue;

        if(sz[ch] << 1 > n)
            return getCentroid(ch, node, n);
    }
    return node;
}

void dfs(int node, int par, int dist, int dep)
{
    if(mn.count(dist))
        mn[dist] = min(mn[dist], dep);
    else
        mn[dist] = dep;

    for(auto &[ch, w]: G[node])
    {
        if(ch == par || vis[ch])
            continue;
        dfs(ch, node, dist + w, dep + 1);
    }
}

ll solve(int node, int par, int dist, int dep)
{
    if(dist > k)
        return LLONG_MAX;

    ll ret = LLONG_MAX;
    if(mn.count(k - dist) && mn[k - dist])
        ret = mn[k - dist] + dep;

    for(auto &[ch, w]: G[node])
    {
        if(ch == par || vis[ch])
            continue;
        ret = min(ret, solve(ch, node, dist + w, dep + 1));
    }
    return ret;
}

void solveSubTree(int centroid, int par, int d)
{

    for(auto &[ch, w]: G[centroid])
    {
        if(ch == par || vis[ch])
            continue;

        ans = min(ans, solve(ch, centroid, d + w, 1));
        dfs(ch, centroid, d + w, 1);
    }
    mn.clear();
}

void decompose(int node, int par, int d)
{
    dfsSZ(node, par);
    int centroid = getCentroid(node, par, sz[node]);

    vis[centroid] = true;
    solveSubTree(centroid, par, d);
    for(auto &[ch, w]: G[centroid])
    {
        if(ch == par || vis[ch])
            continue;
        decompose(ch, centroid, d + w);
    }
}

int best_path(int n, int K, int H[][2], int L[])
{
    k = K;
    for(int i = 0; i < n - 1; i++)
    {
        G[H[i][0]].emplace_back(H[i][1], L[i]);
        G[H[i][1]].emplace_back(H[i][0], L[i]);
    }
    if(ans == LLONG_MAX)
        return -1;
    else
        return ans;
}

Compilation message (stderr)

race.cpp:11:1: error: 'map' does not name a type
   11 | map<ll, int> mn;
      | ^~~
race.cpp:12:10: error: 'LLONG_MAX' was not declared in this scope
   12 | ll ans = LLONG_MAX;
      |          ^~~~~~~~~
race.cpp:2:1: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
    1 | #include "race.h"
  +++ |+#include <climits>
    2 | 
race.cpp:13:1: error: 'vector' does not name a type
   13 | vector<pair<int, ll>> G[N];
      | ^~~~~~
race.cpp: In function 'int dfsSZ(int, int)':
race.cpp:18:24: error: 'G' was not declared in this scope
   18 |     for(auto &[ch, w]: G[node])
      |                        ^
race.cpp: In function 'int getCentroid(int, int, int&)':
race.cpp:29:24: error: 'G' was not declared in this scope
   29 |     for(auto &[ch, w]: G[node])
      |                        ^
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:42:8: error: 'mn' was not declared in this scope
   42 |     if(mn.count(dist))
      |        ^~
race.cpp:43:20: error: 'min' was not declared in this scope
   43 |         mn[dist] = min(mn[dist], dep);
      |                    ^~~
race.cpp:47:24: error: 'G' was not declared in this scope
   47 |     for(auto &[ch, w]: G[node])
      |                        ^
race.cpp: In function 'll solve(int, int, int, int)':
race.cpp:58:16: error: 'LLONG_MAX' was not declared in this scope
   58 |         return LLONG_MAX;
      |                ^~~~~~~~~
race.cpp:58:16: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
race.cpp:60:14: error: 'LLONG_MAX' was not declared in this scope
   60 |     ll ret = LLONG_MAX;
      |              ^~~~~~~~~
race.cpp:60:14: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
race.cpp:61:8: error: 'mn' was not declared in this scope
   61 |     if(mn.count(k - dist) && mn[k - dist])
      |        ^~
race.cpp:64:24: error: 'G' was not declared in this scope
   64 |     for(auto &[ch, w]: G[node])
      |                        ^
race.cpp:68:15: error: 'min' was not declared in this scope
   68 |         ret = min(ret, solve(ch, node, dist + w, dep + 1));
      |               ^~~
race.cpp: In function 'void solveSubTree(int, int, int)':
race.cpp:76:24: error: 'G' was not declared in this scope
   76 |     for(auto &[ch, w]: G[centroid])
      |                        ^
race.cpp:81:15: error: 'min' was not declared in this scope
   81 |         ans = min(ans, solve(ch, centroid, d + w, 1));
      |               ^~~
race.cpp:84:5: error: 'mn' was not declared in this scope
   84 |     mn.clear();
      |     ^~
race.cpp: In function 'void decompose(int, int, int)':
race.cpp:94:24: error: 'G' was not declared in this scope
   94 |     for(auto &[ch, w]: G[centroid])
      |                        ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:107:9: error: 'G' was not declared in this scope
  107 |         G[H[i][0]].emplace_back(H[i][1], L[i]);
      |         ^
race.cpp:110:15: error: 'LLONG_MAX' was not declared in this scope
  110 |     if(ans == LLONG_MAX)
      |               ^~~~~~~~~
race.cpp:110:15: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
race.cpp:114:1: warning: control reaches end of non-void function [-Wreturn-type]
  114 | }
      | ^