oj.uz

답안 #629711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
629711 2022-08-14T23:25:46 Z TAMREF Meetings (JOI19_meetings) C++17
100 / 100
 1207 ms 976 KB 
#include <bits/stdc++.h>
#include "meetings.h"
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long; using lf = long double; 
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(0x1557);
template<class> struct is_container : false_type {};
template<class... Ts> struct is_container<vector<Ts...>> : true_type {};
template<class... Ts> struct is_container<map<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_map<Ts...>> : true_type {};
template<class... Ts> struct is_container<set<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_set<Ts...>> : true_type {};
template<class... Ts> struct is_container<multiset<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_multiset<Ts...>> : true_type {};
template<class T, class = typename enable_if<is_container<T>::value>::type>
ostream& operator<<(ostream &o, T x) {
  #ifndef TAMREF
  return o;
  #endif
  int f = 1;
  o << "{";
  for (auto y : x) {
    o << (f ? "" : ", ") << y;
    f = 0;
  }
  return o << "}";
}
template<class T, class U>
ostream& operator<<(ostream &o, pair<T, U> x) {
  #ifndef TAMREF
  return o;
  #endif
  return o << "(" << x.first << ", " << x.second << ")";
}

void Solve(int);

#ifdef TAMREF
namespace {

const int MAX_N = 2000;
const int MAX_CALLS = 100000;

void WrongAnswer(int code) {
  printf("Wrong Answer [%d]\n", code);
  exit(0);
}

int N, num_calls;
std::vector<int> graph[MAX_N];
std::set<std::pair<int, int>> edges, edges_reported;

int weight[MAX_N];

bool Visit(int p, int e, int rt = -1) {
  if (p == e) {
    ++weight[p];
    return true;
  }
  for (int q : graph[p]) {
    if (q != rt) {
      if (Visit(q, e, p)) {
        ++weight[p];
        return true;
      }
    }
  }
  return false;
}

}  // namespace

int Query(int u, int v, int w, bool stealth=false) {
  if(stealth) --num_calls;
  if(!stealth) {
    debug("Q(%d %d %d) = ", u, v, w);
  }
  if (!(0 <= u && u <= N - 1 && 0 <= v && v <= N - 1 && 0 <= w && w <= N - 1 &&
        u != v && u != w && v != w)) {
    WrongAnswer(1);
  }
  if (++num_calls > MAX_CALLS) {
    WrongAnswer(2);
  }
  std::fill(weight, weight + N, 0);
  Visit(u, v);
  Visit(u, w);
  Visit(v, w);
  for (int x = 0; x < N; ++x) {
    if (weight[x] == 3) {
      if(!stealth) debug("%d\n", x);
      return x;
    }
  }
  printf("Error: the input may be invalid\n");
  exit(0);
}

void Bridge(int u, int v) {
  debug("B(%d %d)\n", u, v);
  if (!(0 <= u && u < v && v <= N - 1)) {
    WrongAnswer(3);
  }
  if (!(edges.count(std::make_pair(u, v)) >= 1)) {
    WrongAnswer(4);
  }
  if (!(edges_reported.count(std::make_pair(u, v)) == 0)) {
    WrongAnswer(5);
  }
  edges_reported.insert(std::make_pair(u, v));
}

int main() {
  if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  for (int i = 0; i < N - 1; ++i) {
    int u, v;
    if (scanf("%d%d", &u, &v) != 2) {
      fprintf(stderr, "Error while reading input\n");
      exit(1);
    }
    graph[u].push_back(v);
    graph[v].push_back(u);
    edges.insert(std::make_pair(u, v));
  }

  num_calls = 0;
  Solve(N);
  if (edges_reported.size() != static_cast<size_t>(N - 1)) {
    WrongAnswer(6);
  }
  printf("Accepted: %d\n", num_calls);
  return 0;
}
#endif

void _Query(int a, int b, int c, int expt) {
  #ifdef TAMREF
  assert(Query(a, b, c, true) == expt);
  #endif
}

void _Bridge(int x, int y) {
  if(x < y) Bridge(x, y);
  else Bridge(y, x);
}

