Submission #629711

#	Time	Username	Problem	Language	Result	Execution time	Memory
629711		TAMREF	Meetings (JOI19_meetings)	C++17	100 / 100	1207 ms	976 KiB

meetings

#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 (stderr)

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 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71