제출 #482894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
482894		blue	경주 (Race) (IOI11_race)	C++17	100 / 100	1715 ms	112592 KiB

race

#include "race.h"
#include <vector>
#include <iostream>
#include <set>
#include <cstdlib>
using namespace std;

const int maxN = 200'000;

int N;
long long K;

vector<int> edge[1+maxN+1];
vector<long long> dist[1+maxN+1];

int ans = maxN;


vector<int> parent(1+maxN+1, maxN);
vector<int> subtree(1+maxN+1, 1);

int curr_size = 0;

vector<int> inaccessible(1+maxN+1, 0);

void dfs(int u, int p, int b)
{
    // cerr << "normal dfs " << u << ' ' << p << ' ' << b << '\n';
    curr_size++;
    parent[u] = p;
    subtree[u] = 1;
    for(int v: edge[u])
    {
        if(inaccessible[v]) continue;
        if(v == p || v == b) continue;
        dfs(v, u, b);
        subtree[u] += subtree[v];
    }
}

int getSize(int u, int v)
{
    if(parent[v] == u) return subtree[v];
    else return curr_size - subtree[u];
}


vector< pair<long long, int> > dist_list[1+maxN+1];

int error_ct = 0;

void dfs2(int u, int p, int r, int b, long long d, int e) //parent, root, banned
{
    // error_ct++;
    // if(error_ct == 100) exit(0);

    // cerr << "dfs2 " << u << ' ' << p << ' ' << r << ' ' << b << ' ' << d << ' ' << e << '\n';
    dist_list[r].push_back(make_pair(d, e));
    for(int z = 0; z < int(edge[u].size()); z++)
    {
        int v = edge[u][z];
        long long w = dist[u][z];

        if(v == p || v == b) continue;
        if(inaccessible[v]) continue;

        dfs2(v, u, r, b, d+w, e+1);
    }
}

multiset< pair<long long, int> > X;

void solve(int u, int p)
{
    // cerr << "\n\n\n\n\n";
    // cerr << "solve " << u << ' ' << p << '\n';
    curr_size = 0;
    dfs(u, p, p);

    int c = u;
    while(1)
    {
        bool flag = 0;
        for(int v: edge[c])
        {
            if(inaccessible[v]) continue;
            if(v == p) continue;
            if(2*getSize(c, v) > curr_size)
            {
                c = v;
                flag = 1;
                break;
            }
        }
        if(!flag) break;
    }
    // cerr << "c = " << c << '\n';


    inaccessible[c]++;
    // cerr << "don't access " << c << '\n';


    X.clear();
    for(int e = 0; e < int(edge[c].size()); e++)
    {
        int v = edge[c][e];
        long long w = dist[c][e];

        if(v == p) continue;

        if(inaccessible[v]) continue;

        dist_list[v].clear();
        dfs2(v, c, v, p, w, 1);
        for(auto x: dist_list[v]) X.insert(x);

        // cerr << c << " -> " << v << ": ";
        // for(auto x: dist_list[v]) cerr << x.first <<","<<x.second << " | ";
        // cerr << '\n';
    }

    auto y1 = X.lower_bound(make_pair(K, -1));
    if(y1 != X.end() && y1->first == K) ans = min(ans, y1->second);

    for(int e = 0; e < int(edge[c].size()); e++)
    {
        int v = edge[c][e];
        long long w = dist[c][e];

        if(v == p) continue;
        if(inaccessible[v]) continue;

        for(auto x: dist_list[v]) X.erase(X.find(x));

        for(auto x: dist_list[v])
        {
            auto y = X.lower_bound(make_pair(K - x.first, -1));
            if(y == X.end()) continue;
            if(y->first + x.first != K) continue;
            ans = min(ans, y->second + x.second);
        }

        for(auto x: dist_list[v]) X.insert(x);
    }





    for(int v: edge[c])
    {
        if(v == p) continue;
        if(inaccessible[v]) continue;
        solve(v, c);
    }
    inaccessible[c]--;
    // cerr << "do access " << c << '\n';
}



int best_path(int N_, int K_, int H_[][2], int L_[])
{
    N = N_;
    K = K_;

    for(int e = 0; e < N-1; e++)
    {
        edge[H_[e][0]].push_back(H_[e][1]);
        dist[H_[e][0]].push_back(L_[e]);

        edge[H_[e][1]].push_back(H_[e][0]);
        dist[H_[e][1]].push_back(L_[e]);
    }

    solve(0, maxN); //solve for paths belonging to centroid subtree of u

    if(ans == maxN) ans = -1;
    return ans;
}

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

race.cpp: In function 'void solve(int, int)':
race.cpp:129:19: warning: unused variable 'w' [-Wunused-variable]
  129 |         long long w = dist[c][e];
      |                   ^

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