Submission #497202

#	Time	Username	Problem	Language	Result	Execution time	Memory
497202		dxz05	통행료 (IOI18_highway)	C++14	69 / 100	224 ms	262148 KiB

highway

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

using namespace std;

typedef long long ll;

#define all(x) (x).begin(), (x).end()

const int MAXN = 1e5 + 3e2;

vector<int> edges;
vector<pair<int, int>> g[MAXN];

void dfs(int v, int p){
    for (auto e : g[v]){
        int u = e.first, i = e.second;
        if (u != p){
            edges.push_back(i);
            dfs(u, v);
        }
    }
}

vector<pair<int, int>> vec;
int dep;
void dfs2(int v, int p, int d){
    for (auto e : g[v]){
        int u = e.first, i = e.second;
        if (u != p){
            if (d + 1 == dep) vec.emplace_back(i, u);
            dfs2(u, v, d + 1);
        }
    }
}

int N, M;
vector<int> U, V;

bool different_groups(vector<int> &grp){
    vector<int> w(M);
    for (int i = 0; i < M; i++){
        w[i] = grp[U[i]] == grp[V[i]];
    }
    return ask(w) % 2 == 1;
}

void find_pair(int _N, vector<int> _U, vector<int> _V, int A, int B) {
    N = _N, U = _U, V = _V, M = U.size();

    for (int i = 0; i < M; i++){
        g[U[i]].emplace_back(V[i], i);
        g[V[i]].emplace_back(U[i], i);
    }

    if (A == 1 && B == 2){
        vector<int> grp(N, 0);
        for (int j = 0; j < 17; j++){
            for (int i = 0; i < N; i++){
                grp[i] = (i & (1 << j)) ? 1 : 0;
            }

            if (different_groups(grp)) break;
        }

        vector<int> q, p;
        for (int i = 0; i < N; i++){
            if (grp[i]) q.push_back(i); else
                p.push_back(i);
        }

        int S = -1, T = -1;

        int l = 0, r = q.size() - 1;
        while (l <= r){
            int mid = (l + r) >> 1;

            fill(all(grp), 0);
            for (int i = 0; i <= mid; i++) grp[q[i]] = 1;

            if (different_groups(grp)){
                S = q[mid];
                r = mid - 1;
            } else l = mid + 1;
        }

        l = 0, r = p.size() - 1;
        while (l <= r){
            int mid = (l + r) >> 1;

            fill(all(grp), 0);
            for (int i = 0; i <= mid; i++) grp[p[i]] = 1;

            if (different_groups(grp)){
                T = p[mid];
                r = mid - 1;
            } else l = mid + 1;
        }

        answer(S, T);
        return;
    }

    dfs(0, 0);

    vector<int> w(M, 0);

    ll onlyA = ask(w);

    int ind = 0;

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

        fill(all(w), 0);
        for (int i = 0; i <= mid; i++) w[edges[i]] = 1;

        ll res = ask(w);
        if (res != onlyA){
            ind = edges[mid];
            r = mid - 1;
        } else l = mid + 1;

    }

    for (int i = 0; i < g[U[ind]].size(); i++){
        if (g[U[ind]][i].first == V[ind]) g[U[ind]].erase(g[U[ind]].begin() + i);
    }
    for (int i = 0; i < g[V[ind]].size(); i++){
        if (g[V[ind]][i].first == U[ind]) g[V[ind]].erase(g[V[ind]].begin() + i);
    }

    if (g[U[ind]].empty() && g[V[ind]].empty()){
        answer(U[ind], V[ind]);
        return;
    }

    int S = -1, T = -1;

    edges.clear();
    dfs(U[ind], U[ind]);

    fill(all(w), 0);
    for (int i : edges) w[i] = 1;

    ll res = ask(w);

    dep = (res - onlyA) / (B - A);
    if (dep != 0) {
        dfs2(U[ind], U[ind], 0);

        l = 0, r = vec.size() - 1;
        while (l <= r){
            int mid = (l + r) >> 1;
            fill(all(w), 0);
            for (int i = 0; i <= mid; i++) w[vec[i].first] = 1;

            res = ask(w);
            if (res != onlyA){
                S = vec[mid].second;
                r = mid - 1;
            } else l = mid + 1;
        }
    } else S = U[ind];

    edges.clear();
    dfs(V[ind], V[ind]);

    fill(all(w), 0);
    for (int i : edges) w[i] = 1;

    res = ask(w);

    dep = (res - onlyA) / (B - A);
    if (dep != 0) {
        vec.clear();
        dfs2(V[ind], V[ind], 0);

        l = 0, r = vec.size() - 1;
        while (l <= r){
            int mid = (l + r) >> 1;
            fill(all(w), 0);
            for (int i = 0; i <= mid; i++) w[vec[i].first] = 1;

            res = ask(w);
            if (res != onlyA){
                T = vec[mid].second;
                r = mid - 1;
            } else l = mid + 1;
        }
    } else T = V[ind];

    answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:127:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for (int i = 0; i < g[U[ind]].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~
highway.cpp:130:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for (int i = 0; i < g[V[ind]].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~

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