제출 #405091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
405091		Vladth11	경주 (Race) (IOI11_race)	C++14	100 / 100	1089 ms	52536 KiB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
#include"race.h"

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 200001;
const ll INF = (1LL << 60);
const ll MOD = 1000000009;
const ll BLOCK = 225;
const ll base = 31;
const ll base2 = 53;
const ll nr_of_bits = 21;

vector <pii> v[NMAX];
int best = 2e9;
int k;
int sz[NMAX];
int total;
int viz[NMAX];
int d[NMAX];
struct ura{
    int first, pfirst, second, psecond;
};
ura mp[1000001];

void getsize(int node, int p){
    sz[node] = 1;
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
      	getsize(x.first, node);
        sz[node] += sz[x.first];
    }
  total = sz[node];
}

int centroid(int node, int p){
    for(auto x : v[node]){
        if(viz[x.first] || x.first == p){
            continue;
        }
        if(sz[x.first] > total / 2)
            return centroid(x.first, node);
    }
    return node;
}

int OneCentroid(int node){
    getsize(node, 0);
    return centroid(node, 0);
}


void ComputeDist(int node, int p, int subTree, int dist, int level){
    d[node] = dist;
    pii act = {level, subTree};
    if(dist <= k && (mp[dist].pfirst == -1 || mp[dist].first >= level)){
        if(mp[dist].pfirst != subTree){
            swap(mp[dist].pfirst, mp[dist].psecond);
            swap(mp[dist].first, mp[dist].second);
        }
        mp[dist].first = level;
        mp[dist].pfirst = subTree;
    }else if(dist <= k && mp[dist].pfirst != subTree && (mp[dist].psecond == -1 || mp[dist].second >= level)){
        mp[dist].second = level;
        mp[dist].psecond = subTree;
    }
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        ComputeDist(x.first, node, subTree, d[node] + x.second, level + 1);
    }
}

void Erase(int node, int p, int subTree, int level){
    int dist = d[node];
    pii act = {level, subTree};
    if(dist <= k && (mp[dist].pfirst != -1 && mp[dist].pfirst == subTree)){
        swap(mp[dist].pfirst, mp[dist].psecond);
        swap(mp[dist].first, mp[dist].second);
        mp[dist].psecond = -1;
        mp[dist].second = 2e9;
    }
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        Erase(x.first, node, subTree, level + 1);
    }
}

void SuperErase(int node, int p, int subTree, int level){
    int dist = d[node];
    pii act = {level, subTree};
    if(dist <= k){
       mp[dist] = {(int)2e9, -1, (int)2e9, -1};
    }
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        SuperErase(x.first, node, subTree, level + 1);
    }
}


void Add(int node, int p, int subTree, int level){
    int dist = d[node];
    pii act = {level, subTree};
    if(dist <= k && (mp[dist].pfirst == -1 || mp[dist].first >= level)){
        if(mp[dist].pfirst != subTree){
            swap(mp[dist].pfirst, mp[dist].psecond);
            swap(mp[dist].first, mp[dist].second);
        }
        mp[dist].first = level;
        mp[dist].pfirst = subTree;
    }else if(dist <= k && mp[dist].pfirst != subTree && (mp[dist].psecond == -1 || mp[dist].second >= level)){
        mp[dist].second = level;
        mp[dist].psecond = subTree;
    }
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        Add(x.first, node, subTree, level + 1);
    }
}

void Compute(int node, int p, int level){
    int trb = k - d[node];
    if(trb >= 0 && mp[trb].pfirst != -1)
    {
        int b = mp[trb].first;
        best = min(best, b + level);
    }
    for(auto x : v[node]){
        if(x.first == p || viz[x.first])
            continue;
        Compute(x.first, node, level + 1);
    }
}


void CD(int node){
    int c = OneCentroid(node);
    viz[c] = 1;
    mp[0].first = 0;
    mp[0].pfirst = 0;
    for(auto x : v[c]){
        if(viz[x.first])
            continue;
        ComputeDist(x.first, c, x.first, x.second, 1);
    }
    for(auto x : v[c]){
        if(viz[x.first])
            continue;
        Erase(x.first, c, x.first, 1);
        Compute(x.first, 0, 1);
        Add(x.first, c, x.first, 1);
    }
    for(auto x : v[c]){
        if(viz[x.first])
            continue;
        SuperErase(x.first, c, x.first, 1);
    }
     for(auto x : v[c]){
        if(viz[x.first])
            continue;
        CD(x.first);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for(int i = 0; i < N - 1; i++){
        int a = H[i][0] + 1;
        int b = H[i][1] + 1;
        v[a].push_back({b, L[i]});
        v[b].push_back({a, L[i]});
    }
    for(int i = 0; i <= k; i++)
       mp[i] = {(int)2e9, -1, (int)2e9, -1};
    CD(1);
    if(best == 2e9)
        best = -1;
    return best;
}

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

race.cpp: In function 'void ComputeDist(int, int, int, int, int)':
race.cpp:65:9: warning: variable 'act' set but not used [-Wunused-but-set-variable]
   65 |     pii act = {level, subTree};
      |         ^~~
race.cpp: In function 'void Erase(int, int, int, int)':
race.cpp:86:9: warning: variable 'act' set but not used [-Wunused-but-set-variable]
   86 |     pii act = {level, subTree};
      |         ^~~
race.cpp: In function 'void SuperErase(int, int, int, int)':
race.cpp:102:9: warning: variable 'act' set but not used [-Wunused-but-set-variable]
  102 |     pii act = {level, subTree};
      |         ^~~
race.cpp: In function 'void Add(int, int, int, int)':
race.cpp:116:9: warning: variable 'act' set but not used [-Wunused-but-set-variable]
  116 |     pii act = {level, subTree};
      |         ^~~

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