Submission #521897

#TimeUsernameProblemLanguageResultExecution timeMemory
521897KalashnikovBirthday gift (IZhO18_treearray)C++17
56 / 100
4098 ms38176 KiB
#include <bits/stdc++.h> #define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) #define all(a) a.begin() , a.end() #define F first #define S second using namespace std; using ll = long long; const int N = 2e5+5 , inf = 2e9 + 7; const ll INF = 1e18 , mod = 1e9+7 , P = 6547; int a[N]; vector<int> g[N]; int tin[N] , tout[N] , timer; int up[N][20]; void dfs(int v = 1, int p = 0) { up[v][0] = p; for(int i = 1; i < 20; i ++) { up[v][i] = up[up[v][i-1]][i-1]; } tin[v] = ++timer; for(auto to: g[v]) { if(to != p) { dfs(to , v); } } tout[v] = ++timer; } bool upper(int a , int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; } int lca(int a , int b) { if(upper(a , b)) return a; if(upper(b , a)) return b; for(int i = 19; i >= 0; i --) { if(up[a][i] && !upper(up[a][i] , b)) { a = up[a][i]; } } return up[a][0]; } void solve(int tc) { int n , m , q; cin >> n >> m >> q; for(int i = 1; i < n; i ++) { int a , b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } dfs(); for(int i = 1; i <= m; i ++) { cin >> a[i]; } while(q --) { int t; cin >> t; if(t == 2) { int l , r , v; cin >> l >> r >> v; int fnd = 0; int p = a[l] , last = l; for(int i = l; i <= r; i ++) { if(!upper(v , a[i])) { p = a[i+1]; last = i+1; continue; } p = lca(p , a[i]); if(p == v) { fnd = 1; cout << last << ' ' << i << '\n'; break; } } if(!fnd) { cout << "-1 -1\n"; continue; } } else { int pos , val; cin >> pos >> val; a[pos] = val; } } } /* */ main() { ios; int tt = 1 , tc = 0; // cin >> tt; while(tt --) { solve(++tc); } return 0; }

Compilation message (stderr)

treearray.cpp:102:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  102 | 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...