Submission #566490

#	Time	Username	Problem	Language	Result	Execution time	Memory
566490		hoanghq2004	Highway Tolls (IOI18_highway)	C++14	51 / 100	199 ms	18696 KiB

highway

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "highway.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

//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;
//}

void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
    vector <vector <pair <int, int>>> g(n), e(n);
    vector <int> ord(n), id(n, -1);
    int m = U.size();
    for (int i = 0; i < m; ++i) {
        g[U[i]].push_back({V[i], i});
        g[V[i]].push_back({U[i], i});
//        cout << U[i] << ' ' << V[i] << "asdsdfsdf\n";
    }
    int L = 0, R = m - 1;
    vector <int> w(m, 0);
    long long tot = ask(w);
    while (L < R) {
        int mid = L + R >> 1;
        vector <int> w(m, 0);
        for (int i = mid + 1; i < m; ++i) w[i] = 1;
        if (ask(w) != tot) L = mid + 1;
        else R = mid;
    }
    int x = L;
    queue <int> q;
    q.push(U[x]);
    q.push(V[x]);
    vector <int> type(n, -1);
    type[U[x]] = 0;
    type[V[x]] = 1;
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (auto [v, i]: g[u]) {
            if (type[v] != -1) continue;
            type[v] = type[u];
            e[u].push_back({v, i});
            q.push(v);
        }
    }
//    cout << x << '\n';
    int ti = 0;
    function <void(int)> dfs = [&](int u) {
        ord[ti++] = u;
        for (auto [v, i]: e[u]) {
            id[v] = i;
            dfs(v);
        }
    };
//    cout << x << '\n';
    dfs(U[x]);
//    cout << U[x] << ' ' << V[x] << "aa\n";
//    for (int i = 0; i < ti; ++i) cout << ord[i] << ' ';
//    cout << '\n';
    w.assign(m, -1);
//    cout << id[0] << "aaa\n";
//    for (int i = 0; i < n; ++i) cout << type[i] << ' ';
//    cout << '\n';
    for (int i = 0; i < n; ++i) {
        if (i == U[x] || i == V[x]) continue;
        if (type[i] == 0) w[id[i]] = 0;
    }
    w[x] = 0;
    for (int i = 0; i < m; ++i) if (w[i] == -1) w[i] = 1;
    tot = ask(w);
//    cout << tot << "aafcdsfsdgf\n";
    L = 0, R = ti - 1;
    while (L < R) {
        int mid = L + R >> 1;
        vector <int> w(m, -1);
        for (int i = 0; i <= mid; ++i) {
            if (ord[i] == U[x] || ord[i] == V[x]) continue;
            if (type[ord[i]] == 0) w[id[ord[i]]] = 0;
        }
        w[x] = 0;
        for (int i = 0; i < m; ++i) if (w[i] == -1) w[i] = 1;
        if (ask(w) == tot) R = mid;
        else L = mid + 1;
    }
    int S = ord[L];
    ti = 0;
    dfs(V[x]);
//    for (int i = 0; i < ti; ++i) cout << ord[i] << ' ';
//    cout << '\n';
    w.assign(m, -1);
    for (int i = 0; i < n; ++i) {
        if (i == U[x] || i == V[x]) continue;
        if (type[i] == 1) w[id[i]] = 0;
    }
    w[x] = 0;
    for (int i = 0; i < m; ++i) if (w[i] == -1) w[i] = 1;
    tot = ask(w);
//    for (int i = 0; i < ti; ++i) cout << ord[i] << ' ';
//    cout << '\n';
    L = 0, R = ti - 1;
    while (L < R) {
        int mid = L + R >> 1;
        vector <int> w(m, -1);
        for (int i = 0; i <= mid; ++i) {
            if (ord[i] == U[x] || ord[i] == V[x]) continue;
            if (type[ord[i]] == 1) w[id[ord[i]]] = 0;
        }
        w[x] = 0;
        for (int i = 0; i < m; ++i) if (w[i] == -1) w[i] = 1;
        if (ask(w) == tot) R = mid;
        else L = mid + 1;
    }
    int T = ord[L];
//    cout << S << ' ' << T << '\n';
    answer(S, T);
}
/*
11 11 1 2 1 8
0 1
0 2
1 3
1 4
4 5
4 6
2 7
2 8
8 9
8 10
1 10
*/
//int main() {
//    freopen("IOI18_highway.inp", "r", stdin);
//    freopen("IOI18_highway.out", "w", stdout);
//  N = read_int();
//  M = read_int();
//  A = read_int();
//  B = read_int();
//  S = read_int();
//  T = read_int();
////  cout << S << ' ' << T << '\n';
////  cout << (S ^ T) << '\n';
//  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) {
////      cerr << N << ' ' << M << ' ' << A << ' ' << B << ' ' << S << ' ' << T << '\n';
////      for (int i = 0; i < M; ++i) cerr << U[i] << ' ' << V[i] << '\n';
//      assert(0);
//    wrong_answer("{s, t} is wrong");
//  }
//  printf("Accepted: %d\n", num_calls);
//  return 0;
//}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:124:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  124 |         int mid = L + R >> 1;
      |                   ~~^~~
highway.cpp:140:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |         for (auto [v, i]: g[u]) {
      |                   ^
highway.cpp: In lambda function:
highway.cpp:151:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  151 |         for (auto [v, i]: e[u]) {
      |                   ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:175:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  175 |         int mid = L + R >> 1;
      |                   ~~^~~
highway.cpp:203:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  203 |         int mid = L + R >> 1;
      |                   ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31