void solve(vector<int> v) {
  int n = szz(v);
  vector<bool> vis(n);
  vector<vector<int>> ch(n);
  vector<int> sz(n), par(n), chain_head(n), chain_leaf(n);

  fill(all(par), -1);
  iota(all(chain_head), 0);
  iota(all(chain_leaf), 0);
  int r = Query(v[0], v[1], v[2]);

  auto manage_hld = [&](int p) {
    for(int g = par[p]; g != -1; p = g, g = par[g]) {
      sz[g] += 1;
      int k = find(all(ch[g]), p) - ch[g].begin();
      for(int j = k; j && sz[ch[g][j-1]] < sz[ch[g][j]]; j--) swap(ch[g][j-1], ch[g][j]);
      if(k && ch[g][0] == p) { // change head and heavy chain
        debug("%d became a new heavy chain of %d, beating %d\n", p, g, ch[g][1]);
        int q = ch[g][1];
        chain_leaf[q] = chain_leaf[chain_head[g]];
        chain_leaf[chain_head[g]] = chain_leaf[p];

        for(int i = q; i != -1; i = szz(ch[i]) ? ch[i][0] : -1) chain_head[i] = q;
        for(int i = p; i != -1; i = szz(ch[i]) ? ch[i][0] : -1) chain_head[i] = chain_head[g];
      }
    }
  };
  
  auto append_as_leaf = [&](int p, int x) {
    assert(!vis[x]);
    vis[x] = 1;
    par[x] = p;
    ch[p].pp(x);
    sz[x] = 1;
    sz[p] += 1;

    if(szz(ch[p]) == 1) {
      chain_head[x] = chain_head[p];
      chain_leaf[ chain_head[x] ] = x;
    } else {
      chain_head[x] = chain_leaf[x] = x;
    }

    // maintain HLD structure
    manage_hld(p);
  };

  vis[r] = 1;
  for(int i = 0; i < 3; i++) {
    if(!vis[v[i]]) append_as_leaf(r, v[i]);
  }

  auto splice_path = [&](int p, int l, int m) {
    assert(par[l] == p);
    sz[m] = sz[l] + 1;
    par[l] = m;
    ch[m].pp(l);
    chain_head[m] = (chain_head[l] == l ? m : chain_head[l]);
    if(l == chain_head[l]) chain_leaf[m] = chain_leaf[l];
    for(int i = l; i != -1; i = szz(ch[i]) ? ch[i][0] : -1) chain_head[i] = chain_head[m];

    par[m] = p;
    auto it = find(all(ch[p]), l);
    assert(it != ch[p].end());
    *it = m;

    manage_hld(m);
  };

  auto bisect_on_path = [&](int u, int v, int x) {
    assert(!vis[x]);
    vis[x] = 1;
    // generate joint path in O(n)
    vector<int> pu, pv;
    for(int x = u; x != -1; x = par[x]) pu.pp(x);
    for(int x = v; x != -1; x = par[x]) pv.pp(x);
    int lc = -1, z = min(szz(pu), szz(pv));
    for(int i = 0; i < z; i++) {
      if(pu.back() == pv.back()) {
        lc = pu.back();
        pu.pop_back(); pv.pop_back();
      }
    }
    assert(lc != -1);
    pu.pp(lc);
    copy(pv.rbegin(), pv.rend(), back_inserter(pu));
    // binary search to insert x
    int lo = 0, hi = szz(pu) - 2, mi;
    while(lo < hi) {
      mi = (lo + hi + 1) >> 1;
      int q = Query(x, pu[mi], v);
      assert(q == x || q == pu[mi]);
      if(q == pu[mi]) hi = mi - 1;
      else lo = mi;
    }
    // hi should be answer
    _Query(pu[hi], pu[hi+1], x, x);
    
    if(par[pu[hi]] == pu[hi + 1]) {
      splice_path(pu[hi+1], pu[hi], x);
    } else {
      splice_path(pu[hi], pu[hi+1], x);
    }
  };

  auto single_branch = [&](int p, int l, int x, bool last_branch) -> int {
    int y = Query(p, l, x);
    if(y == p) {
      if(last_branch) {
        append_as_leaf(p, x);
        return -1;
      } else {
        return p;
      }
    }
    if(y == l) { // subtree of leaf
      append_as_leaf(l, x);
      return -1;
    }
    if(y == x) {
      bisect_on_path(p, l, x);
      return -1;
    }
    if(vis[y]) return y;
    bisect_on_path(p, l, y);
    append_as_leaf(y, x);
    return -1;
  };

  auto double_branch = [&](int rt1, int rt2, int x, bool last_branch) -> int {
    int l1 = chain_leaf[chain_head[rt1]], l2 = chain_leaf[chain_head[rt2]];
    int y = Query(l1, l2, x);
    if(y == l1 || y == l2) {
      append_as_leaf(y, x);
      return -1;
    }
    if(y == par[rt1]) {
      if(last_branch) {
        append_as_leaf(y, x);
        return -1;
      }
      return y;
    }
    if(y == x) {
      bisect_on_path(l1, l2, x);
      return -1;
    }
    if(vis[y]) return y;
    bisect_on_path(l1, l2, y);
    append_as_leaf(y, x);
    return -1;
  };

  for(int i = 3; i < n; i++) {
    int x = v[i];
    debug("processing %d\n", x);
    if(vis[x]) continue;
    
    for(int p = r; p != -1 && sz[p] > 1;) {
      debug("x = %d, p = %d\n", x, p);
      if(szz(ch[p]) == 1) {
        debug("bough\n");
        p = single_branch(p, chain_leaf[chain_head[p]], x, true);
      } else {
        for(int j = 0, init_p = p; p == init_p && j < szz(ch[p]); j += 2) {
          if(j + 1 == szz(ch[p])) {
            p = single_branch(p, chain_leaf[ch[p][j]], x, true);
          } else {
            debug("double branch\n");
            p = double_branch(ch[p][j], ch[p][j+1], x, j + 2 == szz(ch[p]));
            debug("double branch done. p = %d\n", p);
          }
        }
      }
    }
    debug("par[%d] = %d\n", x, par[x]);
  }

  for(int i = 0; i < n; i++) {
    if(par[i] != -1) _Bridge(i, par[i]);
  }
}

