oj.uz

Submission #1067045

# Submission time Handle Problem Language Result Execution time Memory
1067045 2024-08-20T10:04:51 Z Thunnus Race (IOI11_race) C++17
0 / 100
 2 ms 11868 KB 
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int MAXN = 2e5 + 5;
int ans = LLONG_MAX, k;
vector<map<int, int>> mp(MAXN);

inline void dfs(vector<vector<pii>> &adj, int v = 0, int p = -1, int dist = 0, int dep = 0){
    for(pii &u : adj[v]){
        if(u.fi == p) continue;
        dfs(adj, u.fi, v, dist + u.se, dep + 1);
    }
    mp[v][dist] = dep;
    for(pii &u : adj[v]){
        if(u.fi == p) continue;
        if(sz(mp[u.fi]) > sz(mp[v])) mp[v].swap(mp[u.fi]);
        for(auto &it : mp[u.fi]){
            if(mp[v].count(k - (it.fi - 2 * dist))){ // distance with lca
                ans = min(ans, mp[v][k - (it.fi - 2 * dist)] + it.se - 2 * dep);
            }
        }
        for(auto &it : mp[u.fi]){
            if(!mp[v].count(it.fi)) mp[v][it.fi] = it.se;
            else mp[v][it.fi] = min(mp[v][it.fi], it.se);
            if(it.fi - dist == k){
                ans = min(ans, it.se - dep);
            } 
        }
    }
}

int32_t best_path(int32_t n, int32_t K, int32_t h[][2], int32_t l[]){
	k = K;
    vector<vector<pii>> adj(n);
    for(int i = 0; i < n; i++){
        adj[h[i][0]].emplace_back(h[i][1], l[i]);
        adj[h[i][1]].emplace_back(h[i][0], l[i]);
    }
    dfs(adj);
    return (ans == LLONG_MAX ? -1 : ans);
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 57.0

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