oj.uz

Submission #609624

# Submission time Handle Problem Language Result Execution time Memory
609624 2022-07-27T18:26:05 Z MohamedAliSaidane Highway Tolls (IOI18_highway) C++14
51 / 100
 179 ms 29304 KB 
#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];
        }
        ll edges = norm/a;
        edges -= d[t] - d[lca];
        int d_s = d[lca] + edges;
        if(d_s == d[lca])
        {
            answer(t, lca);
            return ;
        }
        vi rem;
        for(int i=  0 ; i < n;i ++)
        {
            if(d[i] == d_s)
            {
                if(!check_sub(i, avlast))
                    rem.pb(i);
            }
        }
        if(rem.empty())
        {
            d[-1] += d[-3809];
        }
        debut = 0;
        fin = (int)(rem.size()) - 1;
        int idx = 0;
        while(debut <= fin)
        {
            int mid = (debut + fin)/2;
            w.assign(m, 0);
            for(int i = debut; i <= mid; i++)
                w[top[rem[i]]] = 1;
            if(ask(w) > norm)
            {
                idx = mid;
                fin = mid - 1;
            }
            else
                debut = mid + 1;
        }
        int s = rem[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

highway.cpp:303:1: warning: "/*" within comment [-Wcomment]
  303 | /*
      |  
highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:151:19: warning: array subscript -1 is below array bounds of 'int [90004]' [-Warray-bounds]
  151 |             d[-1] += d[-3809];
      |             ~~~~~~^~~~~~~~~~~
highway.cpp:151:29: warning: array subscript -3809 is below array bounds of 'int [90004]' [-Warray-bounds]
  151 |             d[-1] += d[-3809];
      |                      ~~~~~~~^
highway.cpp:151:19: warning: array subscript -1 is below array bounds of 'int [90004]' [-Warray-bounds]
  151 |             d[-1] += d[-3809];
      |             ~~~~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4560 KB Output is correct
2 Correct 2 ms 4560 KB Output is correct
3 Correct 3 ms 4560 KB Output is correct
4 Correct 3 ms 4560 KB Output is correct
5 Correct 3 ms 4560 KB Output is correct
6 Correct 2 ms 4560 KB Output is correct
7 Correct 2 ms 4560 KB Output is correct
8 Correct 2 ms 4560 KB Output is correct
9 Correct 3 ms 4560 KB Output is correct
10 Correct 2 ms 4560 KB Output is correct
11 Correct 2 ms 4560 KB Output is correct
12 Correct 3 ms 4560 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4688 KB Output is correct
2 Correct 14 ms 6020 KB Output is correct
3 Correct 111 ms 18640 KB Output is correct
4 Correct 140 ms 18700 KB Output is correct
5 Correct 102 ms 18696 KB Output is correct
6 Correct 133 ms 18620 KB Output is correct
7 Correct 148 ms 18656 KB Output is correct
8 Correct 104 ms 18712 KB Output is correct
9 Correct 149 ms 18676 KB Output is correct
10 Correct 109 ms 18636 KB Output is correct
11 Correct 134 ms 19796 KB Output is correct
12 Correct 152 ms 20676 KB Output is correct
13 Correct 130 ms 19988 KB Output is correct
14 Correct 112 ms 19296 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6920 KB Output is correct
2 Correct 24 ms 9412 KB Output is correct
3 Correct 28 ms 11692 KB Output is correct
4 Correct 99 ms 26008 KB Output is correct
5 Correct 138 ms 26016 KB Output is correct
6 Correct 133 ms 26016 KB Output is correct
7 Correct 92 ms 26000 KB Output is correct
8 Correct 94 ms 26012 KB Output is correct
9 Correct 95 ms 26012 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4688 KB Output is correct
2 Correct 18 ms 6020 KB Output is correct
3 Correct 84 ms 15604 KB Output is correct
4 Correct 155 ms 18620 KB Output is correct
5 Correct 98 ms 18668 KB Output is correct
6 Correct 139 ms 18692 KB Output is correct
7 Correct 110 ms 18644 KB Output is correct
8 Correct 124 ms 18684 KB Output is correct
9 Correct 127 ms 18684 KB Output is correct
10 Correct 161 ms 18744 KB Output is correct
11 Correct 121 ms 19168 KB Output is correct
12 Correct 179 ms 20804 KB Output is correct
13 Correct 160 ms 20088 KB Output is correct
14 Correct 128 ms 20640 KB Output is correct
15 Correct 115 ms 18724 KB Output is correct
16 Correct 106 ms 18644 KB Output is correct
17 Correct 159 ms 20428 KB Output is correct
18 Correct 163 ms 19760 KB Output is correct
19 Correct 108 ms 18612 KB Output is correct
20 Correct 151 ms 21300 KB Output is correct
21 Correct 115 ms 19524 KB Output is correct
22 Correct 170 ms 19512 KB Output is correct
23 Correct 113 ms 19180 KB Output is correct
24 Correct 157 ms 19932 KB Output is correct
25 Correct 170 ms 24816 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 29304 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 28804 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -