oj.uz

Submission #1068251

# Submission time Handle Problem Language Result Execution time Memory
1068251 2024-08-21T08:51:21 Z Ignut Highway Tolls (IOI18_highway) C++17
51 / 100
 450 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 + 1) / 2;
        w.assign(M, 0);
        for (int i = 0; i < M; i ++) {
            int d = max(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)
            lo = mid;
        else
            hi = mid - 1;
    }
    int dv = lo + (dist - (du - 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 2904 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2904 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 2904 KB Output is correct
7 Correct 1 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 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2904 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 8 ms 3652 KB Output is correct
3 Correct 82 ms 7928 KB Output is correct
4 Correct 75 ms 8032 KB Output is correct
5 Correct 73 ms 8040 KB Output is correct
6 Correct 83 ms 7924 KB Output is correct
7 Correct 70 ms 7936 KB Output is correct
8 Correct 74 ms 8052 KB Output is correct
9 Correct 64 ms 7928 KB Output is correct
10 Correct 74 ms 7932 KB Output is correct
11 Correct 86 ms 8864 KB Output is correct
12 Correct 87 ms 9480 KB Output is correct
13 Correct 88 ms 9388 KB Output is correct
14 Correct 87 ms 8716 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3928 KB Output is correct
2 Correct 15 ms 4668 KB Output is correct
3 Correct 27 ms 5580 KB Output is correct
4 Correct 72 ms 12056 KB Output is correct
5 Correct 76 ms 12056 KB Output is correct
6 Correct 88 ms 11860 KB Output is correct
7 Correct 67 ms 12116 KB Output is correct
8 Correct 77 ms 12112 KB Output is correct
9 Correct 65 ms 12288 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 9 ms 3144 KB Output is correct
3 Correct 78 ms 6796 KB Output is correct
4 Correct 120 ms 8028 KB Output is correct
5 Correct 84 ms 8064 KB Output is correct
6 Correct 120 ms 8136 KB Output is correct
7 Correct 87 ms 8012 KB Output is correct
8 Correct 141 ms 8148 KB Output is correct
9 Correct 115 ms 8388 KB Output is correct
10 Correct 119 ms 8176 KB Output is correct
11 Correct 98 ms 8456 KB Output is correct
12 Correct 105 ms 9368 KB Output is correct
13 Correct 95 ms 9012 KB Output is correct
14 Correct 99 ms 9324 KB Output is correct
15 Correct 97 ms 8016 KB Output is correct
16 Correct 75 ms 8076 KB Output is correct
17 Correct 97 ms 9124 KB Output is correct
18 Correct 90 ms 8836 KB Output is correct
19 Correct 109 ms 7996 KB Output is correct
20 Correct 106 ms 9684 KB Output is correct
21 Correct 420 ms 10204 KB Output is correct
22 Correct 450 ms 10216 KB Output is correct
23 Correct 312 ms 9328 KB Output is correct
24 Correct 268 ms 9596 KB Output is correct
25 Correct 114 ms 11652 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 249 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 226 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -