Submission #381034

#	Time	Username	Problem	Language	Result	Execution time	Memory
381034		ponytail	Race (IOI11_race)	C++17	31 / 100	1191 ms	89840 KiB

race

#include "bits/stdc++.h"
using namespace std;
#define double long double
#define mp make_pair
#define fi first
#define se second
#define pb push_back
mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 2e5 + 10;
int sz[MAXN], maxsz[MAXN], n, k;
vector<pair<int,int> >adj[MAXN];
unordered_map<int,int> f[MAXN];
const int MAXK = 10000010;
int exist[MAXK], exist2[MAXK];
int ans = 1e9;
int whole_size;
int number_of_operations = 0;
int dfs0(int node,int prev){
    sz[node]=1;
    number_of_operations++;
    for(pair<int,int>x:adj[node]){
        if(x.se==-1)continue;
        if(x.fi==prev)continue;
        int d=dfs0(x.fi,node);
        sz[node]+=d;
    }
    return sz[node];
}
int dfs(int node,int prev){
    sz[node]=1;
    maxsz[node]=0;
    number_of_operations++;
    for(pair<int,int> x:adj[node]){
        if(x.se==-1) continue;
        if(x.fi==prev) continue;
        int d=dfs(x.fi,node);
        sz[node]+=d;
        maxsz[node]=max(maxsz[node],d);
    }
    maxsz[node]=max(maxsz[node],whole_size-sz[node]);
    return sz[node];
}
queue<int>ntv;
vector<int>all;
void wheewhoowhee(int node,int prev){
    all.pb(node);
    for(pair<int,int>x:adj[node]){
        if(x.se==-1)continue;
        if(x.fi==prev)continue;
        wheewhoowhee(x.fi,node);
    }
}
int divide(){
    all.clear();
    wheewhoowhee(ntv.front(),-1);
    for(int i:all){
        sz[i]=0;
        maxsz[i]=1e9;
        number_of_operations++;
    }
    whole_size=dfs0(ntv.front(),-1);
    dfs(ntv.front(),-1);
    ntv.pop();
    int centroid=0, e=1e9;
    for(int i:all){
        if(e>maxsz[i]){
            e=maxsz[i];
            centroid=i;
        }
    }
    for(pair<int,int> x:adj[centroid]){
        if(x.se==-1) continue;
        ntv.push(x.fi);
    }
    return centroid;
}
queue<int>used, used2, used3;
void dfs2(int node,int prev,int cur,int dep){
//  cout <<cur <<"\n";
    if(cur>=1 && cur<MAXK && exist2[cur]==1e9){
//        cout << "FUCK\n";
        used.push(cur);
        used3.push(cur);
    }
    if(cur>=1 && cur<MAXK){
        exist2[cur]=min(exist2[cur],dep);
    }
    for(pair<int,int>x:adj[node]){
        if(x.se==-1) continue;
        if(x.fi==prev) continue;
        dfs2(x.fi,node,cur+x.se,dep+1);
    }
}
void conquer(int root){
    while(used2.size()){
        exist[used2.front()]=1e9;
        used2.pop();
    }
    for(int i=0;i<adj[root].size();i++){
        if(adj[root][i].se==-1) continue;
        int sto=adj[root][i].se;
        adj[root][i].se=-1;
        adj[adj[root][i].fi][f[adj[root][i].fi][root]].se=-1;
        dfs2(adj[root][i].fi,-1,sto,1);
        while(used3.size()){
//            cout << "E "<<i<<" "<<used3.front()<<"\n";
            if(k==used3.front()){
                ans=min(ans,exist2[used3.front()]);
            }
            if(k-used3.front()>=1 && k-used3.front()<MAXK && exist[k-used3.front()]!=1e9){
//                cout << "F "<<exist[k-used3.front()] << " " << exist2[used3.front()] << "\n";
                ans=min(ans,exist[k-used3.front()]+exist2[used3.front()]);
//                cout << "G "<<ans << "\n";
            }
            used3.pop();
        }
        while(used.size()){
            if(exist[used.front()]==1e9) used2.push(used.front());
            exist[used.front()]=min(exist[used.front()],exist2[used.front()]);
//            cout << "exist "<<used.front()<<" "<<exist[used.front()]<<"\n";
            exist2[used.front()]=1e9;
            used.pop();
        }
    }
}
signed best_path(signed N,signed K,signed h[][2],signed l[]){
    n=N, k=K;
    for(int i=1;i<=n;i++) exist[i]=1e9, exist2[i]=1e9;
    for(int i=1;i<n;i++){
        int u=h[i-1][0],v=h[i-1][1],w=l[i-1];
        //cin >> u >> v >> w;
        u++, v++;
        int U=adj[u].size();
        int V=adj[v].size();
        f[u][v]=U;
        f[v][u]=V;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    ntv.push(1);
    while(ntv.size()){
        conquer(divide());
    }
    return (ans==1e9 ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'void conquer(int)':
race.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i=0;i<adj[root].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~

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