제출 #479637

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

race

#include "race.h"
#include <bits/stdc++.h>
 
#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()
 
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;
 
const int INF = 1e9 + 1;
const int MX = 2e5 + 100;
const double eps = 1e-7;
 
template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
 
 
V<ll> dis(MX);
 
V<int> ms(MX);
VV<pair<int, ll>> g(MX);
 
V<int> dep(MX);
int n;
ll k;
 
V<int> tin(MX), tout(MX);
int T = 1; 
int ret = INF;
multiset<int> Bs[MX];
V<int> val(MX);
V<int> mp(MX);
map<ll, int> UD;
int get_id(ll x) {
    
    if(UD[x])
        return UD[x];
    else return -1;
}
 
void dfs1(int v, int p) {
    tin[v] = T++;
 
    mp[T - 1] = v;
    dep[v] = (p == 0 ? 0 :  dep[p] + 1);
 
    for(auto [c, w] : g[v]) {
        if(c != p) {
            dis[c] =dis[v] + w;
            dfs1(c, v);
        }
    }
 
    tout[v] = T;
    ms[v] = tout[v] - tin[v];
}
 
void dfs2(int v, int p, bool keep) {
    int mx = -1, bg = -1;
 
    for(auto [c, w] : g[v]) 
        if(c != p && ms[c] > mx)
            mx = ms[c], bg = c;
 
    for(auto [c, w] : g[v]) 
        if(c != p && c != bg)
            dfs2(c, v, 0);
 
    if(bg != -1)
        dfs2(bg, v, 1);
    
    
 
    
 
    for(auto [c, w] : g[v]) {
        if(c != p && c != bg) {
            //debug(v, c);
            for(int x = tin[c];x < tout[c];++x) {
               
                if(dis[v] + k == dis[mp[x]]) {
                    ckmi(ret, dep[mp[x]] - dep[v]);
                }
                else if(dis[mp[x]] - dis[v] < k) {
                    
                    ll rr = dis[mp[x]] - dis[v];
                    rr = k - rr;
                    rr += dis[v];
                    //assert(dis[v] + k > rr);
                    int id = get_id(rr);
                    if(id != -1 && sz(Bs[id]))
                        ckmi(ret, *Bs[id].begin() + dep[mp[x]] - 2 * dep[v]);
                }
            }
            for(int x= tin[c];x < tout[c];++x)
                Bs[val[mp[x]]].insert(dep[mp[x]]);
            
        }
    }
 
    
    int prx = dis[v] + k;
    prx = get_id(prx);
    if(prx != -1 && sz(Bs[prx]))
        ckmi(ret, *Bs[prx].begin() - dep[v]);
 
    Bs[val[v]].insert(dep[v]);
    
        
 
    if(keep == 0)
        for(int x = tin[v];x < tout[v];++x)
            Bs[val[mp[x]]].erase(Bs[val[mp[x]]].find(dep[mp[x]]));
            
}
 
int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    k = K;
    forn(i, N - 1) {
        ++H[i][0], ++H[i][1];
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }
    dfs1(1, 0);
    int cor = 1;
   
    for(int i = 1;i <= n;++i)
        val[i] = (UD[dis[i]] ? UD[dis[i]] : UD[dis[i]] = cor++);
 
    
    dfs2(1, 0, 1);
 
    if(ret == INF)
        ret = -1;
 
    return ret;
 
}
 

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