Submission #1196661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196661		aguss	Highway Tolls (IOI18_highway)	C++20	5 / 100	10 ms	4524 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;
vector<vector<int>> adj;
vector<pair<long long, int>> depth;
unordered_map<int, unordered_map<int, int>> path;
void dfs(int node, int prev){
    for(const int &i : adj[node]){
        if(i == prev) continue;
        depth[i] = {depth[node].first + 1, 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, vector<int> U, vector<int> V, int A, int B) {
    adj.assign(N, vector<int>());
    depth.assign(N, {0, 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, 0);
    for(int i = 0; i < (int)depth.size(); i++){
        if(depth[i].first == x / (long long)A){
            vec[depth[i].second] = 1;
            long long new_dis = ask(vec);
            if(new_dis != x){
                answer(0, max_depth(U[depth[i].second], V[depth[i].second]));
                return;
            }
        }
    }
}

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