Submission #691217

#	Time	Username	Problem	Language	Result	Execution time	Memory
691217		boyliguanhan	Race (IOI11_race)	C++17	21 / 100	2216 ms	18680 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int dis[1000][1000][2];
int best_path(int N, int K, int H[][2], int L[]) {
    memset(dis, 1, sizeof dis);
    for(int i=0;i<N;i++)
        dis[i][i][0]=dis[i][i][1]=0;
    for(int i = 0; i < N-1; i++)
        dis[H[i][0]][H[i][1]][0] = 1, dis[H[i][1]][H[i][0]][0] = 1, dis[H[i][0]][H[i][1]][1] = L[i], dis[H[i][1]][H[i][0]][1] = L[i];
    for(int x = 0; x < 2; x++)
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                for(int k = 0; k < N; k++)
                    dis[j][k][x] = min(dis[j][k][x], dis[j][i][x]+dis[i][k][x]);
    int ans = 100000;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            if(dis[i][j][1]==K)
                ans = min(ans, dis[i][j][0]);
    return ans>N?-1:ans;
}

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