Submission #495710

#TimeUsernameProblemLanguageResultExecution timeMemory
495710kinglineBirthday gift (IZhO18_treearray)C++17
30 / 100
4078 ms5724 KiB
#include <bits/stdc++.h> #define pb push_back #define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define all(data) data.begin() , data.end() #define endl '\n' //freopen("nenokku_easy.in", "r", stdin); //freopen("nenokku_easy.out", "w", stdout); #define int long long #define pii pair < int, int > using namespace std; typedef long long ll; const int N = 2e5 + 5; int lg; int n, m, q, tin[N], tout[N], sz, up[N][20], a[N]; vector < int > g[N]; void dfs(int v, int pr) { tin[v] = ++sz; up[v][0] = pr; for(int i = 1; i < lg; i++) { up[v][i] = up[up[v][i - 1]][i - 1]; } for(int i = 0; i < g[v].size(); i++) { int to = g[v][i]; if(to != pr) { dfs(to, v); } } tout[v] = ++sz; } bool upper(int x, int y) { return tin[x] <= tin[y] && tout[x] >= tout[y]; } int lca(int x, int y) { if(upper(x, y)) return x; if(upper(y, x)) return y; for(int i = lg - 1; i >= 0; i--) { if(up[x][i] == 0) continue; if(!upper(up[x][i], y)) { x = up[x][i]; } } return up[x][0]; } main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> q; while((1 << lg) <= n) { lg++; } for(int i = 1; i < n; i++) { int a, b; cin >> a >> b; g[a].pb(b); g[b].pb(a); } dfs(1, 1); for(int i = 1; i <= m; i++) { cin >> a[i]; } while(q--) { int tp, pos, l, r, v; cin >> tp; if(tp % 2) { cin >> pos >> v; a[pos] = v; } else { cin >> l >> r >> v; bool ok = 0; for(int i = l; i <= r; i++) { int lc = a[i]; if(lc == v) { cout << i << " " << i << endl; ok = 1; break; } for(int j = i + 1; j <= r; j++) { lc = lca(lc, a[j]); if(lc == v) { ok = 1; cout << i << " " << j << endl; break; } } if(ok) break; } if(!ok) cout << "-1 -1\n"; } } }

Compilation message (stderr)

treearray.cpp: In function 'void dfs(long long int, long long int)':
treearray.cpp:26:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 0; i < g[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
treearray.cpp: At global scope:
treearray.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...