void Solve(int n) {
  vector<int> v(n);
  iota(all(v), 0);
  shuffle(all(v), rng);
  solve(v);
}

Compilation message

meetings.cpp: In lambda function:
meetings.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 42
      |                    ^~
meetings.cpp:194:9: note: in expansion of macro 'debug'
  194 |         debug("%d became a new heavy chain of %d, beating %d\n", p, g, ch[g][1]);
      |         ^~~~~
meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 42
      |                    ^~
meetings.cpp:332:5: note: in expansion of macro 'debug'
  332 |     debug("processing %d\n", x);
      |     ^~~~~
meetings.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 42
      |                    ^~
meetings.cpp:336:7: note: in expansion of macro 'debug'
  336 |       debug("x = %d, p = %d\n", x, p);
      |       ^~~~~
meetings.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 42
      |                    ^~
meetings.cpp:338:9: note: in expansion of macro 'debug'
  338 |         debug("bough\n");
      |         ^~~~~
meetings.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 42
      |                    ^~
meetings.cpp:345:13: note: in expansion of macro 'debug'
  345 |             debug("double branch\n");
      |             ^~~~~
meetings.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 42
      |                    ^~
meetings.cpp:347:13: note: in expansion of macro 'debug'
  347 |             debug("double branch done. p = %d\n", p);
      |             ^~~~~
meetings.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 42
      |                    ^~
meetings.cpp:352:5: note: in expansion of macro 'debug'
  352 |     debug("par[%d] = %d\n", x, par[x]);
      |     ^~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 0 ms 336 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 0 ms 336 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 0 ms 336 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 4 ms 336 KB Output is correct
28 Correct 3 ms 392 KB Output is correct
29 Correct 4 ms 392 KB Output is correct
30 Correct 3 ms 336 KB Output is correct
31 Correct 3 ms 336 KB Output is correct
32 Correct 5 ms 336 KB Output is correct
33 Correct 6 ms 336 KB Output is correct
34 Correct 8 ms 392 KB Output is correct
35 Correct 7 ms 336 KB Output is correct
36 Correct 4 ms 388 KB Output is correct
37 Correct 14 ms 416 KB Output is correct
38 Correct 15 ms 336 KB Output is correct
39 Correct 14 ms 412 KB Output is correct

