제출 #1123723

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123723		Pacybwoah	통행료 (IOI18_highway)	C++20	51 / 100	142 ms	22972 KiB

highway

#include "highway.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
#include<utility>
using namespace std;
typedef long long ll;
namespace{
    int n, m;
    int maxi = 0;
    vector<vector<int>> deped;
    vector<vector<pair<int, int>>> depv;
    vector<int> dep;
    vector<vector<pair<int, int>>> graph;
    void dfs(int node, int parent){
        dep[node] = dep[parent] + 1;
        maxi = max(maxi, dep[node]);
        for(auto &[x, id]: graph[node]){
            if(x == parent){
                depv[dep[node]].emplace_back(node, id);
                continue;
            }
            deped[dep[node]].push_back(id);
            dfs(x, node);
        }
    }
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B){
    n = N;
    m = (int)U.size();
    assert(m == n - 1);
    deped.resize(n + 1);
    dep.resize(n + 1);
    depv.resize(n + 1);
    graph.resize(n + 1);
    for(int i = 0; i < m; i++){
        graph[U[i]].emplace_back(V[i], i);
        graph[V[i]].emplace_back(U[i], i);
    }
    dfs(0, 0);
    int l = 1, r = maxi - 1;
    vector<int> que(m);
    ll a = A, b = B;
    ll len = ask(que) / a;
    while(l < r){
        int mid = (l + r) >> 1;
        for(int i = 0; i < m; i++) que[i] = 0;
        for(int i = 1; i <= mid; i++){
            for(auto &id: deped[i]) que[id] = 1;
        }
        if(ask(que) == len * b) r = mid;
        else l = mid + 1;
    }
    int mdep = l + 1;
    l = 0, r = (int)depv[mdep].size() - 1;
    while(l < r){
        int mid = ((l + r) >> 1);
        for(int i = 0; i < m; i++) que[i] = 0;
        for(int i = 0; i <= mid; i++) que[depv[mdep][i].second] = 1;
        if(ask(que) == len * a) l = mid + 1;
        else r = mid;
    }
    int s = depv[mdep][l].first;
    mdep = len + 1;
    //cout << mdep << "\n";
    vector<vector<pair<int, int>>>().swap(depv);
    depv.resize(n + 1);
    fill(dep.begin(), dep.end(), 0);
    dfs(s, s);
    l = 0, r = (int)depv[mdep].size() - 1;
    while(l < r){
        int mid = ((l + r) >> 1);
        for(int i = 0; i < m; i++) que[i] = 0;
        for(int i = 0; i <= mid; i++) que[depv[mdep][i].second] = 1;
        if(ask(que) == len * a) l = mid + 1;
        else r = mid;
    }
    int t = depv[mdep][l].first;
    //cout << s << " " << t << "\n";
    answer(s, t);
    //answer(0, 1);
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp highway.cpp

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