Submission #1112728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112728		hainam2k9	Race (IOI11_race)	C++17	21 / 100	3061 ms	22344 KiB

race

#include <bits/stdc++.h>
#include <race.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
using namespace std;
const int MOD = 1e9+7, MAXN = 2e5+5;
const string NAME = "";
int n,k,rs=MAXN,sz[MAXN],cnt[1000005];
bool del[MAXN];
vector<pair<int,int>> adj[MAXN];
set<int> s;
void GetSize(int u, int par){
    sz[u]=1;
    for(pair<int,int> p : adj[u])
        if(p.fi!=par&&!del[p.fi]) GetSize(p.fi,u), sz[u]+=sz[p.fi];
}
int Centroid(int u, int par){
    for(pair<int,int> p : adj[u])
        if(p.fi!=par&&!del[p.fi]&&sz[p.fi]>(n>>1)) return Centroid(p.fi,u);
    return u;
}
void dfs(int u, int par, bool type, int cur, ll len){
    if(k<len||cur>rs) return;
    if(type==1) cnt[len] = !cnt[len] ? cur : min(cnt[len],cur), s.ins(len);
    else if(type==0&&cnt[k-len]) rs=min(rs,cnt[k-len]+cur);
    else if(len==k) rs=min(rs,cur);
    for(pair<int,int> p : adj[u])
        if(p.fi!=par) dfs(p.fi,u,type,cur+1,len+p.se);
}
void CentroidDecomposition(int u){
    GetSize(u,0), n=sz[u];
    int root=Centroid(u,0);
    for(pair<int,int> p : adj[root])
        if(!del[p.fi]) dfs(p.fi,root,0,1,p.se), dfs(p.fi,root,1,1,p.se);
    for(int x : s) cnt[x]=0;
    s.clear();
    del[root]=1;
    for(pair<int,int> p : adj[root])
        if(!del[p.fi]) CentroidDecomposition(p.fi);
}
int best_path(int N, int K, int h[][2], int l[]){
    n=N, k=K;
    for(int i = 1; i<n; ++i)
        adj[h[i-1][0]+1].pb(h[i-1][1]+1,l[i-1]), adj[h[i-1][1]+1].pb(h[i-1][0]+1,l[i-1]);
    CentroidDecomposition(1);
    return rs==MAXN ? -1 : rs;
}
//int main()
//{
//    tt;
//    if(fopen((NAME + ".INP").c_str(), "r")) fo;
//    cin >> n >> k;
//    int h[n][2], l[n];
//    for(int i = 0; i<n-1; ++i)
//        cin >> h[i][0] >> h[i][1] >> l[i];
//    cout << best_path(n,k,h,l);
//    cerr << 1.0L*clock()/CLOCKS_PER_SEC << "s\n";
//}

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