Submission #413052

#	Time	Username	Problem	Language	Result	Execution time	Memory
413052		ngpin04	Race (IOI11_race)	C++14	0 / 100	22 ms	29004 KiB

race

#include <bits/stdc++.h>
#include "race.h"
//#include "grader.cpp"
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int Nmax = 2e5 + 5;

vector <pair <int, int>> adj[Nmax];

map <int, int> s[Nmax];

int k, ans = 1e9;

void dfs(int u, int p) {
    s[u][0] = 0;
    for (pair <int, int> e : adj[u]){
        int v = e.fi;
        int w = e.se;
        if (v == p)
            continue;
        dfs(v, u);
        if (s[u].size() < s[v].size())
            swap(s[u], s[v]);

        for (pair <int, int> pir : s[v]) 
            if (s[u].count(k - pir.fi - w))
                ans = min(ans, s[u][k - pir.fi - w] + pir.se + 1);
        
        for (pair <int, int> pir : s[v]) if (pir.fi + w <= k) {
            if (!s[u].count(pir.fi + w))
                s[u][pir.fi + w] = pir.se + 1;
            else 
                s[u][pir.fi + w] = min(s[u][pir.fi + w], pir.se + 1);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    assert(N <= 2);
    k = K;
    for (int i = 0; i < N - 1; i++) {   
        int u = H[i][0];
        int v = H[i][1];
        adj[u].push_back(mp(v, L[i]));
        adj[v].push_back(mp(u, L[i]));
    }

    dfs(0, -1);
    if (ans == 1e9)
        ans = -1;
    return ans;                                                                               
}

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