Submission #1199664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199664		mareksb	Race (IOI11_race)	C++20	9 / 100	23 ms	9288 KiB

race

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

const int MAXN=200005;
vector<int> mas[MAXN];
deque<int> dq;
void dfs(int v, int p, int dir){

    for(auto u:mas[v]){
        if(u==p)continue;
        if(dir)dq.push_front(v);
        else dq.push_back(v);
        dfs(u,v,dir);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    if(N==1){
        return -1;
    }
    for(int i=0;i<N-1;i++){
        int x=H[i][0];
        int y=H[i][1];
        mas[x].push_back(y);
        mas[y].push_back(x);
    }

    /*
    if(mas[1].size()==1){
        dfs(1,1,1);
    }
    else{
        dfs(0,0,0);
        dfs(1,1,1);
    }
    */
    int64_t len=0;
    int l=0;
    int r=0;
    int ans=INT_MAX;
    while(r<N-1){
        //cout<<"dbg:"<<len<<' '<<l<<' '<<r<<'\n';
        if(len<K){
            len+=L[r];
            r++;
        }

        if(len==K){
            ans=min(ans,r-l);
        }
                if(len>=K){
            len-=L[l];
            l++;
        }
    }

    if(ans==INT_MAX){
        return -1;
    }
    return ans;
}
/*
5 5
0 1 1
1 2 4
2 3 2
3 4 3
2

5 10
0 1 1
1 2 4
2 3 2
3 4 3
4
*/

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