제출 #931342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
931342		Ice_man	Race (IOI11_race)	C++14	컴파일 에러	0 ms	0 KiB

race

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

#define maxn 200005
#define mod 1000000007
#define INF 1000000005

#define X first
#define Y second

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(e.X , node);
    }

    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 ans = 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;

}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'void dfs3(int, int, int, int, int)':
race.cpp:93:24: error: 'par' was not declared in this scope
   93 |     if (k >= weight && par != -1)
      |                        ^~~
race.cpp:98:20: error: 'par' was not declared in this scope
   98 |         if (e.X == par || used[e.X])
      |                    ^~~
race.cpp:101:48: error: too few arguments to function 'void dfs1(int, int, int, int, int)'
  101 |         dfs1(e.X, node, depth + 1, weight + e.Y);
      |                                                ^
race.cpp:57:6: note: declared here
   57 | void dfs1(int node, int parent, int depth, int weight, int k)
      |      ^~~~
race.cpp: In function 'void decompose(int, int)':
race.cpp:110:30: error: too few arguments to function 'int find_sz(int, int)'
  110 |     int cur_sz = find_sz(node);
      |                              ^
race.cpp:20:5: note: declared here
   20 | int find_sz(int node, int parent)
      |     ^~~~~~~