제출 #336234

#제출 시각아이디문제언어결과실행 시간메모리
336234caoashBirthday gift (IZhO18_treearray)C++17
0 / 100
171 ms90988 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using vl = vector<ll>; #define pb push_back #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define lb lower_bound #define ub upper_bound using pi = pair<int,int>; #define f first #define s second #define mp make_pair const int MX = 200005; const int MOD = (int) (1e9 + 7); const ll INF = (ll) 1e18; template < int SZ > struct LCA { int depth[SZ]; int p[SZ][33]; vector < int > adj[SZ]; void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } void dfs(int v, int par) { for (int to: adj[v]) { if (to != par) { p[to][0] = v; depth[to] = depth[v] + 1; dfs(to, v); } } } void precomp() { for (int i = 0; i < SZ; i++) { for (int j = 0; j < 32; j++) { p[i][j] = -1; } } p[0][0] = 0; dfs(0, -1); for (int j = 1; j < 32; j++) { for (int i = 0; i < SZ; i++) { if (p[i][j - 1] == -1) { p[i][j] = -1; } else { p[i][j] = p[p[i][j - 1]][j - 1]; } } } } int query(int a, int b) { if (depth[a] > depth[b]) { swap(a, b); } int lift = depth[b] - depth[a]; for (int j = 31; j >= 0; j--) { if (lift & (1 << j)) { b = p[b][j]; } } for (int j = 31; j >= 0; j--) { if (p[a][j] != p[b][j]) { a = p[a][j]; b = p[b][j]; } } return (a == b) ? a : p[a][0]; } }; namespace output { void pr(int x) { cout << x; } void pr(long x) { cout << x; } void pr(ll x) { cout << x; } void pr(unsigned x) { cout << x; } void pr(unsigned long x) { cout << x; } void pr(unsigned long long x) { cout << x; } void pr(float x) { cout << x; } void pr(double x) { cout << x; } void pr(long double x) { cout << x; } void pr(char x) { cout << x; } void pr(const char * x) { cout << x; } void pr(const string & x) { cout << x; } void pr(bool x) { pr(x ? "true" : "false"); } template < class T1, class T2 > void pr(const pair < T1, T2 > & x); template < class T > void pr(const T & x); template < class T, class...Ts > void pr(const T & t, const Ts & ...ts) { pr(t); pr(ts...); } template < class T1, class T2 > void pr(const pair < T1, T2 > & x) { pr("{", x.f, ", ", x.s, "}"); } template < class T > void pr(const T & x) { pr("{"); // const iterator needed for vector<bool> bool fst = 1; for (const auto & a: x) pr(!fst ? ", " : "", a), fst = 0; pr("}"); } void ps() { pr("\n"); } // print w/ spaces template < class T, class...Ts > void ps(const T & t, const Ts & ...ts) { pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); } void pc() { cout << "]" << endl; } // debug w/ commas template < class T, class...Ts > void pc(const T & t, const Ts & ...ts) { pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); } #define dbg(x...) pr("[", #x, "] = ["), pc(x); } #ifdef mikey using namespace output; #else using namespace output; #define dbg(x...) #endif LCA<MX> lca; vi adj[MX]; multiset<pi> sol[MX]; int main(){ #ifdef mikey freopen("a.in", "r", stdin); #endif ios::sync_with_stdio(false); cin.tie(0); int n, m, q; cin >> n >> m >> q; for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--, v--; lca.addEdge(u, v); adj[u].pb(v), adj[v].pb(u); } lca.precomp(); vi a(m); for (int i = 0; i < m; i++) cin >> a[i], a[i]--; for (int i = 0; i < n - 1; i++) { sol[lca.query(a[i], a[i + 1])].insert(mp(i, i + 1)); sol[a[i]].insert(mp(i, i)); } sol[a[n - 1]].insert(mp(n - 1, n - 1)); for (int i = 0; i < q; i++) { int qt; cin >> qt; if (qt == 1) { int pos, v; cin >> pos >> v; pos--, v--; if (pos) sol[lca.query(a[pos - 1], a[pos])].erase(sol[lca.query(a[pos - 1], a[pos])].find(mp(pos - 1, pos))); if (pos < m - 1) sol[lca.query(a[pos], a[pos + 1])].erase(sol[lca.query(a[pos], a[pos + 1])].find(mp(pos, pos + 1))); sol[a[pos]].erase(sol[a[pos]].find(mp(pos, pos))); a[pos] = v; if (pos) sol[lca.query(a[pos - 1], a[pos])].insert(mp(pos - 1, pos)); if (pos < m - 1) sol[lca.query(a[pos], a[pos + 1])].insert(mp(pos, pos + 1)); sol[a[pos]].insert(mp(pos, pos)); } else { int l, r, v; cin >> l >> r >> v; l--, r--, v--; multiset<pi> &curr = sol[v]; auto x = curr.lb(mp(l, INT_MIN)); if (x == curr.end()) { cout << -1 << " " << -1 << '\n'; } else { if (x->s <= r) cout << (x->f) + 1 << " " << (x->s) + 1 << '\n'; else cout << -1 << " " << -1 << '\n'; } } } }

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

treearray.cpp:163: warning: "dbg" redefined
  163 | #define dbg(x...)
      | 
treearray.cpp:156: note: this is the location of the previous definition
  156 |   #define dbg(x...) pr("[", #x, "] = ["), pc(x);
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...