Submission #1118766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118766		dead0ne	Race (IOI11_race)	C++17	0 / 100	29 ms	37736 KiB

race

#include "race.h"
#include <bits/stdc++.h>

#define pb push_back
#define spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
#define ll long long
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define mid (l+r)/2
#define inf 1e9
#define MOD 998244353
#define MX 500005
using namespace std;

vii edges[MX];
int tin[MX], tout[MX], dep[MX], depfr[MX], par[MX][20], mark[MX], sub[MX];
vi chil[MX];
int tim=0, og=-1;
int k;

void upd(int node, int pa){
    sub[node]=1;
    for(auto p:edges[node]){
        if(p.st==pa || mark[p.st]) continue;
        upd(p.st, node);
        sub[node]+=sub[p.st];
    }
}

int cent(int node){
    upd(node, node);
    int cur=node, las=node;
    int flag;
    while(true){
        flag=1;
        for(auto i:edges[cur]){
            if(mark[i.st] || i.st==las) continue;
            if(sub[i.st]>sub[node]/2){
                las = cur;
                cur = i.st;
                flag=0;
                break;
            }
        }
        if(flag) break;
    }
    mark[cur]=1;
    if(og==-1) og=cur;
    for(auto p:edges[cur]){
        if(mark[p.st]) continue;
        chil[cur].pb(cent(p.st));
    }
    return cur;
}

void dfs(int node, int pa){
    tin[node] = ++tim;
    par[node][0]=pa;
    for(int i=1; i<20; i++) par[node][i] = par[par[node][i-1]][i-1];
    for(auto p:edges[node]){
        if(p.st==pa) continue;
        dep[p.st] = dep[node] + p.nd;
        depfr[p.st] = depfr[node] + 1;
        dfs(p.st, node);
    }
    tout[node] = tim;
}
bool anc(int u, int v){
    return tin[u]<=tin[v] && tout[u]>=tout[v];
}
int lca(int u, int v){
    if(u==v) return u;
    if(dep[v]>dep[u]) swap(u,v);
    for(int i=19; i>=0; i--) if(!anc(par[u][i], v)) u = par[u][i];
    return par[u][0];
}
ii dis(int u, int v){
    int tem = lca(u,v);
    return {dep[u]+dep[v]-2*dep[tem], depfr[u]+depfr[v]-2*depfr[tem]};
}

vi wow[MX];
int dfs2(int node){
    wow[node].pb(node);
    if(!chil[node].size()) return inf;
    int ind=0, maxi=0, res=inf;
    for(auto i:chil[node]){
        res = min(res, dfs2(i));
        if(wow[i].size()>maxi) ind=i;
    }
    wow[node].swap(wow[ind]);
    for(auto i:chil[node]){
        if(i==ind) continue;
        for(auto j:wow[i]) wow[node].pb(j);
    }
    map<int, int> heh;
    for(auto i:wow[node]){
        ii d=dis(node, i);
        if(heh[k-d.st]!=0){
            res = min(res, heh[k-d.st]+d.nd);
        }
        if(heh[d.st]==0 || d.nd<heh[d.st]) heh[d.st]=d.nd;
    }
    wow[node].pb(node);
    return res;
}

int best_path(int N, int K, int H[][2], int L[]){
    k=K;
    for(int i=0; i<N-1; i++){
        edges[H[i][1]].pb({H[i][0],L[i]});
        edges[H[i][0]].pb({H[i][1],L[i]});
    }
    memset(mark, 0, sizeof(mark));
    dep[0]=depfr[0]=0;
    dfs(0,0);
    cent(0);
    int lol = dfs2(og);
    if(lol==inf) return -1;
    return lol;
}

Compilation message (stderr)

race.cpp: In function 'int dfs2(int)':
race.cpp:94:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |         if(wow[i].size()>maxi) ind=i;
      |            ~~~~~~~~~~~~~^~~~~

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