Submission #1201801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201801		edga1	Race (IOI11_race)	C++20	0 / 100	3 ms	4928 KiB

race

#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> a[200005];
int s[200005];
int d[200005];
int rez=1e9,k,n;
vector<int> vert;

int dfs(int x, int p){
    d[x]=1;
    for(int i=0; i<a[x].size(); i++){
        if(!s[a[x][i].first] && a[x][i].first!=p){
            d[x]+=dfs(a[x][i].first,x);
        }
    }
    return d[x];
}

int findc(int x){
    int sk=dfs(x,x);
    int e=1,v=x,p=x;
    while(e){
        e=0;
        if(sk-d[x]>sk/2) e=1;
        int m=0,mpos;
        for(int i=0; i<a[v].size(); i++){
            if(!s[a[v][i].first] && a[v][i].first!=p){
                if(d[a[v][i].first]>m){
                    m=d[a[v][i].first];
                    mpos=a[v][i].first;
                }
            }
        }
        if(m>sk/2) e=1;
        if(e==1){
            p=v;
            v=mpos;
        }
    }

    cout<<'\n';
    return v;
}



void cd(int x){
    int c=findc(x);
    s[c]=1;
    cout<< c;
    for(auto [v,w] : a[c]){
        if(!s[v]) cd(v);
    }
}

int best_path(int N, int K, int h[][2], int l[]){
    k=K;
    n=N;
    for(int i=0; i<N-1; i++){
        a[h[i][0]].push_back({h[i][1],l[i]});
        a[h[i][1]].push_back({h[i][0],l[i]});
    }
    cd(1);
    if(rez==1e9) return -1;
    return rez;
}

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