Submission #1145239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145239		asdfghjk	경주 (Race) (IOI11_race)	C++20	0 / 100	1 ms	2624 KiB

race

#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define con continue
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<ll,ll> pii;

const ll N = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll maxn = 6e5 + 5;
const ll inf = 1e9;
const ll INF = 1e18;
const ll K = 31;

/*vector <ll> z_function(string s){
//    ll n = s.size();
//    ll l = 0,r = 0;
//    vector <ll> z(n);
//    for(ll i = 1;i < n;i++){
//        if(i <= r){
//            z[i] = (r - i + 1,z[i - l]);
//        }
//        while(i + z[i] < n && s[z[i]] == s[z[i] + i]){
//            z[i]++;
//        }
//        if(i + z[i] - 1 > r){
//            r = i + z[i]-1;
//            l = i;
//        }
//    }
}*/

/*vector <ll> prefix_function(string s){
    ll n = s.size();
    vector <ll> pi(n,0);
    for(ll i = 1;i < n;i++){
        ll j = pi[i - 1];
        while(j > 0 && s[i] != s[j]){
            j = pi[j - 1];
        }
        if(s[i] == s[j])++j;
        pi[i] = j;
    }
    return pi;
}*/

vector <pii> g[N];
ll d,ans = inf,C,was[N];
ll get_sz(ll v,ll p,ll n){
    ll sz= 1 ;
    for(auto [to,w] : g[v]){
        if(was[to] || to == p)con;
        sz += get_sz(to,v,n);
    }
    if(!C && (sz+sz>=n || p == 0))C = v;
    return sz;
}
set <ll> has;
map<ll,ll> val;
ll dep[N],dis[N];
void dfs(ll v,ll p){
    if(dis[v] > d)return;
    if(has.count(d - dis[v]) == 1){
        ans = min(ans,(dep[v]+val[(d - dis[v])]));
    }
    for(auto [to,w] : g[v]){
        if(to == p || was[to])con;
        dis[to] = dis[v] + w;
        dep[to] = dep[v] + 1;
        dfs(to,v);
    }
}
void add(ll v,ll p){
    if(dis[v] > d)return;
    if(has.count(dis[v]) == 0){
        has.insert(dis[v]);
        val[dis[v]] = dep[v];
    }
    val[dis[v]] = min(val[dis[v]],dep[v]);
    for(auto [to,w] : g[v]){
        if(was[to] || to == p)con;
        add(to,v);
    }
}
void centr_decop(ll v,ll n){
    C = 0;
    get_sz(v,0,n);
    ll c = C;
    has.clear();
    val.clear();
    has.insert(0);
    val[0] = 0;
    dis[c] = 0;
        dep[c] = 0;
    for(auto [to,w] : g[c]){
        if(was[to])con;
        dep[to] = dep[c] + 1;
        dis[to] = dis[c] + w;
        dfs(to,c);
        add(to,c);
    }
    was[c] = 1;
    for(auto  [to,w] : g[c]){
        if(was[to])con;
        centr_decop(to,n / 2);
    }
}
int best_path(int nn,int k,int h[][2],int l[]){
    ll n = nn;
    d = k;
    for(ll i = 1;i < n;i++){
        ll u = h[i][0];
        ll v = h[i][1];
        u++;
        v++;
        ll w = l[i];
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    centr_decop(1,n);
    if(ans == inf)return -1;
    return ans;
}
//void solve(){
//    ll n =
//}
//main(){
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    ll abd = 1;
////    freopen("yinyang.in","r",stdin);
////    freopen("yinyang.out","w",stdout);
//
////    cin >> abd;
//    for(ll i = 1;i <= abd;i++){
//        solve();
//    }
//}

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