제출 #716026

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

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define F first
#define S second
#define loop(i,a,n) for(int i = a; i <= n; i++)
#define loopr(i,n,a) for(int i = n; i >= a; i--)
#define foor(i,n) for(int i = 0; i < n; i++)
#define fore(el,v) for(auto& el:v)
#define cin(v) for(auto& el:v) cin>>el
#define cout(v) for(auto el:v) cout<<el<<" "; cout<<'\n'
#define undirected(m) for(int iii=0;iii<m;iii++){int aaa,bbb;cin >> aaa >> bbb;adj[aaa].push_back(bbb);adj[bbb].push_back(aaa);}
#define directed(m) for(int iii=0;iii<m;iii++){int aaa,bbb;cin >> aaa >> bbb;adj[aaa].push_back(bbb);}
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define sz(v) (int)v.size()
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define Ones(n) __builtin_popcount(n)
#define Onesll(n) __builtin_popcountll(n)
#define PI acos(-1)
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define tan(a) tan((a)*PI/180)
#define fast ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
#define endl '\n'

using namespace __gnu_pbds;
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pi = pair<int,int>;
using pll = pair<ll,ll>;
using tiii = tuple<int,int,int>;
using tlll = tuple<ll,ll,ll>;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using vpi = vector<pair<int,int>>;
using vvi = vector<vector<int>>;
using mii = map<int,int>;
template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MOD = 1e9+7;
const int OO = 1e9+5;
const int N = 2e5+5, K = 1e6+5, LG = 20;
const double EPS = 1e-9;

int sz[N], n, k, mn[K];
vpi adj[N];
bool rem[N];

void preSize(int i, int par)
{
    sz[i] = 1;
    for(auto e:adj[i])
    {
        if(e.F == par || rem[e.F])continue;
        preSize(e.F, i);
        sz[i] += sz[e.F];
    }
}

int getCen(int i, int par, int subSz)
{
    int ret = -1;
    for(auto e:adj[i])
    {
        if(e.F == par || rem[e.F])continue;
        ret = max(ret, getCen(e.F, i, subSz));
    }
    int mx = subSz-sz[i];
    for(auto e:adj[i])
    {
        if(e.F == par || rem[e.F])continue;
        mx = max(mx, sz[e.F]);
    }
    if(mx <= subSz/2)
        ret = i;
    return ret;
}

int solve(int v, int par, int d, int w){
    if(w > k)
        return OO;
    int ans = min(OO, d + mn[k - w]);
    for(auto u : adj[v]) {
        if (rem[u.F] || u.F == par)
            continue;
        ans = min(ans, solve(u.F,v,d + 1, w + u.S));
    }
    return ans;
}

void update(int v, int par, int d, int w, bool clr){
    if(w > k)
        return;
    mn[w] = clr ? OO : min(mn[w], d);
    for(auto u : adj[v]) {
        if (rem[u.F] || u.F == par)
            continue;
        update(u.F, v, d + 1, w + u.S, clr);
    }
}

int getAns(int v){
    int ans = OO;
    for(auto u : adj[v]){
        if(rem[u.F])
            continue;
        ans = min(ans, solve(u.F,v,1,u.S));
        update(u.F,v,1,u.S,false);
    }
    return ans;
}

int decompose(int v){
    preSize(v,0);
    int cen = getCen(v,0,sz[v]);
    mn[0] = 0;
    int ans = getAns(cen);
    update(cen,0,0,0,true);
    rem[cen] = true;
    for(auto u : adj[cen]){
        if(rem[u.F])
            continue;
        ans = min(ans, decompose(u.F));
    }
    return ans;
}

int best_path(int nn, int kk, int H[][2], int L[]){
    n = nn, k = kk;
    foor(i,n-1){
        adj[H[i][0]+1].pb({H[i][1]+1, L[i]});
        adj[H[i][1]+1].pb({H[i][0]+1, L[i]});
    }
    foor(i,K) mn[i] = OO;
    int ans = decompose(1);
    return ans == OO ? -1 : ans;
}

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