답안 #1068191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1068191	2024-08-21T08:24:12 Z	Ignut	통행료 (IOI18_highway)	C++17	18 / 100	222 ms	262144 KB

highway

// Ignut

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

using namespace std;
using ll = long long;

// ll ask(vector<int> w);

// void answer(int s, int t);

const int MAXN = 9e4 + 123;
int n;

vector<int> tree[MAXN];
int depth[MAXN];
int parent[MAXN];

int maxDepth = 0;

void dfs(int v, int par, int d) {
    depth[v] = d;
    parent[v] = par;
    maxDepth = max(maxDepth, d);
    for (int to : tree[v])
        if (to != par)
            dfs(to, v, d + 1);
}

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 ++) {
        tree[U[i]].push_back(V[i]);
        tree[V[i]].push_back(U[i]);
    }
    dfs(0, -1, 0);

    vector<int> w(M, 0);
    ll da = ask(w);
    int dist = ask(w) / (1ll * A);
    // bigger depth -- u
    int lo = 0, hi = maxDepth;
    int lo2 = 0;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        w.assign(M, 0);
        for (int i = 0; i < M; i ++) {
            int d = min(depth[U[i]], depth[V[i]]);
            if (d >= mid)
                w[i] = true;
        }
        ll val = ask(w);
        if (val == 1ll * dist * B)
            lo2 = max(lo2, mid);

        if (val == da)
            hi = mid;
        else
            lo = mid + 1;
    }
    int du = lo;
    // smaller depth -- v
    lo = lo2, hi = du;
    // cerr << "from " << lo << " to " << hi << '\n';
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        w.assign(M, 0);
        for (int i = 0; i < M; i ++) {
            int d = min(depth[U[i]], depth[V[i]]);
            if (d >= mid)
                w[i] = true;
        }
        ll val = ask(w);
        // cerr << mid << " : " << val << " vs " << da + 1ll * (du - mid) * (B - A) << '\n';
        if (val == da + 1ll * (du - mid) * (B - A))
            hi = mid;
        else
            lo = mid + 1;
    }
    int dv = lo;

    // ========================================================== //

    // findind u (lower point)
    vector<int> eu;
    for (int i = 0; i < M; i ++) {
        int d = max(depth[U[i]], depth[V[i]]);
        if (d == du)
            eu.push_back(i);
    }
    int hi2 = n - 1;
    lo = 0, hi = eu.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        w.assign(M, 0);
        for (int i = 0; i <= mid; i ++)
            w[eu[i]] = true;
        ll val = ask(w);
        if (val == da - 2 * A + 2 * B)
            hi2 = min(hi2, mid);
        // cerr << mid << " : " << val << " vs " << da << '\n';
        // for (int val : w) cerr << val;
        // cerr << '\n';
        if (val > da)
            hi = mid;
        else
            lo = mid + 1;
    }
    int u;
    if (depth[U[eu[lo]]] == du) u = U[eu[lo]];
    else u = V[eu[lo]];
    // for (int ind : eu) {
    //     cerr << U[ind] << " -> " << V[ind] << '\n';
    // }
    // cerr << "U = " << u << "(" << lo << ")\n";

    // cerr << du << ' ' << dv << ' ' << dist << '\n';

    int bad = u;
    while (depth[bad] > dv) bad = parent[bad];

    // finding v
    int v;
    if (du - dv == dist) {
        // just vertical
        // look down
        vector<int> ev;
        for (int i = 0; i < M; i ++) {
            int d = min(depth[U[i]], depth[V[i]]);
            if (d == dv)
                ev.push_back(i);
        }
        lo = 0, hi = ev.size() - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            w.assign(M, 0);
            for (int i = 0; i <= mid; i ++)
                w[ev[i]] = true;
            ll val = ask(w);
            if (val > da)
                hi = mid;
            else
                lo = mid + 1;
        }
        if (depth[U[ev[lo]]] == dv) v = U[ev[lo]];
        else v = V[ev[lo]];
    }
    else {
        // normal path (lca != u and lca != v)
        vector<int> ev;
        for (int i = 0; i < M; i ++) {
            int d = max(depth[U[i]], depth[V[i]]);
            if (U[i] == bad || V[i] == bad) continue;
            if (d == dv)
                ev.push_back(i);
        }
        lo = 0, hi = ev.size() - 1;
        ll needVal = da;
        if (du == dv) {
            hi = min(int(ev.size()) - 1, hi2);
            needVal = needVal - A + B;
        }
        // cerr << lo << " -- " << hi << '\n';
        // answer(-1, -1); return;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            w.assign(M, 0);
            for (int i = 0; i <= mid; i ++)
                w[ev[i]] = true;
            ll val = ask(w);
            if (val > needVal)
                hi = mid;
            else
                lo = mid + 1;
        }
        if (depth[U[ev[lo]]] == dv) v = U[ev[lo]];
        else v = V[ev[lo]];
        // for (int ind : ev) {
        //     cerr << U[ind] << " -> " << V[ind] << '\n';
        // }
        // cerr << "V = " << v << "(" << lo << ")\n";
    }

    answer(u, v);
    return;
}

