제출 #697805

#제출 시각아이디문제언어결과실행 시간메모리
697805vjudge1Birthday gift (IZhO18_treearray)C++17
30 / 100
4049 ms7904 KiB
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> #define file "" #define all(x) x.begin(), x.end() #define fr first #define sc second #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; const int N = 3e5; const int inf = 1e9 + 5; map <int, pii> mp; int a[N], tin[N], tout[N], t[4 * N], timer = 1; int up[N][25]; vector <int> g[N]; void dfs (int x, int pr) { tin[x] = timer++; up[x][0] = pr; for (int i = 1; i <= 20; i++) { up[x][i] = up[up[x][i - 1]][i - 1]; } for (int to : g[x]) { if (to != pr) dfs(to, x); } tout[x] = timer; } bool upper (int x, int y) { if (tin[x] <= tin[y] && tout[x] >= tout[y]) return true; return false; } int lca (int x, int y) { if (x == 0) return y; if (y == 0) return x; if (upper(x, y)) return x; if (upper(y, x)) return y; for (int i = 20; i >= 0; i--) { if (!upper(up[x][i], y)) x = up[x][i]; } return up[x][0]; } void build (int u, int l, int r) { if (l == r) { t[u] = a[l]; return; } int m = l + r >> 1; build(u + u, l, m); build(u + u + 1, m + 1, r); t[u] = lca (t[u + u], t[u + u + 1]); } void upd (int u, int ul, int ur, int pos, int val) { if (ul == ur && ul == pos) { t[u] = val; return; } int m = ul + ur >> 1; if (pos <= m) upd(u + u, ul, m, pos, val); else upd(u + u + 1, m + 1, ur, pos, val); t[u] = lca (t[u + u], t[u + u + 1]); } int get (int u, int ul, int ur, int l, int r) { if (ul > r || ur < l) return 0; if (ul >= l && ur <= r) return t[u]; int m = ul + ur >> 1; int x = get(u + u, ul, m, l, r); int y = get(u + u + 1, m + 1, ur, l, r); return lca(x, y); } pii get (int u, int ul, int ur, int l, int r, int val) { //cerr << u << " " << ul << " " << ur << " " << l << " " << r << " " << val << endl; if (ul == ur && !upper(val, t[u])) return {-1, -1}; if (ul > r || ur < l) { //cerr << u << " " << ul << " " << ur << " " << val << " " << t[u] << " ok1\n"; return {-1, -1}; } if (ul >= l && ur <= r && upper(val, t[u])) { //cerr << u << " " << ul << " " << ur << " " << val << " " << t[u] << " ok2\n"; return {ul, ur}; } //if (ul >= l && ur <= r && !upper(val, t[u])) { // cerr << u << " " << ul << " " << ur << " " << val << " " << t[u] << " ok3\n"; // return {-1, -1}; //} int m = ul + ur >> 1; pii x = get(u + u, ul, m, l, r, val); pii y = get(u + u + 1, m + 1, ur, l, r, val); //cerr << u << " " << ul << " " << ur << ": " << x.fr << " " << x.sc << " - " << y.fr << " " << y.sc << endl; if (x.fr == -1 && y.fr != -1) return y; else if (y.fr == -1 && x.fr != -1) return x; return {x.fr, y.sc}; } int main(){ ios_base :: sync_with_stdio(false); cin.tie(NULL); srand(time(NULL)); int n, m, q; cin >> n >> m >> q; int u, v, tp; for (int i = 1; i < n; i++) { cin >> u >> v; g[u].pb(v); g[v].pb(u); } dfs(1, 1); for (int i = 1; i <= m; i++) { cin >> a[i]; } while (q--) { cin >> tp; if (tp == 1) { int pos, val; cin >> pos >> val; a[pos] = val; } else { int l, r, val; cin >> l >> r >> val; int ok = 0; for (int i = l; i <= r; i++) { int LCA = a[i]; for (int j = i; j <= r; j++) { LCA = lca(LCA, a[j]); if (LCA == val) { cout << i << " " << j << "\n"; ok = 1; break; } } if (ok == 1) break; } if (ok == 0) cout << -1 << " " << -1 << "\n"; } } }

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

treearray.cpp: In function 'void build(int, int, int)':
treearray.cpp:60:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |  int m = l + r >> 1;
      |          ~~^~~
treearray.cpp: In function 'void upd(int, int, int, int, int)':
treearray.cpp:71:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |  int m = ul + ur >> 1;
      |          ~~~^~~~
treearray.cpp: In function 'int get(int, int, int, int, int)':
treearray.cpp:80:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |  int m = ul + ur >> 1;
      |          ~~~^~~~
treearray.cpp: In function 'pii get(int, int, int, int, int, int)':
treearray.cpp:101:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |  int m = ul + ur >> 1;
      |          ~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...