oj.uz

Submission #413471

# Submission time Handle Problem Language Result Execution time Memory
413471 2021-05-28T19:07:31 Z usachevd0 Highway Tolls (IOI18_highway) C++14
90 / 100
 338 ms 11608 KB 
#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(seed);
    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);
    }
    
    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 = (vl + vr) >> 1;
        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;
            }
        }
    }
    // mdebug(qu, n);
    
    vl = -1, vr = n;
    while (vr - vl > 1) {
        int vm = (vl + vr) >> 1;
        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 = n;
    while (vr - vl > 1) {
        int vm = (vl + vr) >> 1;
        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 = 6;
        M = N - 1;
        A = 1;
        B = 2;
        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 (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.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2480 KB Output is correct
2 Correct 17 ms 3196 KB Output is correct
3 Correct 172 ms 9668 KB Output is correct
4 Correct 213 ms 9656 KB Output is correct
5 Correct 191 ms 9776 KB Output is correct
6 Correct 208 ms 9700 KB Output is correct
7 Correct 176 ms 9656 KB Output is correct
8 Correct 236 ms 9760 KB Output is correct
9 Correct 163 ms 9752 KB Output is correct
10 Correct 182 ms 9756 KB Output is correct
11 Correct 169 ms 9160 KB Output is correct
12 Correct 183 ms 9292 KB Output is correct
13 Correct 197 ms 9260 KB Output is correct
14 Correct 185 ms 9104 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3140 KB Output is correct
2 Correct 30 ms 3888 KB Output is correct
3 Correct 57 ms 4636 KB Output is correct
4 Correct 154 ms 9104 KB Output is correct
5 Correct 161 ms 9112 KB Output is correct
6 Correct 177 ms 9180 KB Output is correct
7 Correct 168 ms 9180 KB Output is correct
8 Correct 130 ms 9108 KB Output is correct
9 Correct 143 ms 9136 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2504 KB Output is correct
2 Correct 23 ms 3136 KB Output is correct
3 Correct 156 ms 8060 KB Output is correct
4 Correct 158 ms 9660 KB Output is correct
5 Correct 213 ms 9660 KB Output is correct
6 Correct 214 ms 9668 KB Output is correct
7 Correct 166 ms 9664 KB Output is correct
8 Correct 169 ms 9696 KB Output is correct
9 Correct 230 ms 9672 KB Output is correct
10 Correct 185 ms 9660 KB Output is correct
11 Correct 220 ms 9104 KB Output is correct
12 Correct 230 ms 9124 KB Output is correct
13 Correct 236 ms 9104 KB Output is correct
14 Correct 181 ms 9172 KB Output is correct
15 Correct 222 ms 9660 KB Output is correct
16 Correct 163 ms 9792 KB Output is correct
17 Correct 222 ms 9128 KB Output is correct
18 Correct 220 ms 9160 KB Output is correct
19 Correct 167 ms 9656 KB Output is correct
20 Correct 209 ms 9108 KB Output is correct
21 Correct 170 ms 9800 KB Output is correct
22 Correct 194 ms 9896 KB Output is correct
23 Correct 166 ms 9820 KB Output is correct
24 Correct 198 ms 9860 KB Output is correct
25 Correct 177 ms 9192 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3272 KB Output is correct
2 Correct 22 ms 3264 KB Output is correct
3 Correct 203 ms 10092 KB Output is correct
4 Correct 175 ms 10452 KB Output is correct
5 Correct 334 ms 11392 KB Output is correct
6 Correct 256 ms 11488 KB Output is correct
7 Correct 272 ms 11412 KB Output is correct
8 Correct 304 ms 11396 KB Output is correct
9 Correct 210 ms 8712 KB Output is correct
10 Correct 200 ms 8968 KB Output is correct
11 Correct 241 ms 9464 KB Output is correct
12 Correct 227 ms 10724 KB Output is correct
13 Correct 264 ms 11208 KB Output is correct
14 Correct 244 ms 11404 KB Output is correct
15 Correct 316 ms 11516 KB Output is correct
16 Correct 278 ms 9744 KB Output is correct
17 Correct 202 ms 9880 KB Output is correct
18 Correct 219 ms 10248 KB Output is correct
19 Correct 204 ms 9996 KB Output is correct
20 Correct 213 ms 10204 KB Output is correct
21 Correct 290 ms 11472 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3272 KB Output is correct
2 Correct 20 ms 3268 KB Output is correct
3 Correct 229 ms 10052 KB Output is correct
4 Partially correct 261 ms 10292 KB Output is partially correct
5 Correct 203 ms 10628 KB Output is correct
6 Partially correct 310 ms 11476 KB Output is partially correct
7 Partially correct 194 ms 10092 KB Output is partially correct
8 Partially correct 222 ms 10296 KB Output is partially correct
9 Partially correct 247 ms 10584 KB Output is partially correct
10 Correct 338 ms 11460 KB Output is correct
11 Partially correct 250 ms 11504 KB Output is partially correct
12 Partially correct 264 ms 11416 KB Output is partially correct
13 Correct 275 ms 9384 KB Output is correct
14 Correct 229 ms 8976 KB Output is correct
15 Correct 228 ms 9456 KB Output is correct
16 Correct 206 ms 9044 KB Output is correct
17 Correct 297 ms 9456 KB Output is correct
18 Correct 239 ms 9048 KB Output is correct
19 Correct 277 ms 10780 KB Output is correct
20 Correct 262 ms 11116 KB Output is correct
21 Correct 260 ms 11608 KB Output is correct
22 Partially correct 284 ms 11404 KB Output is partially correct
23 Correct 303 ms 11396 KB Output is correct
24 Partially correct 267 ms 11424 KB Output is partially correct
25 Partially correct 268 ms 11416 KB Output is partially correct
26 Partially correct 257 ms 11404 KB Output is partially correct
27 Partially correct 235 ms 10172 KB Output is partially correct
28 Correct 217 ms 10024 KB Output is correct
29 Partially correct 168 ms 10188 KB Output is partially correct
30 Correct 199 ms 10044 KB Output is correct
31 Partially correct 205 ms 9980 KB Output is partially correct
32 Correct 203 ms 9948 KB Output is correct
33 Correct 264 ms 10252 KB Output is correct
34 Correct 173 ms 10080 KB Output is correct
35 Partially correct 208 ms 9988 KB Output is partially correct
36 Correct 219 ms 9884 KB Output is correct
37 Correct 200 ms 10104 KB Output is correct
38 Correct 192 ms 10068 KB Output is correct
39 Partially correct 222 ms 11488 KB Output is partially correct
40 Partially correct 302 ms 11492 KB Output is partially correct
41 Correct 301 ms 11460 KB Output is correct
42 Partially correct 207 ms 11508 KB Output is partially correct