Submission #1145253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145253		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;
}*/
int n,ans = -1;
ll sz[N],was[N];
vector <pair<ll,ll> > g[N];
void cal(ll v,ll p){
    sz[v] = 1;
    for(auto [to,w] : g[v]){
        if(was[to] || to == p)con;
        cal(to,v);
        sz[v] += sz[to];
    }
}
ll get_centr(ll v,ll p,ll len){
    for(auto [to,w] : g[v]){
        if(was[to] || to == p)con;
        if((sz[to] *2 > len)){
            return get_centr(to,v,len);
        }
    }
    return v;
}
ll k;
map<ll,int> val;
int dep[N];
ll dis[N];
void dfs(ll v,ll p){
    if(dis[v] == k){
        if(ans != -1)ans=  min(ans,dep[v]);
        else ans = dep[v];
    }
    else if(dis[v] < k){
        if(val[(k - dis[v])] != 0){
            if(ans != -1)ans = min(ans,dep[v] + val[(k - dis[v])]);
            else ans = dep[v] + val[(k - dis[v])];
        }
    }
    for(auto [to,w] : g[v]){
        if(was[to] || to == p)con;
        dep[to] = dep[v] + 1;
        dis[to] = dis[v] + w;
        dfs(to,v);
    }
}
void add(ll v,ll p){
    if(val[dis[v]] == 0){
        val[dis[v]] = dep[v];
    }
    else if(dis[v] < k){
        val[dis[v]] = min(val[dis[v]],dep[v]);
    }
    for(auto [to,w] : g[v]){
        if(was[to] || to == p)con;
        dep[to] = dep[v] + 1;
        dis[to] = dis[v] + w;
        add(to,v);
    }
}
void centr_decop(ll v){
    cal(v,0);
    ll c = get_centr(v,v,sz[v]);
    dep[c] = 0;
    dis[c] = 0;
    val.clear();
    for(auto [to,w] : g[v]){
        if(was[to])con;
        dep[to] = 1;
        dis[to] = w;
        dfs(to,c);
        add(to,c);
    }
    was[c] = 1;
    for(auto [to,w] : g[v]){
        if(was[to])con;
        centr_decop(to);
    }
}
int best_path(int nn,int k2,int h[][2],int l[]){
    n = nn;
    k = k2;

    for(int i = 1;i < n;i++){
        int u= h[i][0];
        int v = h[i][1];
        int w = l[i];
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    centr_decop(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