Submission #1271159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271159		zagaro	Race (IOI11_race)	C++20	100 / 100	1557 ms	78364 KiB

race

#include<bits/stdc++.h>
#include "race.h"
#include<ext/pb_ds/assoc_container.hpp>
/**zagaro & lauren <3**/
#define mod 1000000007 //1e9 + 7
#define pi acos(-1)
#define wl while
#define str string
#define ENDL "\n"
#define sal ' '
#define tp_set ll
#define prc(n) cout.precision(n);cout<<fixed;
#define ord_set tree<tp_set, null_type, less<tp_set>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef bool bl;
typedef char car;
using namespace std;
using namespace __gnu_pbds;
ll n, r=LONG_LONG_MAX, k;
vector<vector<pair<ll,ll> > > adj;
vector<ll> sub;
vector<bl> vis;
ll centroid(ll nod, ll par, ll tam){
    for(int i=0;i<adj[nod].size();i++){
        if(adj[nod][i].first != par && vis[adj[nod][i].first]){
            if(sub[adj[nod][i].first]*2 > tam){
                return centroid(adj[nod][i].first, nod, tam);
            }
        }
    }
    return nod;
}
ll calc(ll nod, ll par){
    sub[nod] = 1;
    for(int i=0;i<adj[nod].size();i++){
        if(adj[nod][i].first != par && vis[adj[nod][i].first]){
            sub[nod] += calc(adj[nod][i].first, nod);
        }
    }
    return sub[nod];
}
void dfs(ll nod, ll par, ll m, ll cdist, map<ll,ll> &mp){
    if(cdist > k)return ;
    if(mp[cdist] == 0)mp[cdist] = m;
    else mp[cdist] = min(mp[cdist], m);
    for(int i=0;i<adj[nod].size();i++){
        if(adj[nod][i].first != par && vis[adj[nod][i].first]){
            dfs(adj[nod][i].first, nod, m+1, cdist+adj[nod][i].second, mp);
        }
    }
    return ;
}
void build(ll nod){
    ll x = centroid(nod, -1, calc(nod, -1));
    vis[x]=false;
    map<ll,pair<ll,ll> > tot;
    vector<map<ll,ll> > mp(adj[x].size());
    for(int i=0;i<adj[x].size();i++){
        if(vis[adj[x][i].first]){
            dfs(adj[x][i].first, x, 1, adj[x][i].second, mp[i]);
            pair<ll,ll> p;
            for(auto w: mp[i]){
                p = tot[w.first];
                if(p.first == 0)tot[w.first].first = w.second;
                else if(p.second == 0)tot[w.first].second = w.second;
                else if(w.second <= p.first){
                    tot[w.first].first = w.second;
                    tot[w.first].second = p.first;
                }
                else if(w.second < p.second)tot[w.first].second = w.second;
            }
            build(adj[x][i].first);
        }
    }
    if(tot[k].first != 0)r = min(r, tot[k].first);
    for(int i=0;i<adj[x].size();i++){
        for(auto w: mp[i]){
            if(tot[k-w.first].first == 0)continue;
            if(tot[k-w.first].first == (*mp[i].find(k-w.first)).second){
                if(tot[k-w.first].second != 0)r = min(r, tot[k-w.first].second + w.second);
            }
            else r = min(r, tot[k-w.first].first + w.second);
        }
    }
    return ;
}
int best_path(int N, int K, int H[][2], int L[]){
    ll a, b, v;
    n = N;k = K;
    adj.assign(n+1, vector<pair<ll,ll> > (0, {0, 0}));
    sub.assign(n+1, 1);
    vis.assign(n+1, true);
    for(int i=0;i<n-1;i++){
        a = H[i][0]+1;
        b = H[i][1]+1;
        v = L[i];
        adj[a].push_back({b, v});
        adj[b].push_back({a, v});
    }
    build(1);
    if(r == LONG_LONG_MAX)return -1;
    return r;
}

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