답안 #139375

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
139375 2019-07-31T15:28:56 Z fredbr 통행료 (IOI18_highway) C++17
18 / 100
384 ms 262148 KB
#include "highway.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int const maxn = 90909;

struct Edge {
    int u, id;
};

vector<Edge> v[maxn];

vector<int> order;
vector<int> vt;

void dfs(int x, int p) {
    for (Edge e : v[x]) {
        if (e.u == p) continue;
        order.push_back(e.id);
        vt.push_back(x);
        dfs(e.u, x);
        vt.push_back(e.u);
        order.push_back(e.id);
    }
}

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

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

    dfs(0, 0);

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

    int l = 0, r = order.size();

    while (r-l > 1) {
        int mid = (l+r)/2;

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

        ll cost = ask(q);

        if (cost == total_cost) l = mid;
        else r = mid;
    }

    int old_l = l;

    l = 0, r = (int)order.size();

    while (r-l > 1) {
        int mid = (l+r)/2;

        vector<int> q(m);
        for (int i = mid; i < (int)order.size(); i++)
            q[order[i]]++;

        for (int& i : q) {
            if (i == 2) i = 1;
            else i = 0;
        }

        ll cost = ask(q);

        if (cost == total_cost) r = mid;
        else l = mid;
    }

    r = l;
    l = old_l;

    // for (int i : order) cout << i << " ";
    // cout << "\n";

    // cout << l << " " << r << "\n";
    vector<int> cnt(n);

    for (int i = l; i <= r; i++) {
        cnt[U[order[i]]]++;
        cnt[V[order[i]]]++;
    }

    a = -1, b = -1;

    for (int i = 0; i < n; i++) {
        if (cnt[i] == 1) {
            if (i != U[order[l]] and i != V[order[l]] and
                i != U[order[r]] and i != V[order[r]]) continue;

            if (a == -1) a = i;
            else b= i;
        }
    }

    // cout << vt[l] <<" " << vt[r] << "\n";
    // cout << a << " " << b << "\n";

    if (a > b) swap(a, b);
    answer(a, b);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 5 ms 2424 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 5 ms 2424 KB Output is correct
5 Correct 4 ms 2428 KB Output is correct
6 Correct 4 ms 2428 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2424 KB Output is correct
10 Correct 4 ms 2428 KB Output is correct
11 Correct 4 ms 2424 KB Output is correct
12 Correct 4 ms 2424 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2424 KB Output is correct
2 Correct 20 ms 3164 KB Output is correct
3 Correct 178 ms 9024 KB Output is correct
4 Correct 238 ms 9124 KB Output is correct
5 Correct 205 ms 9348 KB Output is correct
6 Correct 195 ms 9008 KB Output is correct
7 Correct 209 ms 9024 KB Output is correct
8 Correct 174 ms 9264 KB Output is correct
9 Correct 192 ms 9028 KB Output is correct
10 Correct 222 ms 9028 KB Output is correct
11 Correct 219 ms 10280 KB Output is correct
12 Correct 222 ms 11136 KB Output is correct
13 Correct 212 ms 10308 KB Output is correct
14 Correct 203 ms 9640 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 3904 KB Output is correct
2 Correct 29 ms 5452 KB Output is correct
3 Correct 55 ms 6828 KB Output is correct
4 Correct 183 ms 15504 KB Output is correct
5 Correct 182 ms 15524 KB Output is correct
6 Correct 181 ms 15500 KB Output is correct
7 Correct 205 ms 15528 KB Output is correct
8 Correct 153 ms 15504 KB Output is correct
9 Correct 164 ms 15580 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2424 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 384 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 361 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -