제출 #982852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982852		mariaclara	통행료 (IOI18_highway)	C++17	90 / 100	193 ms	11436 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 4e5+5; 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    vector<vector<pii>> edges(N);
    int M = sz(U);

    for(int i = 0; i < M; i++)
        edges[U[i]].pb({V[i], i}), edges[V[i]].pb({U[i], i});

    int Raiz = 0;
    vector<int> query(M);
    ll def = ask(query);
    if(M != N-1) {
        int l = 0, r = N-1;

        while(l < r) {
            int mid = (l+r)/2;

            for(int i = 0; i <= mid; i++)
                for(auto [viz,ind] : edges[i])
                    query[ind] = 1;

            if(ask(query) > def) r = mid;
            else l = mid+1;

            for(int i = 0; i < M; i++) query[i] = 0;
        }

        Raiz = l;
    }

    vector<int> dist(N), ord_edges;
    queue<int> fila;
    fila.push(Raiz);

    while(!fila.empty()) {
        int x = fila.front();
        fila.pop();

        for(auto [viz, ind] : edges[x]) {
            if(dist[viz] == 0 and viz != Raiz) {
                dist[viz] = dist[x] + 1;
                ord_edges.pb(ind);
                fila.push(viz);
            }
        }
    }

    query.clear();
    query.resize(M,1);
    for(int i = 0; i < N-1; i++) query[ord_edges[i]] = 0;

    if(def == 0) def = ask(query);

    int l = 0, r = N-1;
    while(l < r) {
        int mid = (l+r)/2;
        for(int i = 0; i <= mid; i++) query[ord_edges[i]] = 0;
        for(int i = mid+1; i < N-1; i++) query[ord_edges[i]] = 1;
        if(ask(query) > def) l = mid+1;
        else r = mid;
    }

    int k = ord_edges[l], S;
    if(dist[U[k]] > dist[V[k]]) S = U[k];
    else S = V[k];

    ord_edges.clear();
    fila.push(S);
    dist.clear();
    dist.resize(N,0);

    while(!fila.empty()) {
        int x = fila.front();
        fila.pop();

        for(auto [viz, ind] : edges[x]) {
            if(dist[viz] == 0 and viz != S) {
                dist[viz] = dist[x] + 1;
                ord_edges.pb(ind);
                fila.push(viz);
            }
        }
    }

    query.clear();
    query.resize(M,1);
    for(int i = 0; i < N-1; i++) query[ord_edges[i]] = 0;

    l = 0;
    r = N-1;
    while(l < r) {
        int mid = (l+r)/2;
        for(int i = 0; i <= mid; i++) query[ord_edges[i]] = 0;
        for(int i = mid+1; i < N-1; i++) query[ord_edges[i]] = 1;
        if(ask(query) > def) l = mid+1;
        else r = mid;
    }

    k = ord_edges[l];
    int T = V[k];
    if(dist[U[k]] > dist[V[k]]) T = U[k];
    
    answer(S,T);
}

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