oj.uz

Submission #413474

# Submission time Handle Problem Language Result Execution time Memory
413474 2021-05-28T19:09:47 Z usachevd0 Highway Tolls (IOI18_highway) C++14
90 / 100
 315 ms 11572 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);
    }
    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 = (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 2 ms 2376 KB Output is correct
2 Correct 2 ms 2376 KB Output is correct
3 Correct 2 ms 2376 KB Output is correct
4 Correct 3 ms 2376 KB Output is correct
5 Correct 2 ms 2420 KB Output is correct
6 Correct 3 ms 2376 KB Output is correct
7 Correct 2 ms 2424 KB Output is correct
8 Correct 2 ms 2376 KB Output is correct
9 Correct 2 ms 2376 KB Output is correct
10 Correct 2 ms 2420 KB Output is correct
11 Correct 2 ms 2424 KB Output is correct
12 Correct 3 ms 2376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2504 KB Output is correct
2 Correct 24 ms 3172 KB Output is correct
3 Correct 165 ms 9728 KB Output is correct
4 Correct 224 ms 9652 KB Output is correct
5 Correct 217 ms 9756 KB Output is correct
6 Correct 201 ms 9664 KB Output is correct
7 Correct 226 ms 9756 KB Output is correct
8 Correct 262 ms 9656 KB Output is correct
9 Correct 178 ms 9656 KB Output is correct
10 Correct 181 ms 9664 KB Output is correct
11 Correct 220 ms 9416 KB Output is correct
12 Correct 205 ms 9180 KB Output is correct
13 Correct 231 ms 9196 KB Output is correct
14 Correct 186 ms 9108 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3144 KB Output is correct
2 Correct 41 ms 3892 KB Output is correct
3 Correct 59 ms 4644 KB Output is correct
4 Correct 150 ms 9184 KB Output is correct
5 Correct 152 ms 9108 KB Output is correct
6 Correct 138 ms 9148 KB Output is correct
7 Correct 144 ms 9216 KB Output is correct
8 Correct 143 ms 9172 KB Output is correct
9 Correct 174 ms 9176 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2504 KB Output is correct
2 Correct 21 ms 3132 KB Output is correct
3 Correct 163 ms 8384 KB Output is correct
4 Correct 164 ms 9876 KB Output is correct
5 Correct 161 ms 9692 KB Output is correct
6 Correct 172 ms 9740 KB Output is correct
7 Correct 155 ms 9664 KB Output is correct
8 Correct 180 ms 9656 KB Output is correct
9 Correct 229 ms 9660 KB Output is correct
10 Correct 199 ms 9728 KB Output is correct
11 Correct 181 ms 9212 KB Output is correct
12 Correct 236 ms 9192 KB Output is correct
13 Correct 197 ms 9136 KB Output is correct
14 Correct 235 ms 9140 KB Output is correct
15 Correct 203 ms 9680 KB Output is correct
16 Correct 218 ms 9712 KB Output is correct
17 Correct 197 ms 9164 KB Output is correct
18 Correct 182 ms 9236 KB Output is correct
19 Correct 212 ms 9680 KB Output is correct
20 Correct 178 ms 9096 KB Output is correct
21 Correct 230 ms 9876 KB Output is correct
22 Correct 211 ms 9808 KB Output is correct
23 Correct 189 ms 9916 KB Output is correct
24 Correct 211 ms 9740 KB Output is correct
25 Correct 222 ms 9204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3236 KB Output is correct
2 Correct 27 ms 3260 KB Output is correct
3 Correct 278 ms 10012 KB Output is correct
4 Correct 248 ms 10556 KB Output is correct
5 Correct 274 ms 11496 KB Output is correct
6 Correct 275 ms 11416 KB Output is correct
7 Correct 309 ms 11380 KB Output is correct
8 Correct 315 ms 11388 KB Output is correct
9 Correct 220 ms 8596 KB Output is correct
10 Correct 259 ms 9024 KB Output is correct
11 Correct 246 ms 9372 KB Output is correct
12 Correct 291 ms 10792 KB Output is correct
13 Correct 311 ms 11248 KB Output is correct
14 Correct 232 ms 11572 KB Output is correct
15 Correct 266 ms 11408 KB Output is correct
16 Correct 238 ms 9672 KB Output is correct
17 Correct 185 ms 9984 KB Output is correct
18 Correct 208 ms 10152 KB Output is correct
19 Correct 239 ms 10056 KB Output is correct
20 Correct 171 ms 10084 KB Output is correct
21 Correct 289 ms 11476 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3132 KB Output is correct
2 Correct 22 ms 3260 KB Output is correct
3 Correct 188 ms 10132 KB Output is correct
4 Correct 195 ms 10224 KB Output is correct
5 Partially correct 213 ms 10536 KB Output is partially correct
6 Partially correct 282 ms 11504 KB Output is partially correct
7 Correct 181 ms 10088 KB Output is correct
8 Partially correct 252 ms 10216 KB Output is partially correct
9 Partially correct 202 ms 10452 KB Output is partially correct
10 Correct 280 ms 11484 KB Output is correct
11 Partially correct 294 ms 11528 KB Output is partially correct
12 Partially correct 296 ms 11396 KB Output is partially correct
13 Correct 274 ms 9524 KB Output is correct
14 Correct 199 ms 9080 KB Output is correct
15 Correct 227 ms 9388 KB Output is correct
16 Correct 265 ms 8980 KB Output is correct
17 Correct 298 ms 9384 KB Output is correct
18 Correct 251 ms 9024 KB Output is correct
19 Correct 236 ms 10760 KB Output is correct
20 Correct 244 ms 11164 KB Output is correct
21 Correct 299 ms 11432 KB Output is correct
22 Partially correct 273 ms 11408 KB Output is partially correct
23 Partially correct 242 ms 11476 KB Output is partially correct
24 Partially correct 226 ms 11504 KB Output is partially correct
25 Partially correct 302 ms 11400 KB Output is partially correct
26 Correct 312 ms 11488 KB Output is correct
27 Correct 220 ms 10072 KB Output is correct
28 Partially correct 185 ms 9932 KB Output is partially correct
29 Partially correct 229 ms 10180 KB Output is partially correct
30 Partially correct 168 ms 10100 KB Output is partially correct
31 Partially correct 199 ms 9984 KB Output is partially correct
32 Partially correct 188 ms 9908 KB Output is partially correct
33 Correct 167 ms 10140 KB Output is correct
34 Partially correct 217 ms 10056 KB Output is partially correct
35 Correct 232 ms 9980 KB Output is correct
36 Correct 219 ms 9876 KB Output is correct
37 Correct 180 ms 10156 KB Output is correct
38 Partially correct 183 ms 10068 KB Output is partially correct
39 Partially correct 274 ms 11568 KB Output is partially correct
40 Correct 262 ms 11472 KB Output is correct
41 Partially correct 259 ms 11464 KB Output is partially correct
42 Partially correct 289 ms 11492 KB Output is partially correct