Submission #413076

#	Time	Username	Problem	Language	Result	Execution time	Memory
413076		ngpin04	Race (IOI11_race)	C++14	0 / 100	8 ms	14432 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) 
            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