oj.uz

Submission #994430

# Submission time Handle Problem Language Result Execution time Memory
994430 2024-06-07T15:40:22 Z pannenkoek Race (IOI11_race) C++14
0 / 100
 3 ms 18008 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define pb push_back
#define fi first
#define se second

using ll = long long;
using ld = long double;
using pii = pair<ll, ll>;

const int MAXN = 2e5 + 5;
vector<pii> adj[MAXN];
map<ll, ll> poss[MAXN]; 
ll res = 1e18;
int k;

void dfs(ll v, ll p){
    poss[v][0] = 0;
    for(auto [u, d]: adj[v]){
        if(u == p) continue;
        dfs(u, v);
        if(poss[u].size() > poss[v].size()) swap(poss[u], poss[v]);
        for(auto [dis, cost]: poss[u]){
            ll new_dis = dis + d;
            if(new_dis > k) continue;
            if(poss[v].count(k - dis - d)) {
                res = min(poss[v][k - dis - d] + 1 + cost, res);
            }
            if(poss[v].count(new_dis))
                poss[v][new_dis] = min(poss[v][new_dis], cost + 1);
            else
                poss[v][new_dis] = cost + 1;
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    rep(i, 0, N) {
        adj[i] = {};
        poss[i] = {};
    }
    k = K;
    rep(i, 0, N - 1) {
        adj[H[i][0]].pb({H[i][1], L[i]});
        adj[H[i][1]].pb({H[i][0], L[i]});
    }
    dfs(0, -1); 
    if(res < 1e18) return res;
    else return -1;
}

Compilation message

race.cpp: In function 'void dfs(ll, ll)':
race.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for(auto [u, d]: adj[v]){
      |              ^
race.cpp:25:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |         for(auto [dis, cost]: poss[u]){
      |                  ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 18008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 18008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 18008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 18008 KB Output isn't correct
2 Halted 0 ms 0 KB -