Submission #774463

#	Time	Username	Problem	Language	Result	Execution time	Memory
774463		teokakabadze	Race (IOI11_race)	C++17	9 / 100	80 ms	27464 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define n 200005
#define pii pair<int, int>
using namespace std;

int ans = 1e9, i, k, s[n], s1[n];
vector<pii> v[n];
map<int, int> m[n];

void dfs(int u, int p)
{
    pii b = {-1, 0};
    int mx = 0;
    for(auto x : v[u])
    if(x.f != p)
    {
        dfs(x.f, u);
        if(m[x.f].size() > mx) mx = m[x.f].size(), b = x;
    }
    if(b.f != -1)
    {
        s[u] = s[b.f] + b.s;
        s1[u] = s1[b.f] + 1;
        swap(m[u], m[b.f]);
        if(m[u].find(b.s - s[u]) != m[u].end()) m[u][b.s - s[u]] = min(1 - s1[u], m[u][b.s - s[u]]);
        else m[u][b.s - s[u]] = 1 - s1[u];
    }
    for(auto x : v[u])
    if(x.f != p && x.f != b.f)
    {
        for(auto y : m[x.f])
        {
            int c = y.f + s[x.f] - s[u];
            if(m[u].find(k - 2 * s[u] - c) != m[u].end()) ans = min(ans, m[u][c] + m[u][k - 2 * s[u] - c] + 2 * s1[u]);
        }
        int c = x.s - s[u];
        if(m[u].find(k - 2 * s[u] - c) != m[u].end()) ans = min(ans, m[u][c] + m[u][k - 2 * s[u] - c] + 2 * s1[u]);
        if(m[u].find(x.s - s[u]) != m[u].end()) m[u][x.s - s[u]] = min(1 - s1[u], m[u][x.s - s[u]]);
        else m[u][x.s - s[u]] = 1 - s1[u];
        for(auto y : m[x.f])
        {
            int c = y.f + s[x.f] - s[u];
            if(m[u].find(c) != m[u].end()) m[u][c] = y.s + s1[x.f] - s1[u];
            else m[u][c] = min(m[u][c], y.s + s1[x.f] - s1[u]);
        }
    }
    if(m[u].find(k - s[u]) != m[u].end()) ans = min(ans, m[u][k - s[u]] + s1[u]);
   /* cout << "SIZE " << u << ' ' << m[u].size() << ' ' << b.f << '\n';
    for(auto x : m[u])
        cout << x.f + s[u] << ' ' << x.s + s1[u] << '\n'; */
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for(i = 0; i < N - 1; i++)
    {
        v[H[i][0]].pb({H[i][1], L[i]});
        v[H[i][1]].pb({H[i][0], L[i]});
    }
    dfs(0, 0);
    if(ans == 1e9) return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:22:26: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |         if(m[x.f].size() > mx) mx = m[x.f].size(), b = x;
      |            ~~~~~~~~~~~~~~^~~~

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