Submission #386095

#	Time	Username	Problem	Language	Result	Execution time	Memory
386095		cpp219	Race (IOI11_race)	C++14	43 / 100	3071 ms	38136 KiB

race

#pragma GCC optimization "Ofast"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e5 + 6;
const ll Log2 = 19;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
vector<LL> g[N];
ll n,k,w[N],H[N][2],child[N],len[N],d[N],ans = inf,L[N],centroid;
bool Is_cent[N];
multiset<LL> All;

ll Find_cent(ll u,ll p,ll total){
    for (auto i : g[u]){
        ll v = i.fs,now = i.sc;
        if (!Is_cent[v]&&v != p&&child[v]*2 >= total) return Find_cent(v,u,total);
    }
    Is_cent[u] = 1; return u;
}

void reDFS(ll u,ll p){
    child[u] = 1;
    for (auto i : g[u]){
        ll v = i.fs,now = i.sc;
        if (!Is_cent[v] && v != p){
            len[v] = len[u] + now;  d[v] = d[u] + 1;
            reDFS(v,u); child[u] += child[v];
        }
    }
}

void Add(ll u,ll p){
    All.insert({len[u],d[u]});
    for (auto i : g[u]){
        ll v = i.fs;
        if (!Is_cent[v] && v != p) Add(v,u);
    }
}

void Delete(ll u,ll p){
    auto it = All.find({len[u],d[u]});
    All.erase(it);
    for (auto i : g[u]){
        ll v = i.fs;
        if (!Is_cent[v] && v != p) Delete(v,u);
    }
}

void out(){
    for (auto i : All) cout<<i.fs<<" "<<i.sc<<"\n"; exit(0);
}

void update(ll u,ll p){
    if (len[u] == k) ans = min(ans,d[u]);
    if (len[u] < k){
        auto now = All.lower_bound({k - len[u],0});
        LL it = *now; //cout<<it.fs<<" "<<k <<" "<< len[u]; exit(0);
        if (now != All.end()&&it.fs == k - len[u]){
            ans = min(ans,it.sc + d[u]);
        }
        //if (u == 8&&centroid == 10) cout<<it.fs<<"x\n",out();
    }
    for (auto i : g[u]){
        ll v = i.fs;
        if (!Is_cent[v] && v != p) update(v,u);
    }
}

void DFS(ll u){
    reDFS(u,0); All.clear();
    centroid = Find_cent(u,0,child[u]); len[centroid] = 0; d[centroid] = 0;
    reDFS(centroid,0);
    for (auto i : g[centroid]){
        ll v = i.fs;
        if (!Is_cent[v]) Add(v,centroid);
    }
    for (auto i : g[centroid]){
        ll v = i.fs;
        if (!Is_cent[v]){
            Delete(v,centroid);
            update(v,centroid); Add(v,centroid);
        }
    }
    //cout<<centroid<<" x "<<ans; exit(0);
    for (auto i : g[centroid]){
        ll v = i.fs;
        if (!Is_cent[v]) DFS(v);
    }
}

int best_path(int num,int K,int H[][2],int L[]){
    n = num; k = K;
    for (ll i = 0;i < n - 1;i++){
        ll x = H[i][0],y = H[i][1]; x++; y++;
        g[x].push_back({y,L[i]}); g[y].push_back({x,L[i]});
    }
    DFS(1);
    if (ans != inf) return ans;
    return -1;
}
/*
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n>>k;
    for (ll i = 0;i < n - 1;i++) cin>>H[i][0]>>H[i][1]>>L[i];
    cout<<best_path(n,k,H,L);
}
*/

Compilation message (stderr)

race.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    1 | #pragma GCC optimization "Ofast"
      | 
race.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
race.cpp: In function 'int Find_cent(int, int, int)':
race.cpp:22:21: warning: unused variable 'now' [-Wunused-variable]
   22 |         ll v = i.fs,now = i.sc;
      |                     ^~~
race.cpp: In function 'void out()':
race.cpp:57:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   57 |     for (auto i : All) cout<<i.fs<<" "<<i.sc<<"\n"; exit(0);
      |     ^~~
race.cpp:57:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   57 |     for (auto i : All) cout<<i.fs<<" "<<i.sc<<"\n"; exit(0);
      |                                                     ^~~~

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