Submission #283062

#	Time	Username	Problem	Language	Result	Execution time	Memory
283062		Mercenary	Highway Tolls (IOI18_highway)	C++14	51 / 100	297 ms	11368 KiB

highway

#include "highway.h"

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 90000 + 5;
const int logn = log2(maxn) + 1;

int n , m;
vector<ii> adj[maxn];
int par[2][maxn];
int dis[2][maxn];

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n = N;m = U.size();
//    return;
    ll initial = ask(vector<int>(m , 0));
    int l = 0 , h = m - 1;
    while(l < h){
        int mid = l + h >> 1;
        vector<int> val(m , 0);
        for(int i = 0 ; i <= mid ; ++i)val[i] = 1;
        if(ask(val) > initial)h = mid;
        else l = mid + 1;
    }
    for(int i = 0 ; i < m ; ++i){
        adj[U[i]].pb(mp(V[i] , i));
        adj[V[i]].pb(mp(U[i] , i));
    }
    memset(par,-1,sizeof par);
    memset(dis,123,sizeof dis);
    auto bfs = [&](int dis[] , int par[] , int st){
        dis[st] = 0;queue<int> q;q.push(st);
        while(q.size()){
            auto u = q.front();q.pop();
            for(auto & c : adj[u]){
                if(dis[c.first] > dis[u] + 1){
                    dis[c.first] = dis[u] + 1;q.push(c.first);
                    par[c.first] = c.second;
                }
            }
        }
    };
    int u = U[l] , v = V[l];
    vector<int> valU , valV;
    bfs(dis[0] , par[0] , u);
    bfs(dis[1] , par[1] , v);
    for(int i = 0 ; i < n ; ++i){
        if(dis[0][i] < dis[1][i])valU.pb(i);
        else if(dis[0][i] > dis[1][i])valV.pb(i);
    }
//    cout << U[l] << " " << V[l] << endl;
    auto solve = [&](int & res , vector<int> & val , int dis[] , int par[]){
        sort(val.begin(),val.end(),[&](const int u , const int v){return dis[u] < dis[v];});
        int l = 0 , h = (int)val.size() - 1;
        while(l < h){
            int mid = l + h >> 1;
            vector<int> query(m , 0);
            for(int i = mid + 1 ; i < val.size() ; ++i){
                if(par[val[i]] != -1)query[par[val[i]]] = 1;
            }
            if(ask(query) > initial)l = mid + 1;
            else h = mid;
        }
//        cout << val.size() << " " << val[l] << endl;
        res = val[l];
    };
    solve(u , valU , dis[0] , par[0]);
    solve(v , valV , dis[1] , par[1]);
    answer(u,v);
}

#ifdef LOCAL
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#include "highway.h"

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() {
    freopen(taskname".INP","r",stdin);
  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;
}

#endif // LOCAL

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:33:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int mid = l + h >> 1;
      |                   ~~^~~
highway.cpp: In lambda function:
highway.cpp:70:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |             int mid = l + h >> 1;
      |                       ~~^~~
highway.cpp:72:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for(int i = mid + 1 ; i < val.size() ; ++i){
      |                                   ~~^~~~~~~~~~~~

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