Submission #793272

#	Time	Username	Problem	Language	Result	Execution time	Memory
793272		welleyth	Highway Tolls (IOI18_highway)	C++17	100 / 100	291 ms	16528 KiB

highway

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

using namespace std;

constexpr int NN = 90000;

//#define int long long

typedef long long ll;

vector<pair<int,int>> g[NN];
vector<pair<int,int>> BFSTree[NN];
bool can[NN];
bool marked[NN];
bool wasL[NN],wasR[NN];
bool banned[NN];

void dfs(int v,int& c){
    marked[v] = true;
    c -= can[v];
    for(auto&[to,id] : g[v]){
        if(c > 0 && !marked[to]){
            dfs(to,c);
        }
    }
    return;
}

void dfsL(int v,int& c){
    if(wasL[v]){
        marked[v] = true;
        c -= can[v];
    }
    for(auto&[to,id] : BFSTree[v]){
        if(c > 0 && !marked[to] && wasL[to]){
            dfsL(to,c);
        }
    }
    return;
}

void dfsR(int v,int& c){
    if(wasR[v]){
        marked[v] = true;
        c -= can[v];
    }
    for(auto&[to,id] : BFSTree[v]){
        if(c > 0 && !marked[to] && wasR[to]){
            dfsR(to,c);
        }
    }
    return;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B){
    int m = U.size();

    for(int i = 0; i < m; i++){
        g[U[i]].push_back(make_pair(V[i],i));
        g[V[i]].push_back(make_pair(U[i],i));
    }

    vector<int> w(m,0);
    ll minVal = ask(w);

    for(int i = 0; i < N; i++){
        can[i] = true;
    }

    int edgeID = -1;

    {
        vector<int> v;
        for(int i = 0; i < m; i++) v.push_back(i);
        bool s[m];
        for(int i = 0; i < m; i++){
            s[i] = 0;
        }
        while(v.size() > 1){
            vector<int> L,R;
            for(auto& id : v){
                if(R.size() < L.size())
                    R.push_back(id);
                else
                    L.push_back(id);
            }
            for(int i = 0; i < m; i++) w[i] = s[i];
            for(auto& id : L) w[id] = 1;
            ll val1 = ask(w);
            if(val1 > minVal){

                v = L;
            }
            else {
                for(auto& id : L) s[id] = true;
                v = R;
            }
        }
        assert(!v.empty());
        edgeID = v[0];
    }

    vector<int> BFSEdges;
    {
        bool used[N];
        memset(used,0,sizeof used);
        queue<int> q;
        q.push(U[edgeID]);
        used[U[edgeID]] = true;
        q.push(V[edgeID]);
        used[V[edgeID]] = true;
        BFSEdges.push_back(edgeID);

        while(!q.empty()){
            int v = q.front();
            q.pop();
            for(auto&[to,id] : g[v]){
                if(!used[to]){
                    used[to] = true;
                    q.push(to);
                    BFSEdges.push_back(id);
                    BFSTree[v].push_back(make_pair(to,id));
                    BFSTree[to].push_back(make_pair(v,id));
                }
            }
        }
    }

    {
        int u = U[edgeID], v = V[edgeID];
        banned[u] = banned[v] = true;
        queue<int> q;
        q.push(u);
        while(!q.empty()){
            int vv = q.front();
            wasL[vv] = true;
            can[vv] = true;
            q.pop();
            for(auto&[to,id] : BFSTree[vv]){
                if(!banned[to] && !wasL[to]){
                    wasL[to] = true;
                    can[to] = true;
                    q.push(to);
                }
            }
        }
        q.push(v);
        while(!q.empty()){
            int vv = q.front();
            q.pop();
            wasR[vv] = true;
            can[vv] = true;
            for(auto&[to,id] : BFSTree[vv]){
                if(!banned[to] && !wasR[to]){
                    wasR[to] = true;
                    can[to] = true;
                    q.push(to);
                }
            }
        }
    }

    bool notInBFSTRee[m];
    for(int i = 0; i < m; i++) notInBFSTRee[i] = true;
    for(auto& id : BFSEdges) notInBFSTRee[id] = false;

    int s,t;
    s = t = -1;

    {
        int root = U[edgeID];
        int cnt = 0;
        for(int i = 0; i < N; i++){
            if(wasL[i]){
                cnt += can[i];
            }
        }
        while(cnt > 1){
            for(int i = 0; i < N; i++) marked[i] = false;
            int c = cnt/2;
            dfsL(root,c);
            for(int i = 0; i < m; i++) w[i] = notInBFSTRee[i];
            for(int i = 0; i < N; i++){
                for(auto&[to,id] : g[i]){
                    if(marked[i] && !marked[to] && !banned[to])
                        w[id] = true;
                }
            }
            if(ask(w) > minVal){
                for(int i = 0; i < N; i++){
                    if(wasL[i] && marked[i])
                        can[i] = false;
                }
            } else {
                for(int i = 0; i < N; i++){
                    if(wasL[i] && !marked[i])
                        can[i] = false;
                }
            }

            cnt = 0;
            for(int i = 0; i < N; i++){
                if(wasL[i])
                    cnt += can[i];
            }
        }
        for(int i = 0; i < N; i++){
            if(wasL[i] && can[i])
                s = i;
        }
    }
    {
        int root = V[edgeID];
        int cnt = 0;
        for(int i = 0; i < N; i++){
            if(wasR[i])
                cnt += can[i];
        }
        while(cnt > 1){
            for(int i = 0; i < N; i++) marked[i] = false;
            int c = cnt/2;
            dfsR(root,c);
            for(int i = 0; i < m; i++) w[i] = notInBFSTRee[i];
            for(int i = 0; i < N; i++){
                for(auto&[to,id] : g[i]){
                    if(marked[i] && !marked[to] && !banned[to])
                        w[id] = true;
                }
            }
            if(ask(w) > minVal){
                for(int i = 0; i < N; i++){
                    if(wasR[i] && marked[i])
                        can[i] = false;
                }
            } else {
                for(int i = 0; i < N; i++){
                    if(wasR[i] && !marked[i])
                        can[i] = false;
                }
            }

            cnt = 0;
            for(int i = 0; i < N; i++){
                if(wasR[i])
                    cnt += can[i];
            }
        }
        for(int i = 0; i < N; i++){
            if(wasR[i] && can[i])
                t = i;
        }
    }

    answer(s,t);

    return;
}

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