제출 #624042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
624042		79brue	통행료 (IOI18_highway)	C++17	100 / 100	261 ms	13772 KiB

highway

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

using namespace std;

typedef long long ll;

int n, m;
ll A, B;
int ex[130002], ey[130002];
vector<pair<int, int> > link[100002];
ll def;

int U, V;
void findOneEdge(){
    int L = 0, R = m-2, ANS = m-1;
    while(L<=R){
        int MID = (L+R)/2;
        vector<int> tv (m, 0);
        for(int i=0; i<=MID; i++) tv[i] = 1;
        if(ask(tv) != def) ANS = MID, R = MID-1;
        else L = MID+1;
    }
    U = ex[ANS], V = ey[ANS];
}

int uDist[100002], vDist[100002];
void bfs(int st, int *dist){
    queue<pair<int, int> > que;
    vector<bool> vec (n);
    que.push(make_pair(st, 0));
    vec[st] = 1;

    while(!que.empty()){
        pair<int, int> tmp = que.front(); que.pop();
        dist[tmp.first] = tmp.second;
        for(auto y: link[tmp.first]){
            if(vec[y.first]) continue;
            vec[y.first] = 1;
            que.push(make_pair(y.first, tmp.second+1));
        }
    }
}

int group[100002]; /// 1이면 U그룹, 2이면 V그룹
vector<int> base;
vector<int> uVec, vVec;
int uIdx[100002], vIdx[100002];

void binarySearch(int &X, vector<int> &vec, int *idx, int gnum){
    int sz = (int)vec.size();
    int L = 0, R = sz-2, ANS = sz-1;
    while(L<=R){
        int MID = (L+R)/2;
        vector<int> v = base;
        for(int i=0; i<m; i++){
            if(group[ex[i]] == gnum && group[ey[i]] == gnum && ((idx[ex[i]] <= MID) ^ (idx[ey[i]] <= MID))) v[i] = 1;
        }
        if(ask(v) != def) L = MID+1;
        else ANS = MID, R = MID-1;
    }
    X = vec[ANS];
}

void find_pair(int N, vector<int> _U, vector<int> _V, int _A, int _B){
    n = N;
    m = (int)_U.size();
    def = ask(vector<int> (m, 0));
    for(int i=0; i<m; i++){
        ex[i] = _U[i], ey[i] = _V[i];
        link[ex[i]].push_back(make_pair(ey[i], i));
        link[ey[i]].push_back(make_pair(ex[i], i));
    }
    A = _A, B = _B;

    findOneEdge();
    bfs(U, uDist);
    bfs(V, vDist);

    for(int i=0; i<n; i++){
        if(uDist[i] == vDist[i]) continue;
        if(uDist[i] < vDist[i]) group[i] = 1;
        else group[i] = 2;
    }

    base = vector<int> (m, 0);
    for(int i=0; i<m; i++){
        if(!group[ex[i]] || !group[ey[i]] || group[ex[i]] != group[ey[i]]) base[i] = 1;
        else if(group[ex[i]] == 1){
            if(abs(uDist[ex[i]] - uDist[ey[i]]) != 1) base[i] = 1;
        }
        else if(group[ex[i]] == 2){
            if(abs(vDist[ex[i]] - vDist[ey[i]]) != 1) base[i] = 1;
        }
        if((U==ex[i] && V==ey[i]) || (U==ey[i] && V==ex[i])) base[i] = 0;
    }

    for(int i=0; i<n; i++){
        if(group[i] == 1) uVec.push_back(i);
        if(group[i] == 2) vVec.push_back(i);
    }
    sort(uVec.begin(), uVec.end(), [&](int x, int y){
        return uDist[x] < uDist[y];
    });
    sort(vVec.begin(), vVec.end(), [&](int x, int y){
        return vDist[x] < vDist[y];
    });
    for(int i=0; i<(int)uVec.size(); i++) uIdx[uVec[i]] = i;
    for(int i=0; i<(int)vVec.size(); i++) vIdx[vVec[i]] = i;

    binarySearch(U, uVec, uIdx, 1);
    binarySearch(V, vVec, vIdx, 2);
    answer(U, V);
}

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