Submission #1199614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199614		mareksb	Race (IOI11_race)	C++20	0 / 100	3 ms	4936 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[])
{
    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);
    }
    */
    int i=0;
    int len=L[0];
    int ans=INT_MAX;
    for(int j=1;j<N-1;j++){
        while(len>K){
            len-=L[i];
            i++;
        }
        if(len==K){
            ans=min(ans,j-i);
        }
        len+=L[j];
    }
    if(ans==INT_MAX){
        return -1;
    }
    return ans;
}
/*
5 5
0 1 1
1 2 4
2 3 2
3 4 3
2
*/

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