Submission #1255394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255394		avohado	Race (IOI11_race)	C++20	0 / 100	2 ms	4928 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)
vector<pair<int, int>> g[maxn];
int p[1000000+1], mx=1e6, o[maxn], k;
bool ch[maxn];
void ex(int u, int r, int sm, int sh){
    int sum=sm;if(sm>k)return;
    if(p[k-sm]<3e5){
        mx=min(mx, sh+p[k-sm]);
    }
    for(auto i:g[u]){
        if(i.f!=r&&!ch[i.f]){
            ex(i.f, u, sum+i.s, sh+1);
        }
    }
    p[sm]=min(p[sm], sh);
}
int req(int n, int u, int v){
    int sum=1;
    for(auto i:g[u]){
        if(i.f!=v&&!ch[i.f]){
            req(n, i.f, u);
            if(o[i.f]==-1){
                o[u]=-1;
                return -1;
            }
            sum+=o[i.f];
        }
    }
    
            if(sum>=n/2){
                ch[u]=1;
                vector<pair<int, int>> j;
                for(auto i:g[u]){
                    if(!ch[i.f]){
                        ex(i.f, u, i.s, 1);
                    j.push_back({i.f, o[i.f]});
                    }
                }
                for(auto i:j){
                    if(i.s>1){
                        for(int i=1; i<=k; i++){
                            p[i]=3e5;
                        }
                        req(i.s, i.f, i.f);
                    }
                }
                o[u]=-1;
                return -1;
            }
    o[u]=sum;
    return sum;
}
int best_path(int n, int k1, int h[][2], int l[]){
    for(int i=0; i<n-1; i++){
        g[h[i][0]].push_back({h[i][1], l[i]});
        g[h[i][1]].push_back({h[i][0], l[i]});
    }
    k=k1;
    req(n, 0, 0);
    return (mx==1e6?-1:mx);
}

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