Submission #1196657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196657		aguss	Highway Tolls (IOI18_highway)	C++20	5 / 100	9 ms	4680 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << ": " << x << "\n";
#define dbgv(x) cerr << #x << ": "; for(const auto &i : x) cerr << i << " "; cerr << "\n";
using namespace std;
using ll = long long;
vector<vector<int>> adj;
vector<pair<long long, long long>> depth;
unordered_map<int, unordered_map<int, int>> path;

int get_path(int node, int i){
    return path[node][i];
}

void dfs(int node, int prev){
    for(int &i : adj[node]){
        if(i == prev) continue;
        depth[i] = {depth[node].first + 1, get_path(node, i)};
        dfs(i, node);
    }
}

int max_depth(int a, int b){
    if(depth[a].first > depth[b].first) return a;
    return b;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    adj.assign(N, vector<int>());
    depth.assign(N, {0, 0});
    int ans = 0;
    for(int i = 0; i < (int)U.size(); i++){
        path[U[i]][V[i]] = i;
        path[V[i]][U[i]] = i;
        adj[U[i]].push_back(V[i]);
        adj[V[i]].push_back(U[i]);
    }
    vector<int> vec(N - 1, 0);
    long long x = ask(vec);
    dfs(0, -1);
    for(int i = 0; i < (int)depth.size(); i++){
        if(depth[i].first == x / (long long)A){
            vec[depth[i].second] = 1;
            int new_dis = ask(vec);
            if(new_dis != x){
                ans = max_depth(U[depth[i].second], V[depth[i].second]); 
                break;
            }
        }
    }
    answer(0, ans);
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31