Submission #838140

#	Time	Username	Problem	Language	Result	Execution time	Memory
838140		becaido	Highway Tolls (IOI18_highway)	C++17	100 / 100	188 ms	12148 KiB

highway

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for(int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1.3e5 + 5;

ll len;
vector<pair<int, int>> adj[SIZE], all[2];
vector<int> e;
int g[SIZE];
bool is[SIZE];

int cal(int s, int M) {
    int sz = all[s].size();
    int l = 0, r = sz - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        FOR (i, 0, M - 1) e[i] = !is[i];
        FOR (i, mid + 1, sz - 1) e[all[s][i].S] = 1;
        if (ask(e) == len) r = mid;
        else l = mid + 1;
    }
    return all[s][l].F;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();
    e.resize(M, 0);
    FOR (i, 0, M - 1) {
        adj[U[i]].pb(V[i], i);
        adj[V[i]].pb(U[i], i);
    }
    len = ask(e);
    int l = 0, r = M - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        fill(e.begin(), e.end(), 0);
        fill(e.begin(), e.begin() + mid + 1, 1);
        if (ask(e) == len) l = mid + 1;
        else r = mid;
    }
    queue<int> q;
    is[l] = 1;
    fill(g, g + N, -1);
    q.push(U[l]), g[U[l]] = 0, all[0].pb(U[l], -1);
    q.push(V[l]), g[V[l]] = 1, all[1].pb(V[l], -1);
    while (q.size()) {
        int pos = q.front();
        q.pop();
        for (auto [np, id] : adj[pos]) if (g[np] == -1) {
            g[np] = g[pos];
            is[id] = 1;
            all[g[pos]].pb(np, id);
            q.push(np);
        }
    }
    answer(cal(0, M), cal(1, M));
}

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