제출 #434556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434556		dxz05	통행료 (IOI18_highway)	C++14	6 / 100	195 ms	59216 KiB

highway

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

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 3e2;

vector<int> g[MAXN];
int p[MAXN], d[MAXN];
vector<int> vec[MAXN];
int edgeID[MAXN];

void dfs(int v, int par, int dep){
    p[v] = par;
    d[v] = dep;
    vec[dep].push_back(v);

    for (int u : g[v]){
        if (u != par) dfs(u, v, dep + 1);
    }
}

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

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

    dfs(0, -1, 0);

    ll onlyA = ask(w);

    int S = 0, T = 0;

    int l = 0, r = N - 1;
    while (l <= r){
        int m = (l + r) >> 1;
        for (int i = 0; i < M; i++){
            w[i] = (i < m);
        }

        ll res = ask(w);

        if (res == onlyA){
            S = m;
            l = m + 1;
        } else r = m - 1;

    }

    l = S, r = N - 1;
    while (l <= r){
        int m = (l + r) >> 1;
        for (int i = 0; i < M; i++){
            w[i] = (i >= m);
        }

        ll res = ask(w);

        if (res == onlyA){
            T = m;
            r = m - 1;
        } else l = m + 1;

    }

    answer(S, T);
}
/**
12 11 3 5 0 9
0 1
0 2
1 3
1 4
4 5
2 6
2 7
2 8
7 9
7 10
9 11

5 4 3 5 1 3
0 1
1 2
2 3
3 4

*/

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