제출 #672388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
672388		vjudge1	경주 (Race) (IOI11_race)	C++14	0 / 100	12 ms	23764 KiB

race

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

using namespace std;


typedef long long ll;


const int N = 1e6;

bool vis[N];
int sz[N], k;
int ans = -1;
map<ll, int> mn;
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] * 2 > n)
            return getCentroid(ch, node, n);
    }
    return node;
}

void dfs(int node, int par = -1, ll dist = 0, int dep = 0)
{
    if(mn.find(k - dist) != mn.end())
        ans = (ans == -1 ? mn[k - dist] + dep : min(ans, mn[k - dist] + dep));

    if(mn.find(dist) != mn.end())
        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);
    }
}


void decompose(int node = 0)
{
    int centroid = getCentroid(node, -1, dfsSZ(node));

    mn.clear();
    dfs(centroid);
    vis[centroid] = true;

    for(auto &[ch, w]: G[centroid])
    {
        if(vis[ch])
            continue;
        decompose(ch);
    }
}

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]);
    }
    decompose();
    return ans;
}

//int main()
//{
//    int n, K;
//    cin >> n >> K;
//    int H[n][2], L[n];
//    for(int i = 0; i < n - 1; i++)
//        cin >> H[i][0] >> H[i][1];
//    for(int i = 0; i < n - 1; i++)
//        cin >> L[i];
//
//    cout << best_path(n, K, H, L) << '\n';
//}

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

race.cpp: In function 'int dfsSZ(int, int)':
race.cpp:21:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for(auto &[ch, w]: G[node])
      |               ^
race.cpp: In function 'int getCentroid(int, int, int)':
race.cpp:32:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |     for(auto &[ch, w]: G[node])
      |               ^
race.cpp: In function 'void dfs(int, int, ll, int)':
race.cpp:53:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |     for(auto &[ch, w]: G[node])
      |               ^
race.cpp: In function 'void decompose(int)':
race.cpp:70:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |     for(auto &[ch, w]: G[centroid])
      |               ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57