Submission #413077

#	Time	Username	Problem	Language	Result	Execution time	Memory
413077		ngpin04	Race (IOI11_race)	C++14	0 / 100	9 ms	14412 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 <long long, int> s[Nmax];

long long val[Nmax];

int cnt[Nmax];
int k, ans = 1e9;

void dfs(int u, int p) {
    int vmax = u;
    for (pair <int, int> e : adj[u]){
        int v = e.fi;
        int w = e.se;
        if (v == p)
            continue;
        dfs(v, u);
        if (s[v].size() > s[vmax].size()) {
            vmax = v;
            cnt[u] = cnt[vmax] + 1;
            val[u] = val[vmax] + w;
        }
    }

    swap(s[u], s[vmax]);
    if (!s[u].count(-val[u]))
        s[u][-val[u]] = -cnt[u];
    else 
        s[u][-val[u]] = min(s[u][-val[u]], -cnt[u]);

    if (vmax == u) 
        return;

    for (pair <int, int> e : adj[u]) {
        int v = e.fi;
        int w = e.se;   
        if (v == vmax || v == p) 
            continue;
        for (pair <long long, int> pir : s[v]) {
            long long res = k - ((pir.fi + val[v] + w) + val[u]);
            if (s[u].count(res))
                ans = min(ans, (s[u][res] + cnt[u]) + (pir.se + cnt[v]) + 1);
        }
        
        for (pair <long long, int> pir : s[v]) {
            long long res = (pir.fi + val[v] + w) - val[u];
            int rescnt = (pir.se + cnt[v] + 1) - cnt[u];
            if (!s[u].count(res))
                s[u][res] = rescnt;
            else 
                s[u][res] = min(s[u][res], rescnt);
        }   
    }

    // cout << "Path " << u << ": \n";
    // for (pair <long long, int> pir : s[u]) 
    //     cout << pir.fi + val[u] << " " << pir.se + cnt[u] << "\n";
}

int best_path(int N, int K, int H[][2], int L[])
{
    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