oj.uz

답안 #775731

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
775731 2023-07-06T20:35:06 Z GusterGoose27 통행료 (IOI18_highway) C++17
5 / 100
 166 ms 262144 KB 
#include "highway.h"

#include <bits/stdc++.h>

const int MAXN = 9e4;

using namespace std;
typedef pair<int, int> pii;

vector<int> weight;
int n, m;
vector<pii> edges[MAXN];
int base;
bool vis[MAXN];
int sz[MAXN];
int a, b;

void make_sz(int cur, int p = -1) {
    sz[cur] = 1;
    for (pii e: edges[cur]) {
        int nxt = e.first;
        if (nxt == p || vis[nxt]) continue;
        make_sz(nxt, cur);
        sz[cur] += sz[nxt];
    }
}

vector<int> res;

void deactivate(int v) {
    for (pii e: edges[v]) weight[e.second] = 1;
}

void activate(int v) {
    for (pii e: edges[v]) weight[e.second] = 0;
}

int find(int cur, int dest, int p = -1) {
    for (pii e: edges[cur]) {
        if (e.first == p) continue;
        if (e.first == dest) return cur;
        int m = find(e.first, dest, cur);
        if (m != -1) return m;
    }
    return -1;
}

void set_sub(int cur, bool v, int p = -1) {
    if (v) deactivate(cur);
    else activate(cur);
    for (pii e: edges[cur]) {
        if (vis[e.first] || e.first == p) continue;
        set_sub(e.first, v, cur);
    }
}

void solve(int cur, int num = 2, int oth = -1) {
    if (num == 0) return;
    make_sz(cur);
    int tot = sz[cur];
    if (tot == 1) {
        // assert(num == 1);
        res.push_back(cur);
        vis[cur] = 1;
        return;
    }
    int p = -1;
    bool f = 0;
    while (!f) {
        f = 1;
        for (pii e: edges[cur]) {
            int nxt = e.first;
            if (vis[nxt] || nxt == p) continue;
            if (2*sz[nxt] >= tot) {
                f = 0;
                p = cur;
                cur = nxt;
                break;
            }
        }
    }
    vis[cur] = 1;
    deactivate(cur);
    int val = ask(weight);
    activate(cur);
    if (val == base+b-a) {
        res.push_back(cur);
        val = base;
        num--;
        oth = cur;
    }
    if (val == base) { // figure out which subtree
        vector<pii> adj;
        for (pii e: edges[cur]) {
            if (vis[e.first]) continue;
            adj.push_back(e);
        }
        int l = 0;
        int r = adj.size();
        assert(adj.size() >= 1);
        while (r > l+1) {
            int mid = (l+r)/2;
            for (int i = l; i < mid; i++) set_sub(adj[i].first, 1);
            if (ask(weight) > base) {
                r = mid;
            }
            else {
                l = mid;
            }
            for (int i = l; i < mid; i++) set_sub(adj[i].first, 0);
        }
        solve(adj[l].first, num, oth);
    }
    else {
        while (num > 0) {
            int ig_dir = -1;
            if (num == 1) ig_dir = find(oth, cur);
            vector<pii> adj;
            for (pii e: edges[cur]) {
                if (vis[e.first] || e.first == ig_dir) continue;
                adj.push_back(e);
            }
            int l = 0;
            int r = adj.size();
            assert(adj.size() >= num);
            while (r > l+1) {
                int mid = (l+r)/2;
                for (int i = l; i < mid; i++) weight[adj[i].second] = 1;
                if (ask(weight) > base) {
                    r = mid;
                }
                else {
                    l = mid;
                }
                for (int i = l; i < mid; i++) weight[adj[i].second] = 0;
            }
            solve(adj[l].first, 1, cur);
            num--;
            oth = res[0];
        }
    }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    a = A; b = B;
    // assert(U.size() == N-1);
    n = N;
    m = U.size();
    for (int i = 0; i < m; i++) {
        edges[U[i]].push_back(pii(V[i], i));
        edges[V[i]].push_back(pii(U[i], i));
    }
    weight = vector<int>(m);
    fill(weight.begin(), weight.end(), 0);
    base = ask(weight);
    solve(0);
    answer(res[0], res[1]);
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from highway.cpp:3:
highway.cpp: In function 'void solve(int, int, int)':
highway.cpp:125:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |             assert(adj.size() >= num);
      |                    ~~~~~~~~~~~^~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 2 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2328 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 1 ms 2384 KB Output is correct
12 Correct 1 ms 2384 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 9 ms 2976 KB Output is correct
3 Incorrect 164 ms 7956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 3664 KB Output is correct
2 Correct 23 ms 4988 KB Output is correct
3 Correct 36 ms 6400 KB Output is correct
4 Correct 75 ms 14428 KB Output is correct
5 Correct 84 ms 14392 KB Output is correct
6 Correct 95 ms 14420 KB Output is correct
7 Correct 101 ms 14412 KB Output is correct
8 Correct 77 ms 14408 KB Output is correct
9 Incorrect 102 ms 14404 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 11 ms 3000 KB Output is correct
3 Correct 60 ms 6708 KB Output is correct
4 Correct 138 ms 8136 KB Output is correct
5 Correct 106 ms 7928 KB Output is correct
6 Correct 123 ms 7972 KB Output is correct
7 Correct 94 ms 7932 KB Output is correct
8 Correct 94 ms 8012 KB Output is correct
9 Incorrect 99 ms 7908 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 166 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 146 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -