Submission #422149

#	Time	Username	Problem	Language	Result	Execution time	Memory
422149		Peti	통행료 (IOI18_highway)	C++14	51 / 100	260 ms	11480 KiB

highway

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

using namespace std;

const int maxn = (int)1e5;

vector<vector<pair<int, int>>> g;
vector<int> ose, el, gTav;
long long tav, A, B;
int N, M;

int el_keres(){
    vector<int> query(M, 0);
    int l = 0, r = M;
    while(l+1 < r){
        vector<int> query2 = query;
        int m = (l+r)/2;
        for(int i = l; i < m; i++)
            query2[i] = 1;
        long long ans = ask(query2);
        if(ans != tav*A){
            r = m;
        } else{
            for(int i = l; i < m; i++)
                query[i] = 1;
            l = m;
        }
    }
    return l;
}

int sor[maxn];
void bejar(int x, int y, int elInd){
    vector<bool> volt(N, false);
    sor[0] = x;
    sor[1] = y;
    volt[x] = volt[y] = true;
    ose[x] = x;
    ose[y] = y;
    el[x] = el[y] = elInd;
    gTav[x] = gTav[y] = 0;
    int ind = 0, veg = 2;
    while(ind < veg){
        int akt = sor[ind];
        for(auto e : g[akt]){
            if(!volt[e.first]){
                volt[e.first] = true;
                el[e.first] = e.second;
                ose[e.first] = ose[akt];
                gTav[e.first] = gTav[akt]+1;
                sor[veg++] = e.first;
            }
        }
        ind++;
    }
}

int get(int os){
    vector<int> v;
    for(int i = 0; i < N; i++)
        if(ose[i] == os)
            v.push_back(i);
    sort(v.begin(), v.end(), [](int a, int b){return gTav[a] < gTav[b]; });
    int l = 0, r = (int)v.size();
    while(l+1 < r){
        int m = (l+r)/2;
        vector<int> query(M, 1);
        for(int i = m; i < r; i++)
            query[el[v[i]]] = 0;
        long long ans = ask(query);
        if(ans < tav*B)
            l = m;
        else
            r = m;
    }
    return v[l];
}

void find_pair(int n, std::vector<int> U, std::vector<int> V, int CA, int CB) {
    //cout<<"called"<<endl;
    N = n;
    M = (int)U.size();
    A = CA;
    B = CB;
    g.resize(N);
    el.resize(N);
    ose.resize(N);
    gTav.resize(N);
    for(int i = 0; i < M; i++){
        g[U[i]].emplace_back(V[i], i);
        g[V[i]].emplace_back(U[i], i);
    }

    vector<int> query(M, 0);
    tav = ask(query)/A;

    //cout<<"tav: "<<tav<<endl;

    int ind = el_keres();
    //cout<<"keres kesz | ind: "<<ind<<endl;
    bejar(U[ind], V[ind], ind);

    //cout<<"bejar kesz"<<endl;
    answer(get(U[ind]), get(V[ind]));
}

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