oj.uz

Submission #1068241

# Submission time Handle Problem Language Result Execution time Memory
1068241 2024-08-21T08:48:14 Z Ignut Highway Tolls (IOI18_highway) C++17
18 / 100
 426 ms 262144 KB 
// 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;
    // cerr << "hi2 = " << hi2 << '\n';
    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 << "hi2 min= " << mid << '\n';
        }
        // 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
        // cerr << "VERTICAL\n";
        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;
        }
        needVal = da;
        // cerr << needVal << '\n';
        // cerr << lo << " -- " << hi << '\n';
        // cout << "hi2 = " << hi2 << '\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);
            // cerr << mid << " ::: " << val << ' ' << needVal << '\n';
            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";
    }

    cerr << "DEPTH[18] = " << depth[18] << '\n';

    // cerr << "DEPTH[18] = " << depth[56] << '\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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2340 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 2 ms 2392 KB Output is correct
5 Correct 1 ms 2904 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 1 ms 2392 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct
11 Correct 2 ms 2392 KB Output is correct
12 Correct 2 ms 2392 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 10 ms 3160 KB Output is correct
3 Correct 87 ms 8288 KB Output is correct
4 Correct 89 ms 7968 KB Output is correct
5 Correct 90 ms 8044 KB Output is correct
6 Correct 73 ms 8160 KB Output is correct
7 Correct 80 ms 8000 KB Output is correct
8 Correct 90 ms 8272 KB Output is correct
9 Correct 84 ms 7924 KB Output is correct
10 Correct 99 ms 7940 KB Output is correct
11 Correct 91 ms 8852 KB Output is correct
12 Correct 109 ms 9296 KB Output is correct
13 Correct 89 ms 8960 KB Output is correct
14 Correct 89 ms 8552 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3416 KB Output is correct
2 Correct 18 ms 4644 KB Output is correct
3 Correct 22 ms 6112 KB Output is correct
4 Correct 100 ms 12052 KB Output is correct
5 Correct 61 ms 12060 KB Output is correct
6 Correct 85 ms 12052 KB Output is correct
7 Correct 91 ms 11948 KB Output is correct
8 Correct 69 ms 12064 KB Output is correct
9 Correct 77 ms 12052 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2904 KB Output is correct
2 Correct 9 ms 3160 KB Output is correct
3 Correct 88 ms 6908 KB Output is correct
4 Correct 118 ms 8092 KB Output is correct
5 Correct 106 ms 8056 KB Output is correct
6 Correct 151 ms 8232 KB Output is correct
7 Correct 82 ms 7940 KB Output is correct
8 Correct 131 ms 8272 KB Output is correct
9 Correct 122 ms 8112 KB Output is correct
10 Correct 165 ms 8080 KB Output is correct
11 Correct 101 ms 8452 KB Output is correct
12 Correct 102 ms 9544 KB Output is correct
13 Correct 104 ms 9020 KB Output is correct
14 Correct 98 ms 9332 KB Output is correct
15 Correct 96 ms 8024 KB Output is correct
16 Correct 94 ms 8076 KB Output is correct
17 Correct 94 ms 9124 KB Output is correct
18 Correct 112 ms 8844 KB Output is correct
19 Correct 84 ms 7996 KB Output is correct
20 Correct 84 ms 9680 KB Output is correct
21 Correct 426 ms 10344 KB Output is correct
22 Correct 417 ms 10352 KB Output is correct
23 Correct 313 ms 9324 KB Output is correct
24 Correct 273 ms 9452 KB Output is correct
25 Incorrect 121 ms 11488 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 240 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 234 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -