제출 #629710

#제출 시각아이디문제언어결과실행 시간메모리
629710TAMREFMeetings (JOI19_meetings)C++17
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.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); }

컴파일 시 표준 에러 (stderr) 메시지

meetings.cpp: In function 'void _Bridge(int, int)':
meetings.cpp:172:13: error: 'Bridge' was not declared in this scope
  172 |   if(x < y) Bridge(x, y);
      |             ^~~~~~
meetings.cpp:173:8: error: 'Bridge' was not declared in this scope
  173 |   else Bridge(y, x);
      |        ^~~~~~
meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:185:11: error: 'Query' was not declared in this scope
  185 |   int r = Query(v[0], v[1], v[2]);
      |           ^~~~~
meetings.cpp: In lambda function:
meetings.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
meetings.cpp:193:9: note: in expansion of macro 'debug'
  193 |         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:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
meetings.cpp:331:5: note: in expansion of macro 'debug'
  331 |     debug("processing %d\n", x);
      |     ^~~~~
meetings.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
meetings.cpp:335:7: note: in expansion of macro 'debug'
  335 |       debug("x = %d, p = %d\n", x, p);
      |       ^~~~~
meetings.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
meetings.cpp:337:9: note: in expansion of macro 'debug'
  337 |         debug("bough\n");
      |         ^~~~~
meetings.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
meetings.cpp:344:13: note: in expansion of macro 'debug'
  344 |             debug("double branch\n");
      |             ^~~~~
meetings.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
meetings.cpp:346:13: note: in expansion of macro 'debug'
  346 |             debug("double branch done. p = %d\n", p);
      |             ^~~~~
meetings.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
meetings.cpp:351:5: note: in expansion of macro 'debug'
  351 |     debug("par[%d] = %d\n", x, par[x]);
      |     ^~~~~