Submission #943795

#	Time	Username	Problem	Language	Result	Execution time	Memory
943795		irmuun	Race (IOI11_race)	C++17	21 / 100	25 ms	16216 KiB

race

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int maxn=1e3+5;

vector<pair<int,int>>adj[maxn];
ll dist[maxn][maxn];
int len[maxn][maxn];

void dfs(int x,int p,int r){
    for(auto [y,w]:adj[x]){
        if(y!=p){
            len[r][y]=len[r][x]+1;
            dist[r][y]=dist[r][x]+w;
            dfs(y,x,r);
        }
    }
}

int best_path(int N,int K,int H[][2],int L[]){
    for(int i=0;i<N-1;i++){
        adj[H[i][0]].pb({H[i][1],L[i]});
        adj[H[i][1]].pb({H[i][0],L[i]});
    }
    int ans=-1;
    if(N<=1000){
        for(int i=0;i<N;i++){
            dist[i][i]=0;
            len[i][i]=0;
            dfs(i,-1,i);
        }
        int mx=1e9;
        for(ll i=0;i<N;i++){
            for(ll j=0;j<N;j++){
                if(dist[i][j]==(ll)K){
                    mx=min(mx,len[i][j]);
                }
            }
        }
        if(mx<1e9) ans=mx;
    }
    return ans;
}

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