Submission #410767

#	Time	Username	Problem	Language	Result	Execution time	Memory
410767		LouayFarah	Race (IOI11_race)	C++14	21 / 100	3095 ms	202292 KiB

race

#include <bits/stdc++.h>
#include "race.h"
 
using namespace std;
 
void depth(vector<pair<int, int>> adj[], int u, int e, vector<int> &cnt)
{
    for(auto v: adj[u])
    {
        if(v.first!=e)
        {
            cnt[v.first] = cnt[u]+v.second;
            depth(adj, v.first, u, cnt);
        }
    }
}
 
void all_pairs_distance(vector<pair<int, int>> adj[], int N, vector<vector<int>> &cnt)
{
    for(int i = 0; i<N; i++)
    {
        vector<int> temp(N);
        depth(adj, i, -1, temp);
        cnt.push_back(temp);
    }
}
 
void depth2(vector<pair<int, int>> adj[], int u, int e, vector<int> &cnt)
{
    for(auto v: adj[u])
    {
        if(v.first!=e)
        {
            cnt[v.first] = cnt[u]+1;
            depth2(adj, v.first, u, cnt);
        }
    }
}
 
void all_pairs_distance2(vector<pair<int, int>> adj[], int N, vector<vector<int>> &cnt)
{
    for(int i = 0; i<N; i++)
    {
        vector<int> temp(N);
        depth2(adj, i, -1, temp);
        cnt.push_back(temp);
    }
}
 
int best_path(int N, int K, int H[][2], int L[])
{
    vector<pair<int, int>> adj[N];
    for(int i = 0; i<N-1; i++)
    {
        adj[H[i][0]].push_back(make_pair(H[i][1], L[i]));
        adj[H[i][1]].push_back(make_pair(H[i][0], L[i]));
    }
 
    vector<vector<int>> cnt;
    all_pairs_distance(adj, N, cnt);
 
    vector<vector<int>> cnt2;
    all_pairs_distance2(adj, N, cnt2);
 
    bool flag = false;
    int res = 1e8;
    for(int i = 0; i<N; i++)
    {
        for(int j = 0; j<N; j++)
        {
            if(cnt[i][j]==K)
                res = min(res, cnt2[i][j]), flag = true;
        }
    }
 
    if(!flag)
        return -1;
    return res;
}

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