oj.uz

Submission #1097070

# Submission time Handle Problem Language Result Execution time Memory
1097070 2024-10-06T03:06:52 Z orcslop Race (IOI11_race) C++17
0 / 100
 6 ms 14428 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first
#define s second
#define pii pair<int, int>

struct Highway{
    int a, b, w; 
}; 

const int N = 2e5 + 5; 

int n, k, ans = 1e9; 
Highway h[N]; 
map<int, int> mp[N]; 
vector<pii> adj[N]; 

void dfs(int node, int prev){
    for(auto x : adj[node]){
        if(x.f == prev) continue; 
        dfs(x.f, node); 
        if(sz(mp[x.f]) > sz(mp[node])) {
            swap(mp[x.f], mp[node]); 
        }
        if(mp[node].count(k - x.s)) {
            ans = min(ans, mp[node][k - x.s] + 1); 
        }
        for(auto y : mp[x.f]){
            if(mp[node].count(k - y.f - x.s)){
                cout << node << ' ' << y.f << '\n'; 
                ans = min(ans, mp[node][k - y.f - x.s] + y.s + 1); 
            }
        }
        mp[node][x.s] = 1; 
        for(auto y : mp[x.f]){
            if(!mp[node].count(y.f + x.s)){
                mp[node][y.f + x.s] = y.s + 1; 
            }
            else mp[node][y.f + x.s] = min(mp[node][y.f + x.s], y.s + 1); 
        }
    }
    if(mp[node].count(k)) {
        ans = min(ans, mp[node][k]); 
    }
}

int best_path(int n, int k, int edges[][2], int weights[]) {
    if (k == 1) { return 0; }
    for (int i = 0; i < n - 1; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        adj[u].pb({v, weights[i]});
        adj[v].pb({u, weights[i]});
    }
    dfs(0, -1); 
    return (ans == 1e9 ? -1 : ans);
}

// int32_t main() {
//     cin.tie(0)->sync_with_stdio(0);
//     cin >> n >> k; 
//     for(int i = 0; i < n - 1; i++){
//         cin >> h[i].a >> h[i].b; 
//     }
//     for(int i = 0; i < n - 1; i++){
//         cin >> h[i].w; 
//     }
//     for(int i = 0; i < n - 1; i++){
//         adj[h[i].a].pb({h[i].b, h[i].w}); 
//         adj[h[i].b].pb({h[i].a, h[i].w}); 
//     }
//     dfs(0, -1); 
//     cout << (ans < 1e9 ? ans : -1) << '\n'; 
//     return 0; 
// }

Subtask #1
0 / 9.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 57.0

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