Submission #931337

#	Time	Username	Problem	Language	Result	Execution time	Memory
931337		Ice_man	경주 (Race) (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

race

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

#define maxn 200005
#define mod 1000000007

using namespace std;

vector <pair <int, int>> v[maxn];
int sz[maxn];

int used[maxn];


int find_sz(int node, int parent)
{
    sz[node] = 1;

    for(pair <int, int> e : v[node])
    {
        if(e.X == parent || used[e.X] == true)
            continue;

        sz[node] += find_sz(nb);
    }

    return sz[node];
}



int find_centroid(int node, int parent, int _sz)
{
    for(pair <int, int> e : v[node])
    {
        if(e.X == parent || used[e.X] == true)
            continue;

        if(sz[e.X] * 2 > _sz)
            return find_centroid(e.X, node, _sz);

    }

    return node;
}

int c = 1e8;
int answer = INF;

int help[maxn];

void dfs1(int node, int parent, int depth, int weight, int k)
{
    if(weight > 0 && weight <= k)
        help[weight] = c;

    if(k > weight)
        help[k - weight] = c;

    for(pair <int, int> e : v[node])
    {
        if(e.X == parent || used[e.X] == true)
            continue;

        dfs1(e.X, node, depth + 1, weight + e.Y, k);
    }

}

void dfs2(int node, int parent, int depth, int weight, int k)
{
    if(weight <= k && parent != -1)
        ans = min(ans, help[k - weight] + depth);

    for(pair <int, int> e : v[node])
    {
        if(e.X == parent || used[e.X] == true)
            continue;

        dfs2(e.X, node, depth + 1, weight + e.Y, k);
    }

}


void dfs3(int node, int parent, int depth, int weight, int k)
{
    if (k >= weight && par != -1)
        help[weight] = min(help[weight], depth);

    for (pair <int, int> e : v[node])
    {
        if (e.X == par || used[e.X])
            continue;

        dfs1(e.X, node, depth + 1, weight + e.Y);
    }
}




void decompose(int node , int k)
{
    int cur_sz = find_sz(node);

    int centroid = find_centroid(node , -1 , cur_sz);

    used[centroid] = true;

    for(pair <int , int> e : v[centroid])
    {
        if(used[e.X] == true)
            continue;

        dfs1(e.X , centroid , 1 , e.Y , k);
    }

    for(pair <int , int> e : v[centroid])
    {
        if(used[e.X] == true)
            continue;

        dfs2(e.X, centroid , 1 , e.Y , k);
        dfs3(e.X , centroid , 1 , e.Y , k);

    }

    for(pair <int , int> e : v[centroid])
    {
        if(used[e.X] == true)
            continue;

        decompose(e.X , k);
    }
}



int best_path(int n , int k , int h[][2] , int l[])
{
    for(int i = 0; i < n - 1; i++)
    {
        v[h[i][0]].push_back({h[i][1] , l[i]});
        v[h[i][1]].push_back({h[i][0] , l[i]});
    }

    help[0] = 0;
    decompose(0 , k);

    if(ans > n)
        return -1;

    return ans;

}

Compilation message (stderr)

race.cpp: In function 'int find_sz(int, int)':
race.cpp:22:14: error: 'struct std::pair<int, int>' has no member named 'X'
   22 |         if(e.X == parent || used[e.X] == true)
      |              ^
race.cpp:22:36: error: 'struct std::pair<int, int>' has no member named 'X'
   22 |         if(e.X == parent || used[e.X] == true)
      |                                    ^
race.cpp:25:29: error: 'nb' was not declared in this scope
   25 |         sz[node] += find_sz(nb);
      |                             ^~
race.cpp: In function 'int find_centroid(int, int, int)':
race.cpp:37:14: error: 'struct std::pair<int, int>' has no member named 'X'
   37 |         if(e.X == parent || used[e.X] == true)
      |              ^
race.cpp:37:36: error: 'struct std::pair<int, int>' has no member named 'X'
   37 |         if(e.X == parent || used[e.X] == true)
      |                                    ^
race.cpp:40:17: error: 'struct std::pair<int, int>' has no member named 'X'
   40 |         if(sz[e.X] * 2 > _sz)
      |                 ^
race.cpp:41:36: error: 'struct std::pair<int, int>' has no member named 'X'
   41 |             return find_centroid(e.X, node, _sz);
      |                                    ^
race.cpp: At global scope:
race.cpp:49:14: error: 'INF' was not declared in this scope
   49 | int answer = INF;
      |              ^~~
race.cpp: In function 'void dfs1(int, int, int, int, int)':
race.cpp:63:14: error: 'struct std::pair<int, int>' has no member named 'X'
   63 |         if(e.X == parent || used[e.X] == true)
      |              ^
race.cpp:63:36: error: 'struct std::pair<int, int>' has no member named 'X'
   63 |         if(e.X == parent || used[e.X] == true)
      |                                    ^
race.cpp:66:16: error: 'struct std::pair<int, int>' has no member named 'X'
   66 |         dfs1(e.X, node, depth + 1, weight + e.Y, k);
      |                ^
race.cpp:66:47: error: 'struct std::pair<int, int>' has no member named 'Y'
   66 |         dfs1(e.X, node, depth + 1, weight + e.Y, k);
      |                                               ^
race.cpp: In function 'void dfs2(int, int, int, int, int)':
race.cpp:74:9: error: 'ans' was not declared in this scope; did you mean 'abs'?
   74 |         ans = min(ans, help[k - weight] + depth);
      |         ^~~
      |         abs
race.cpp:78:14: error: 'struct std::pair<int, int>' has no member named 'X'
   78 |         if(e.X == parent || used[e.X] == true)
      |              ^
race.cpp:78:36: error: 'struct std::pair<int, int>' has no member named 'X'
   78 |         if(e.X == parent || used[e.X] == true)
      |                                    ^
race.cpp:81:16: error: 'struct std::pair<int, int>' has no member named 'X'
   81 |         dfs2(e.X, node, depth + 1, weight + e.Y, k);
      |                ^
race.cpp:81:47: error: 'struct std::pair<int, int>' has no member named 'Y'
   81 |         dfs2(e.X, node, depth + 1, weight + e.Y, k);
      |                                               ^
race.cpp: In function 'void dfs3(int, int, int, int, int)':
race.cpp:89:24: error: 'par' was not declared in this scope
   89 |     if (k >= weight && par != -1)
      |                        ^~~
race.cpp:94:15: error: 'struct std::pair<int, int>' has no member named 'X'
   94 |         if (e.X == par || used[e.X])
      |               ^
race.cpp:94:20: error: 'par' was not declared in this scope
   94 |         if (e.X == par || used[e.X])
      |                    ^~~
race.cpp:94:34: error: 'struct std::pair<int, int>' has no member named 'X'
   94 |         if (e.X == par || used[e.X])
      |                                  ^
race.cpp:97:16: error: 'struct std::pair<int, int>' has no member named 'X'
   97 |         dfs1(e.X, node, depth + 1, weight + e.Y);
      |                ^
race.cpp:97:47: error: 'struct std::pair<int, int>' has no member named 'Y'
   97 |         dfs1(e.X, node, depth + 1, weight + e.Y);
      |                                               ^
race.cpp: In function 'void decompose(int, int)':
race.cpp:106:30: error: too few arguments to function 'int find_sz(int, int)'
  106 |     int cur_sz = find_sz(node);
      |                              ^
race.cpp:16:5: note: declared here
   16 | int find_sz(int node, int parent)
      |     ^~~~~~~
race.cpp:114:19: error: 'struct std::pair<int, int>' has no member named 'X'
  114 |         if(used[e.X] == true)
      |                   ^
race.cpp:117:16: error: 'struct std::pair<int, int>' has no member named 'X'
  117 |         dfs1(e.X , centroid , 1 , e.Y , k);
      |                ^
race.cpp:117:37: error: 'struct std::pair<int, int>' has no member named 'Y'
  117 |         dfs1(e.X , centroid , 1 , e.Y , k);
      |                                     ^
race.cpp:122:19: error: 'struct std::pair<int, int>' has no member named 'X'
  122 |         if(used[e.X] == true)
      |                   ^
race.cpp:125:16: error: 'struct std::pair<int, int>' has no member named 'X'
  125 |         dfs2(e.X, centroid , 1 , e.Y , k);
      |                ^
race.cpp:125:36: error: 'struct std::pair<int, int>' has no member named 'Y'
  125 |         dfs2(e.X, centroid , 1 , e.Y , k);
      |                                    ^
race.cpp:126:16: error: 'struct std::pair<int, int>' has no member named 'X'
  126 |         dfs3(e.X , centroid , 1 , e.Y , k);
      |                ^
race.cpp:126:37: error: 'struct std::pair<int, int>' has no member named 'Y'
  126 |         dfs3(e.X , centroid , 1 , e.Y , k);
      |                                     ^
race.cpp:132:19: error: 'struct std::pair<int, int>' has no member named 'X'
  132 |         if(used[e.X] == true)
      |                   ^
race.cpp:135:21: error: 'struct std::pair<int, int>' has no member named 'X'
  135 |         decompose(e.X , k);
      |                     ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:152:8: error: 'ans' was not declared in this scope; did you mean 'abs'?
  152 |     if(ans > n)
      |        ^~~
      |        abs
race.cpp:155:12: error: 'ans' was not declared in this scope; did you mean 'abs'?
  155 |     return ans;
      |            ^~~
      |            abs