Subtask #4
71.0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 257 ms 612 KB Output is correct
2 Correct 267 ms 596 KB Output is correct
3 Correct 274 ms 620 KB Output is correct
4 Correct 260 ms 616 KB Output is correct
5 Correct 251 ms 716 KB Output is correct
6 Correct 241 ms 592 KB Output is correct
7 Correct 325 ms 616 KB Output is correct
8 Correct 353 ms 604 KB Output is correct
9 Correct 342 ms 700 KB Output is correct
10 Correct 315 ms 608 KB Output is correct
11 Correct 392 ms 748 KB Output is correct
12 Correct 398 ms 656 KB Output is correct
13 Correct 212 ms 640 KB Output is correct
14 Correct 215 ms 644 KB Output is correct
15 Correct 210 ms 624 KB Output is correct
16 Correct 223 ms 616 KB Output is correct
17 Correct 325 ms 728 KB Output is correct
18 Correct 191 ms 616 KB Output is correct
19 Correct 208 ms 624 KB Output is correct
20 Correct 259 ms 624 KB Output is correct
21 Correct 264 ms 624 KB Output is correct
22 Correct 265 ms 712 KB Output is correct
23 Correct 256 ms 624 KB Output is correct
24 Correct 260 ms 620 KB Output is correct
25 Correct 257 ms 636 KB Output is correct
26 Correct 243 ms 620 KB Output is correct
27 Correct 257 ms 736 KB Output is correct
28 Correct 397 ms 644 KB Output is correct
29 Correct 304 ms 608 KB Output is correct
30 Correct 324 ms 612 KB Output is correct
31 Correct 346 ms 592 KB Output is correct
32 Correct 1207 ms 976 KB Output is correct
33 Correct 1028 ms 908 KB Output is correct
34 Correct 3 ms 336 KB Output is correct
35 Correct 3 ms 336 KB Output is correct
36 Correct 3 ms 336 KB Output is correct
37 Correct 3 ms 388 KB Output is correct
38 Correct 3 ms 336 KB Output is correct
39 Correct 4 ms 336 KB Output is correct
40 Correct 6 ms 336 KB Output is correct
41 Correct 8 ms 336 KB Output is correct
42 Correct 7 ms 392 KB Output is correct
43 Correct 4 ms 336 KB Output is correct
44 Correct 15 ms 412 KB Output is correct
45 Correct 14 ms 336 KB Output is correct
46 Correct 14 ms 416 KB Output is correct
47 Correct 1 ms 336 KB Output is correct
48 Correct 1 ms 336 KB Output is correct
49 Correct 0 ms 336 KB Output is correct
50 Correct 1 ms 336 KB Output is correct
51 Correct 1 ms 336 KB Output is correct
52 Correct 0 ms 336 KB Output is correct
53 Correct 1 ms 360 KB Output is correct
54 Correct 1 ms 336 KB Output is correct
55 Correct 1 ms 336 KB Output is correct
56 Correct 1 ms 344 KB Output is correct
57 Correct 1 ms 336 KB Output is correct
58 Correct 1 ms 336 KB Output is correct
59 Correct 1 ms 336 KB Output is correct
60 Correct 0 ms 336 KB Output is correct
61 Correct 0 ms 336 KB Output is correct
62 Correct 0 ms 336 KB Output is correct
63 Correct 0 ms 336 KB Output is correct
64 Correct 1 ms 336 KB Output is correct
65 Correct 0 ms 336 KB Output is correct
66 Correct 0 ms 336 KB Output is correct
67 Correct 0 ms 336 KB Output is correct
68 Correct 1 ms 336 KB Output is correct
69 Correct 0 ms 336 KB Output is correct
70 Correct 0 ms 336 KB Output is correct
71 Correct 0 ms 336 KB Output is correct
72 Correct 0 ms 336 KB Output is correct