제출 #1016954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1016954		vyshniak_n	통행료 (IOI18_highway)	C++17	5 / 100	84 ms	17140 KiB

highway

//#pragma optimize("Ofast")
//#pragma optimize("unroll-loops")
//#pragma traget("avx,avx2")

#include "highway.h"
 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
using namespace std;
 
#include <random>
mt19937 rnd(time(0));

const int maxn = 9e4 + 10;
vector <pair <int, int>> gr[maxn];
int from[maxn], dist[maxn];

void find_pair(int n, vector <int> u, vector <int> v, int a, int b) {
    int m = u.size();

    vector <int> q(m);
    int len = ask(q) / a;

    int l = -1, r = m;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;

        for (int i = 0; i <= mid; i++)
            q[i] = 1;
        for (int i = mid + 1; i < m; i++)
            q[i] = 0;

        if (ask(q) == len * a) l = mid;
        else r = mid;
    }

    for (int i = 0; i < m; i++)
        q[i] = 1;
    q[r] = 0;

    for (int i = 0; i < m; i++) {
        if (i == r)
            continue;

        gr[u[i]].pb({v[i], i});
        gr[v[i]].pb({u[i], i});
    }

    vector <int> left, right;
    for (int i = 0; i < n; i++)
        from[i] = -1;
    from[u[r]] = u[r];
    from[v[r]] = v[r];

    queue <int> qu;
    qu.push(u[r]);
    qu.push(v[r]);

    while (!qu.empty()) {
        int ver = qu.front();
        qu.pop();

        for (auto &[to, id] : gr[ver]) {
            if (from[to] != -1)
                continue;

            from[to] = from[ver];
            dist[to] = dist[ver] + 1;
            if (from[to] == u[r]) left.pb(id);
            else right.pb(id);

            q[id] = 0;
            qu.push(to);
        }
    }

    vector <int> now;
    int s = u[r], t = v[r];

    now = q;
    for (int i : left)
        now[i] = 1;

    int len_left = ask(now);
    l = -2, r = left.size();
    while (l + 1 < r) {
        int mid = (l + r) >> 1;

        now = q;
        for (int i = 0; i <= mid; i++)
            now[left[i]] = 1;

        if (ask(now) == len_left) r = mid;
        else l = mid;
    }

    if (r != -1) {
        if (dist[u[left[r]]] > dist[v[left[r]]]) s = u[left[r]];
        else s = v[left[r]];
    }

    now = q;
    for (int i : right)
        now[i] = 1;

    int len_right = ask(now);
    l = -2, r = right.size();
    while (l + 1 < r) {
        int mid = (l + r) >> 1;

        now = q;
        for (int i = 0; i <= mid; i++)
            now[right[i]] = 1;

        if (ask(now) == len_right) r = mid;
        else l = mid;
    }

    if (r != -1) {
        if (dist[u[right[r]]] > dist[v[right[r]]]) t = u[right[r]];
        else t = v[right[r]];
    }

    answer(s, t);
    return;
}

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