Submission #1273714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273714		quanduongxuan12	Race (IOI11_race)	C++20	100 / 100	563 ms	36008 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define name "race"
#define MAXN 200005
#define pb push_back
#define pf push_front
#define ll long long
#define ii pair<int, int>
#define fs first
#define sc second
#define ill pair<int, ll>
#define lli pair<ll, int>
#define llll pair<ll, ll>
#define all(v) v.begin(),v.end()
#define uni(v) v.erase(unique(all(v)),v.end())
#define bit(n,i) (((n)>>(i))&1)
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for (int i=(a),_b=(b); i>=_b; i--)
#define MASK(i) (1LL<<(i))
const int INF=1e9;
const int MOD=1e9+7;
void add(int &u, int v){
    u+=v;
    if (u>=MOD) u-=MOD;
}
void sub(int &u, int v){
    u-=v;
    if (u<0) u+=MOD;
}
void minimize(int &u, int v){
    u=min(u,v);
}
void maximize(int &u, int v){
    u=max(u,v);
}
long long Rand(long long l, long long r){
    ll tmp=0;
    FOR(i,1,4) tmp=((tmp<<15)^(((1<<15)-1)&rand()));
    return l+tmp%(r-l+1);
}
int n,k;
vector<ii> adj[MAXN];
namespace sub2{
    int dfs(int u, int p, int d, int w){
        if (w>k) return INF;
        if (w==k) return d;
        int kq=INF;
        for (ii pairs:adj[u]){
            int v=pairs.fs;
            int wei=pairs.sc;
            if (v==p) continue;
            minimize(kq,dfs(v,u,d+1,w+wei));
        }
        return kq;
    }
    int solve(){
        int res=INF;
        FOR(i,1,n){
            minimize(res,dfs(i,0,0,0));
        }
        return (res==INF?-1:res);
    }
}
namespace sub3{
    int sz[MAXN];
    bool del[MAXN];
    int get_sz(int u, int p){
        sz[u]=1;
        for (ii pairs:adj[u]){
            int v=pairs.fs;
            if (del[v]||v==p) continue;
            sz[u]+=get_sz(v,u);
        }
        return sz[u];
    }
    int centroid(int u, int p, int n){
        for (ii pairs:adj[u]){
            int v=pairs.fs;
            if (v==p||del[v]) continue;
            if (2*sz[v]>n) return centroid(v,u,n);
        }
        return u;
    }
    int kq;
    set<ii> se;
    void update(int type, int u, int p, int d, int w){
        if (w>k) return;
        if (type==0){
            //minmize(ans,d+mp[k-w]);
            auto it=se.lower_bound((ii){k-w,0});
            if (it!=se.end()){
                ii tmp=(*it);
                if (tmp.fs==k-w){
                    minimize(kq,tmp.sc+d);
                }
            }
        }
        else{
            se.insert({w,d});
        }
        for (ii pairs:adj[u]){
            int v=pairs.fs;
            int wei=pairs.sc;
            if (v==p||del[v]) continue;
            update(type,v,u,d+1,w+wei);
        }
    }
    void calc(int u){
        int c=centroid(u,-1,get_sz(u,-1));
        del[c]=1;
        se.insert((ii){0,0});
        for (ii pairs:adj[c]){
            int v=pairs.fs;
            int wei=pairs.sc;
            if (del[v]) continue;
            update(0,v,c,1,wei);
            update(1,v,c,1,wei);
        }
        se.clear();
        for (ii pairs:adj[c]){
            int v=pairs.fs;
            if (del[v]) continue;
            calc(v);
        }
    }
    int solve(){
        kq=INF;
        calc(1);
        return (kq==INF?-1:kq);
    }
}
int best_path(int N, int K, int H[][2], int L[]){
    FOR(i,0,N-2){
        int u=H[i][0];
        int v=H[i][1];
        ++u;
        ++v;
        int w=L[i];
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    n=N;
    k=K;
    if (N<=1000) return sub2::solve();
    else
        return sub3::solve();
}

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