제출 #491378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
491378		MohammadAghil	Race (IOI11_race)	C++14	100 / 100	483 ms	139072 KiB

race

#include <bits/stdc++.h> 
// #include "race.h"
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx,avx2")
using namespace std; 
typedef long long ll; 
typedef pair<ll, int> pp;
#define rep(i,l,r) for(int i = (l); i < r; i++)
#define per(i,r,l) for(int i = (r); i >= l; i--)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define ss second 

const ll mod = 998244353, maxn = 1e6 + 5, inf = 1e9 + 5;

bool ban[maxn];
int cnt[maxn], k;
vector<pp> adj[maxn], st[maxn];
int dist[maxn];

void set_cnt(int r, int p){
    cnt[r] = 1;
    for(pp c: adj[r]) if(c.ff != p && !ban[c.ff]){
        set_cnt(c.ff, r);
        cnt[r] += cnt[c.ff];
    }
}

int findCenteroid(int r, int p, int tot){
    for(pp c: adj[r]) if(c.ff != p && !ban[c.ff]){
        if(cnt[c.ff] >= tot - cnt[c.ff]) return findCenteroid(c.ff, r, tot);
    }
    return r;
}

void dfs(int r, int p, int rt, ll len, int w){
    st[rt].pb({len, w});
    for(pp c: adj[r]) if(c.ff != p && !ban[c.ff]) dfs(c.ff, r, rt, len + c.ss, w + 1);
}

int slv(int r){
    set_cnt(r, r);
    r = findCenteroid(r, r, cnt[r]);
    int ans = inf;
    for(pp c: adj[r]) if(!ban[c.ff]){
        dfs(c.ff, r, c.ff, c.ss, 1);
        for(pp t: st[c.ff]){
            int v = k - t.ff;
            if(v < 0 || (v > 0 && dist[v] == 0)) continue;
            ans = min(ans, dist[v] + t.ss);
        }
        for(pp t: st[c.ff]){
            if(t.ff > k) continue;
            if(dist[t.ff] == 0) dist[t.ff] = t.ss;
            dist[t.ff] = min(dist[t.ff], t.ss);
        }
    }
    for(pp c: adj[r]) if(!ban[c.ff]){
        for(pp t: st[c.ff]){
            if(t.ff > k) continue;
            dist[t.ff] = 0;
        }
        st[c.ff].clear();
    }
    ban[r] = true;
    for(pp c: adj[r]) if(!ban[c.ff]){
        ans = min(ans, slv(c.ff));
    }
    return ans;
}

int best_path(int N, int K, int H[][2], int L[]){
    k = K;
    rep(i,0,N-1){
        adj[H[i][0]].pb({H[i][1], L[i]});
        adj[H[i][1]].pb({H[i][0], L[i]});
    }
    int ans = slv(0);
    return ans == inf? -1: ans;
}

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