Submission #988879

#	Time	Username	Problem	Language	Result	Execution time	Memory
988879		NoLove	Race (IOI11_race)	C++14	100 / 100	325 ms	102740 KiB

race

/**
 *    author : Lăng Trọng Đạt
 *    created: 26-05-2024 
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define all(v) (v).begin(), (v).end()
using pii = pair<int, int>;
using vi = vector<int>;
#define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
void mx(int& a, int b) { if (b > a) a = b; }
void mi(int& a, int b) { if (b < a) a = b; }
#define si(x) (int)(x.size())
const int INF = 1e18;
const int MOD = 1e9 + 7;

const int MAXN = 5e5 + 5;
int g[MAXN];
int n, ans = INF, k;
vector<pii> adj[MAXN];
map<int, int> md[MAXN]; // md[v][l] = độ sâu lớn nhất khi đi khoảng cách từ node đó đến root đúng = l

void dfs(int v, int prv, int len, int d) {
    md[v][len] = d;
    for (auto[u, l] : adj[v]) {
        if (u == prv) continue;
        dfs(u, v, len + l, d + 1);
        if (si(md[u]) > si(md[v])) swap(md[u], md[v]);
        // x + y - 2 * len = k
        // length = depth + depth_y - 2*d
        for (auto[x, depth] : md[u]) {
            if (md[v].count(k + 2*len - x)) {
                mi(ans, depth + md[v][k + 2*len - x] - 2*d);
            }
        }
        for (auto[x, depth] : md[u]) {
            if (md[v].count(x)) {
                mi(md[v][x], depth);
            } else {
                md[v][x] = depth;
            }
        }
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    FOR(i, 0, N - 2) {
        adj[H[i][0]].pb({H[i][1], L[i]});
        adj[H[i][1]].pb({H[i][0], L[i]});
    }
    dfs(1, -1, 0, 0);

    return (ans == INF ? -1 : ans);
}

Compilation message (stderr)

race.cpp:21:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   21 | const int INF = 1e18;
      |                 ^~~~
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |     for (auto[u, l] : adj[v]) {
      |              ^
race.cpp:38:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         for (auto[x, depth] : md[u]) {
      |                  ^
race.cpp:43:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |         for (auto[x, depth] : md[u]) {
      |                  ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:17:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
race.cpp:55:5: note: in expansion of macro 'FOR'
   55 |     FOR(i, 0, N - 2) {
      |     ^~~

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