Submission #1264027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264027		avohado	Race (IOI11_race)	C++20	100 / 100	320 ms	31988 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define maxn 200005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
int n, k, inf=maxn*2, sh=maxn*2, v=-1, timer=1, l[maxn];
bool used[maxn];
pair<int, int> k1[1000005];
vector<pair<int, int>> g[maxn];
int dfs1(int u, int p, int n){
    int sh=1;
    for(auto i:g[u]){
        if(i.f!=p&&!used[i.f]){
            sh+=dfs1(i.f, u, n);
        }
    }
    if(sh>n/2&&v==-1){
        v=u;
    }
    return sh;
}
void dfs2(int u, int p, int ck, int cnt){
    if(k1[k-ck].s==timer){
        sh=min(sh, (k1[k-ck].f+cnt));
    }
    for(auto i:g[u]){
        if(i.f!=p&&l[i.s]+ck<=k&&!used[i.f]){
            dfs2(i.f, u, l[i.s]+ck, cnt+1);
        }
    }
}
int dfs3(int u, int p){
    int sh=1;
    for(auto i:g[u]){
        if(!used[i.f]&&p!=i.f){
            sh+=dfs3(i.f, u);
        }
    }
    return sh;
}
void dfs4(int u, int p, int ck, int cnt){
    for(auto i:g[u]){
        if(i.f!=p&&l[i.s]+ck<=k&&!used[i.f]){
            dfs4(i.f, u, l[i.s]+ck, cnt+1);
        }
    }
    if(k1[ck].s<timer){
        k1[ck]={cnt, timer};
    }else{
        k1[ck].f=min(k1[ck].f, cnt);
    }
}
void rem(int u, int n){
    v=-1;
    if(n==1)return;
    dfs1(u, u, n);
    if(v==-1){
        cout << 1/0;
    }
    k1[0]={0, timer};
    for(auto i:g[v]){
        if(!used[i.f]&&l[i.s]<=k){
            dfs2(i.f, v, l[i.s], 1);
            dfs4(i.f, v, l[i.s], 1);
        }
    }
    used[v]=1;
    timer++;
    for(auto i:g[v]){
        if(!used[i.f]){
            rem(i.f, dfs3(i.f, v));
        }
    }
}
int best_path(int n1, int k1, int h[][2], int l1[]){
    n=n1, k=k1;
    for(int i=0; i<n-1; i++){
        g[h[i][0]].push_back({h[i][1], i});
        g[h[i][1]].push_back({h[i][0], i});
        l[i]=l1[i];
    }
    rem(0, n);
    return (sh==inf?-1:sh);
}

Compilation message (stderr)

race.cpp: In function 'void rem(int, int)':
race.cpp:61:18: warning: division by zero [-Wdiv-by-zero]
   61 |         cout << 1/0;
      |                 ~^~

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