oj.uz

Submission #91636

# Submission time Handle Problem Language Result Execution time Memory
91636 2018-12-28T19:45:13 Z Swistakk Highway Tolls (IOI18_highway) C++14
90 / 100
 388 ms 9772 KB 
#include "highway.h"

#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define st first
#define nd second
#define rd third
#define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
#define RE(i, n) FOR(i, 1, n)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define REP(i, n) for(int i = 0;i <(n); ++i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
  while(*sdbg != ','){cerr<<*sdbg++; }cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define cerr if(0)cout
#endif
#define next ____next
#define prev ____prev
#define left ____left
#define hash ____hash
typedef long long ll;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<pair<int, int> > VPII;
typedef vector<pair<ll, ll> > VPLL;

template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
template<class T1, class T2>
ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
template<class A, class B, class C> struct Triple { A first; B second; C third;
  bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } };
template<class T> void ResizeVec(T&, vector<int>) {}
template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
  vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
  for (T& v : vec) { ResizeVec(v, sz); }
}
typedef Triple<int, int, int> TIII;
template<class A, class B, class C>
ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; }
template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class T> ostream& operator<<(ostream& out, set<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class L, class R> ostream& operator<<(ostream& out, map<L, R> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }


void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
#define int long long
  int M = SZ(U);
  vector<int32_t> zeros(M);
  int best = ask(zeros);
  function<int(VI)> Binuj = [&](VI order) {
    int kl = 0, kp = N - 1, faj = N - 1;
    while (kl <= kp) {
      VI is_forb(N);
      int aktc = (kl + kp) / 2;
      FOR (i, aktc, N - 1) {
        is_forb[order[i]] = 1;
      }
      VI to_ask(M);
      REP (i, M) {
        if (is_forb[U[i]] || is_forb[V[i]]) {
          to_ask[i] = 1;
        }
      }
      if (ask(to_ask) == best) {
        kp = aktc - 1;
      } else {
        kl = aktc + 1;
        faj = order[aktc];
      }
    }
    return faj;
  };
  VVI slo(N);
  REP (i, M) {
    slo[U[i]].PB(V[i]);
    slo[V[i]].PB(U[i]);
  }
  function<vector<int32_t>(int)> Bfs = [&](int root) {
    VI dis(N, N);
    dis[root] = 0;
    vector<int32_t> que{(int32_t)root};
    for (int ii = 0; ii < SZ(que); ii++) {
      int v = que[ii];
      for (auto nei : slo[v]) {
        if (dis[nei] == N) {
          dis[nei] = dis[v] + 1;
          que.PB(nei);
        }
      }
    }
    return que;
  };
  vector<int32_t> order(N);
  iota(ALL(order), 0);
  int any = Binuj(order);
  order = Bfs(any);
  int s = Binuj(order);
  order = Bfs(s);
  int t = Binuj(order);
  answer(s, t);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 416 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 2 ms 248 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 320 KB Output is correct
12 Correct 2 ms 328 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 30 ms 1280 KB Output is correct
3 Correct 320 ms 8620 KB Output is correct
4 Correct 243 ms 8692 KB Output is correct
5 Correct 283 ms 8696 KB Output is correct
6 Correct 248 ms 8644 KB Output is correct
7 Correct 286 ms 8648 KB Output is correct
8 Correct 263 ms 8672 KB Output is correct
9 Correct 263 ms 8664 KB Output is correct
10 Correct 258 ms 8756 KB Output is correct
11 Correct 284 ms 8568 KB Output is correct
12 Correct 319 ms 8640 KB Output is correct
13 Correct 299 ms 8580 KB Output is correct
14 Correct 296 ms 8552 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1276 KB Output is correct
2 Correct 58 ms 2188 KB Output is correct
3 Correct 65 ms 3048 KB Output is correct
4 Correct 202 ms 8544 KB Output is correct
5 Correct 190 ms 8612 KB Output is correct
6 Correct 191 ms 8504 KB Output is correct
7 Correct 183 ms 8600 KB Output is correct
8 Correct 202 ms 8592 KB Output is correct
9 Correct 177 ms 8520 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 26 ms 1284 KB Output is correct
3 Correct 195 ms 6916 KB Output is correct
4 Correct 272 ms 8616 KB Output is correct
5 Correct 270 ms 8644 KB Output is correct
6 Correct 253 ms 8620 KB Output is correct
7 Correct 249 ms 8676 KB Output is correct
8 Correct 253 ms 8692 KB Output is correct
9 Correct 278 ms 8640 KB Output is correct
10 Correct 292 ms 8644 KB Output is correct
11 Correct 317 ms 8556 KB Output is correct
12 Correct 261 ms 8536 KB Output is correct
13 Correct 265 ms 8536 KB Output is correct
14 Correct 284 ms 8548 KB Output is correct
15 Correct 267 ms 8636 KB Output is correct
16 Correct 287 ms 8656 KB Output is correct
17 Correct 305 ms 8596 KB Output is correct
18 Correct 290 ms 8544 KB Output is correct
19 Correct 299 ms 8696 KB Output is correct
20 Correct 269 ms 8552 KB Output is correct
21 Correct 223 ms 8940 KB Output is correct
22 Correct 237 ms 8896 KB Output is correct
23 Correct 274 ms 8924 KB Output is correct
24 Correct 213 ms 8892 KB Output is correct
25 Correct 265 ms 8608 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1320 KB Output is correct
2 Correct 26 ms 1296 KB Output is correct
3 Correct 328 ms 8968 KB Output is correct
4 Correct 373 ms 9188 KB Output is correct
5 Correct 382 ms 9764 KB Output is correct
6 Correct 371 ms 9728 KB Output is correct
7 Correct 340 ms 9672 KB Output is correct
8 Correct 368 ms 9684 KB Output is correct
9 Correct 312 ms 6228 KB Output is correct
10 Correct 291 ms 6656 KB Output is correct
11 Correct 287 ms 7264 KB Output is correct
12 Correct 332 ms 8668 KB Output is correct
13 Correct 363 ms 9168 KB Output is correct
14 Correct 341 ms 9580 KB Output is correct
15 Correct 361 ms 9548 KB Output is correct
16 Correct 293 ms 7584 KB Output is correct
17 Correct 254 ms 8988 KB Output is correct
18 Correct 295 ms 9028 KB Output is correct
19 Correct 224 ms 8992 KB Output is correct
20 Correct 280 ms 9132 KB Output is correct
21 Correct 303 ms 9672 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1336 KB Output is correct
2 Correct 56 ms 1320 KB Output is correct
3 Partially correct 300 ms 8888 KB Output is partially correct
4 Correct 316 ms 9040 KB Output is correct
5 Partially correct 348 ms 9200 KB Output is partially correct
6 Correct 374 ms 9772 KB Output is correct
7 Correct 309 ms 8860 KB Output is correct
8 Partially correct 320 ms 9068 KB Output is partially correct
9 Correct 329 ms 9176 KB Output is correct
10 Partially correct 368 ms 9704 KB Output is partially correct
11 Partially correct 361 ms 9696 KB Output is partially correct
12 Partially correct 371 ms 9704 KB Output is partially correct
13 Correct 343 ms 7348 KB Output is correct
14 Correct 307 ms 6684 KB Output is correct
15 Correct 283 ms 7236 KB Output is correct
16 Correct 296 ms 6720 KB Output is correct
17 Correct 307 ms 7332 KB Output is correct
18 Correct 326 ms 6772 KB Output is correct
19 Correct 340 ms 8684 KB Output is correct
20 Partially correct 388 ms 9112 KB Output is partially correct
21 Partially correct 372 ms 9588 KB Output is partially correct
22 Correct 365 ms 9536 KB Output is correct
23 Correct 334 ms 9540 KB Output is correct
24 Partially correct 350 ms 9556 KB Output is partially correct
25 Partially correct 379 ms 9548 KB Output is partially correct
26 Partially correct 365 ms 9664 KB Output is partially correct
27 Correct 248 ms 9052 KB Output is correct
28 Partially correct 261 ms 9064 KB Output is partially correct
29 Correct 250 ms 9124 KB Output is correct
30 Correct 263 ms 9084 KB Output is correct
31 Correct 274 ms 9060 KB Output is correct
32 Correct 253 ms 8960 KB Output is correct
33 Correct 265 ms 9196 KB Output is correct
34 Partially correct 280 ms 9032 KB Output is partially correct
35 Correct 269 ms 8988 KB Output is correct
36 Partially correct 244 ms 9024 KB Output is partially correct
37 Partially correct 270 ms 9276 KB Output is partially correct
38 Partially correct 258 ms 9088 KB Output is partially correct
39 Correct 332 ms 9636 KB Output is correct
40 Partially correct 349 ms 9664 KB Output is partially correct
41 Correct 327 ms 9668 KB Output is correct
42 Correct 351 ms 9688 KB Output is correct