Submission #609605

#	Time	Username	Problem	Language	Result	Execution time	Memory
609605		MohamedAliSaidane	Highway Tolls (IOI18_highway)	C++14	18 / 100	174 ms	29272 KiB

highway

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

    using namespace std;

    typedef long long ll;

    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;

    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pii> vpi;
    typedef vector<pll> vpl;

    #define pb push_back
    #define popb pop_back
    #define all(x) (x).begin(),(x).end()

    #define ff first
    #define ss second

    const int nax = 9e4 + 4;
    vpi adj[nax];
    int n, m, a, b;
    int d[nax];
    vi cor[nax];
    int top[nax], sp[nax][20], tin[nax], tout[nax];
    int max_d = 1;
    int cureul = -1;

/*
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B);

long long ask(const std::vector<int> &w);
void answer(int s, int t);
*/
    void dfs(int x, int p = 0)
    {
        sp[x][0] = p;
        d[x] = d[p]  + 1;
        tin[x] = ++cureul;
        max_d = max(max_d, d[x]);
        cor[d[x]].pb(x);
        for(auto e: adj[x])
        {
            if(e.ff  != p)
            {
                top[e.ff] = e.ss;
                dfs(e.ff,x);
            }
        }
        tout[x] = cureul;
    }
    bool check_sub(int a, int b)
    {
        if(tin[a] >= tin[b] && tin[a] <= tout[b])
            return true;
        else
            return false;
    }
    void find_pair(int N, vi U, vi V, int A, int B)
    {
        n = N;
        m = U.size();
        for(int i = 0 ;  i < m; i++)
        {
            adj[U[i]].pb({V[i], i });
            adj[V[i]].pb({U[i], i });
        }
        dfs(0);
        int debut = 2;
        int fin = max_d;
        vi w(m, 0);
        ll norm = ask(w);
        int d_t = 2;
        while(debut <= fin )
        {
            int mid = (debut + fin)/2;
            w.assign(m, 0);
            for(int i = mid; i <= max_d; i ++)
            {
                for(auto e: cor[i])
                    w[top[e]] = 1;
            }
            ll cb =ask(w);
            if(cb > norm)
            {
                d_t = mid;
                debut = mid +1 ;
            }
            else
                fin = mid - 1;
        }
        debut  = 0;
        fin = (int)(cor[d_t].size()) - 1;
        int t_idx = 0;
        while(debut <= fin)
        {
            int mid = (debut + fin)/2;
            w.assign(m, 0);
            for(int i = 0; i <= mid; i ++)
                w[top[cor[d_t][i]]] = 1;
            ll cb = ask(w);
            if(cb > norm)
            {
                t_idx = mid;
                fin = mid - 1;
            }
            else
                debut = mid + 1;
        }
        w.assign(m, 0);
        int t = cor[d_t][t_idx];
        int cur = t;
        while(cur != 0)
        {
            w[top[cur]] = 1;
            cur=  sp[cur][0];
        }
        ll a= A;
        ll b= B;
        ll delt = 1ll * (ask(w) - norm);
        delt /= (ll)(b - a);
        int lca =t;
        int avlast = t;
        for(int i = 0; i < delt;  i ++)
        {
            avlast=  lca;
            lca= sp[lca][0];
        }
        for(int i=  1; i <= max_d; i++)
        {
            cor[i].clear();
        }
        for(int i  = 0 ; i < n; i++)
        {
            if(check_sub(i, lca))
            {
                if(!check_sub(i, avlast))
                {
                    cor[d[i]].pb(i);
                }
            }
        }
        int d_s = d[lca];
        debut = d[lca] + 1;
        fin = max_d;
        while(debut <= fin)
        {
            int mid= (debut + fin)/2;
            w.assign(m, 0);
            for(int i = mid; i<= fin; i ++)
                for(auto e: cor[i])
                    w[top[e]] = 1;
            ll cb = ask(w);
            if(cb > norm)
            {
                d_s = mid;
                debut = mid + 1;
            }
            else
                fin = mid - 1;
        }
        int s_idx = 0;
        debut = 0 ;
        fin = (int)(cor[d_s].size()) - 1;
        while(debut <= fin)
        {
            int mid=  (debut + fin)/2;
            w.assign(m, 0);
            for(int i = debut ; i <= mid; i ++)
                w[top[cor[d_s][i]]] = 1;
            ll cb  = ask(w);
            if(cb > norm)
            {
                s_idx = mid;
                fin = mid - 1;
            }
            else
                debut = mid + 1;
        }
        int s= cor[d_s][s_idx];
        answer(s,t);

    }

/*
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;
}
/*
12 11 5 9 1 11
0 1
1 2
1 3
2 7
3 9
3 8
0 6
0 4
0 5
4 11
6 10
*/

Compilation message (stderr)

highway.cpp:316:1: warning: "/*" within comment [-Wcomment]
  316 | /*
      |

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