Submission #413514

#	Time	Username	Problem	Language	Result	Execution time	Memory
413514		usachevd0	Highway Tolls (IOI18_highway)	C++17	90 / 100	331 ms	11568 KiB

highway

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

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& x : v)
        stream << x << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}


const int INF32 = 0x3f3f3f3f;
const int maxN = 9e4 + 4;
vector<pii> G[maxN];
int col[maxN];

ll ask(const vector<int>& w);
void answer(int s, int t);
void find_pair(int n, vector<int> eu, vector<int> ev, int A, int B) {
    #ifdef LOCAL
        #define seed 228
    #else
        #define seed time(0)
    #endif
    mt19937 rng(time(0));
    uniform_real_distribution<double> dstrb(0.45, 0.55);
    const int MIN_RAND_SEP = 50;
    
    int m = eu.size();
    for (int v = 0; v < n; ++v)
        G[v].clear();
    for (int i = 0; i < m; ++i) {
        G[eu[i]].emplace_back(ev[i], i);
        G[ev[i]].emplace_back(eu[i], i);
    }
    for (int v = 0; v < n; ++v)
        shuffle(all(G[v]), rng);
    
    ll d0 = ask(vector<int>(m, 0));
    
    auto askCol = [&]() -> ll {
        vector<int> w(m, 0);
        for (int i = 0; i < m; ++i)
            if (!col[eu[i]] || !col[ev[i]])
                w[i] = 1;
        return ask(w);
    };
    
    vector<int> ordv(n);
    iota(all(ordv), 0);
    shuffle(all(ordv), rng);
    
    
    int vl = -1, vr = n - 1;
    while (vr - vl > 1) {
        int vm;
        if (vr - vl > MIN_RAND_SEP) {
            vm = vl + (vr - vl) * dstrb(rng) + 0.5;
        } else {
            vm = (vl + vr) / 2;
        }
        for (int i = 0; i <= vm; ++i)
            col[ordv[i]] = 0;
        for (int i = vm + 1; i < n; ++i)
            col[ordv[i]] = 1;
        if (askCol() == d0)
            vl = vm;
        else
            vr = vm;
    }
    
    int v0 = ordv[vr];
    static int qu[maxN], qt, dist[maxN], parv[maxN], pare[maxN];
    qu[0] = v0;
    fill(dist, dist + n, INF32);
    dist[v0] = 0;
    qt = 1;
    for (int qi = 0; qi < qt; ++qi) {
        int u = qu[qi];
        for (pii e : G[u]) {
            int v = e.fi, eidx = e.se;
            if (chkmin(dist[v], dist[u] + 1)) {
                pare[v] = eidx;
                parv[v] = u;
                qu[qt++] = v;
            }
        }
    }
    for (int i = 0; i < n; ) {
        int j = i;
        while (j < n && dist[qu[j]] == dist[qu[i]])
            ++j;
        shuffle(qu + i, qu + j, rng);
        i = j;
    }
    // mdebug(qu, n);
    
    vl = -1, vr = n - 1;
    while (vr - vl > 1) {
        int vm;
        if (vr - vl > MIN_RAND_SEP) {
            vm = vl + (vr - vl) * dstrb(rng) + 0.5;
        } else {
            vm = (vl + vr) / 2;
        }
        for (int i = 0; i <= vm; ++i)
            col[qu[i]] = 1;
        for (int i = vm + 1; i < n; ++i)
            col[qu[i]] = 0;
        if (askCol() == d0)
            vr = vm;
        else
            vl = vm;
    }
    assert(vl >= 0);
    int T = qu[vr];
    // debug(vl, vr, T);
    
    vl = -1;
    --vr;
    while (vr - vl > 1) {
        int vm;
        if (vr - vl > MIN_RAND_SEP) {
            vm = vl + (vr - vl) * dstrb(rng) + 0.5;
        } else {
            vm = (vl + vr) / 2;
        }
        for (int i = 0; i <= vm; ++i)
            col[qu[i]] = 1;
        for (int i = vm + 1; i < n; ++i)
            col[qu[i]] = 0;
        vector<int> w(m, 0);
        for (int i = 0; i < m; ++i)
            if (!col[eu[i]] || !col[ev[i]])
                w[i] = 1;
        for (int v = T; v != v0; v = parv[v]) {
            w[pare[v]] = 0;
        }
        if (ask(w) == d0)
            vr = vm;
        else
            vl = vm;
    }
    int S = qu[vr];
    // debug(S, T);
    answer(S, T);
}

#ifdef LOCAL


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);
    cout << N << ' ' << M << ' ' << A << ' ' << B << ' ' << S << ' ' << T << endl;
    for (int i = 0; i < M; ++i)
        cout << U[i] << ' ' << V[i] << endl;
    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("in", "r", stdin);
    
    mt19937 rng(1337);
    for (int test = 1; ; ++test) {
        N = 3;//9e4;
        M = N - 1;//13e4;//N - 1;
        A = 1;
        B = 1e9;
        S = rng() % N;
        T = rng() % N;
        while (T == S) T = rng() % N;
        U.resize(M);
        V.resize(M);
        graph.assign(N, std::vector<std::pair<int, int>>());
        for (int v = 1; v < N; ++v) {
            int i = v - 1;
            int p = rng() % v;
            U[i] = p;
            V[i] = v;
            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);
        if (num_calls > 50) exit(0);
        
        if (test % 10000 == 0) debug(test);
    }/**/
    
    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;
}


// int32_t main() {
// #ifdef LOCAL
//     freopen("in", "r", stdin);
// #endif
//     ios::sync_with_stdio(0);
//     cin.tie(0);


//     return 0;
// }
#endif

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