/*
4, [0, 0, 0, 1], [1, 2, 3, 2], 1, 3)
4 4 1 3 1 3
0 1
0 2
0 3
1 2

N M  A B  S T

tree:
4 3  1 2  3 2
0 1
0 2
1 3
*/


// namespace {

// constexpr int MAX_NUM_CALLS = 100;
// constexpr long long INF = 1LL << 61;

// int N, M, A, B, S, T;
// std::vector<int> U, V;
// std::vector<std::vector<std::pair<int, int>>> graph;

// bool answered, wrong_pair;
// int num_calls;

// int read_int() {
//   int x;
//   if (scanf("%d", &x) != 1) {
//     fprintf(stderr, "Error while reading input\n");
//     exit(1);
//   }
//   return x;
// }

// void wrong_answer(const char *MSG) {
//   printf("Wrong Answer: %s\n", MSG);
//   exit(0);
// }

// }  // namespace

// long long ask(const std::vector<int> &w) {
//   if (++num_calls > MAX_NUM_CALLS) {
//     wrong_answer("more than 100 calls to ask");
//   }
//   if (w.size() != (size_t)M) {
//     wrong_answer("w is invalid");
//   }
//   for (size_t i = 0; i < w.size(); ++i) {
//     if (!(w[i] == 0 || w[i] == 1)) {
//       wrong_answer("w is invalid");
//     }
//   }

//   std::vector<bool> visited(N, false);
//   std::vector<long long> current_dist(N, INF);
//   std::queue<int> qa, qb;
//   qa.push(S);
//   current_dist[S] = 0;
//   while (!qa.empty() || !qb.empty()) {
//     int v;
//     if (qb.empty() ||
//         (!qa.empty() && current_dist[qa.front()] <= current_dist[qb.front()])) {
//       v = qa.front();
//       qa.pop();
//     } else {
//       v = qb.front();
//       qb.pop();
//     }
//     if (visited[v]) {
//       continue;
//     }
//     visited[v] = true;
//     long long d = current_dist[v];
//     if (v == T) {
//       return d;
//     }
//     for (auto e : graph[v]) {
//       int vv = e.first;
//       int ei = e.second;
//       if (!visited[vv]) {
//         if (w[ei] == 0) {
//           if (current_dist[vv] > d + A) {
//             current_dist[vv] = d + A;
//             qa.push(vv);
//           }
//         } else {
//           if (current_dist[vv] > d + B) {
//             current_dist[vv] = d + B;
//             qb.push(vv);
//           }
//         }
//       }
//     }
//   }
//   return -1;
// }

// void answer(int s, int t) {
//   if (answered) {
//     wrong_answer("answered not exactly once");
//   }

//   if (!((s == S && t == T) || (s == T && t == S))) {
//     wrong_pair = true;
//   }

//   answered = true;
// }

// int main() {
//   N = read_int();
//   M = read_int();
//   A = read_int();
//   B = read_int();
//   S = read_int();
//   T = read_int();
//   U.resize(M);
//   V.resize(M);
//   graph.assign(N, std::vector<std::pair<int, int>>());
//   for (int i = 0; i < M; ++i) {
//     U[i] = read_int();
//     V[i] = read_int();
//     graph[U[i]].push_back({V[i], i});
//     graph[V[i]].push_back({U[i], i});
//   }

//   answered = false;
//   wrong_pair = false;
//   num_calls = 0;
//   find_pair(N, U, V, A, B);
//   if (!answered) {
//     wrong_answer("answered not exactly once");
//   }
//   if (wrong_pair) {
//     wrong_answer("{s, t} is wrong");
//   }
//   printf("Accepted: %d\n", num_calls);
//   return 0;
// }

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2392 KB	Output is correct
2	Correct	8 ms	3404 KB	Output is correct
3	Correct	75 ms	8036 KB	Output is correct
4	Correct	73 ms	8132 KB	Output is correct
5	Correct	83 ms	8040 KB	Output is correct
6	Correct	72 ms	7956 KB	Output is correct
7	Correct	66 ms	8472 KB	Output is correct
8	Correct	73 ms	8044 KB	Output is correct
9	Correct	75 ms	7948 KB	Output is correct
10	Correct	71 ms	7932 KB	Output is correct
11	Correct	87 ms	8852 KB	Output is correct
12	Correct	109 ms	9348 KB	Output is correct
13	Correct	88 ms	8952 KB	Output is correct
14	Correct	81 ms	8532 KB	Output is correct

Subtask #3
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	3416 KB	Output is correct
2	Correct	15 ms	4644 KB	Output is correct
3	Correct	27 ms	5720 KB	Output is correct
4	Correct	87 ms	12280 KB	Output is correct
5	Correct	64 ms	12048 KB	Output is correct
6	Correct	62 ms	12060 KB	Output is correct
7	Correct	66 ms	11948 KB	Output is correct
8	Correct	71 ms	12516 KB	Output is correct
9	Correct	78 ms	12064 KB	Output is correct