Submission #947865

#TimeUsernameProblemLanguageResultExecution timeMemory
947865nguyennhBirthday gift (IZhO18_treearray)C++14
0 / 100
13 ms23952 KiB
#include<bits/stdc++.h> #define el '\n' using namespace std ; mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); const int MN = 2e5 + 5; const int block_size = 350; vector<int> adj[MN]; set<int> pos[MN] , heavy_ans[MN]; int a[MN] , st[MN] , en[MN] , timer = 0 , tour[MN] , depth[MN]; void dfs(int u , int p){ tour[++timer] = u; st[timer] = u; for ( auto x : adj[u] ){ if (x == p) continue; depth[x] = depth[u] + 1; dfs(x , u); } en[u] = timer; } bool is_anc(int u , int p){ return st[u] >= st[p] && en[u] <= en[p]; } int32_t main (){ ios_base::sync_with_stdio(0); cin.tie(0); int n , m , q; cin >> n >> m >> q; for ( int i = 1 ; i < n ; i++ ){ int u , v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } for ( int i = 1 ; i <= m ; i++ ) cin >> a[i]; for ( int i = 1 ; i <= m ; i++ ){ pos[a[i]].insert(i); } vector<int> heavy; for ( int i = 1 ; i <= n ; i++ ){ if (adj[i].size() > block_size) heavy.push_back(i); } dfs(1 , 0); for ( int i = 0 ; i < heavy.size() ; i++ ){ for ( int j = 1 ; j <= m - 1 ; j++ ){ if (depth[a[j]] == depth[heavy[i]] + 1){ if (is_anc(a[j + 1] , heavy[i])) heavy_ans[heavy[i]].insert(j); } } } while (q--){ int type; cin >> type; if (type == 2){ int l , r , v; cin >> l >> r >> v; auto f = pos[v].lower_bound(l); if (f != pos[v].end()){ if (*f <= r){ cout << *f << ' ' << *f << el; continue; } } if (adj[v].size() <= block_size){ int x = -1 , y = -1; for ( int i = 0 ; i < adj[v].size() ; i++ ){ if (x != -1 && y != -1) break; auto it = pos[adj[v][i]].lower_bound(l); while (it != pos[adj[v][i]].end()){ if (*it > r) break; if (*it - 1 >= l){ if (is_anc(a[*it - 1] , v)){ x = *it , y = *it - 1; break; } } if (*it + 1 <= r){ if (is_anc(a[*it + 1] , v)){ x = *it , y = *it + 1; break; } } ++it; } } if (x > y) swap(x , y); cout << x << " " << y << el; } else { auto it = heavy_ans[v].lower_bound(l); if (it == heavy_ans[v].end() || *it >= r){ cout << -1 << " " << -1 << el; continue; } cout << *it << ' ' << *it + 1 << el; } } else { int p , v; cin >> p >> v; pos[a[p]].erase(pos[a[p]].find(p)); pos[v].insert(p); for ( int i = 0 ; i < heavy.size() ; i++ ){ auto it = heavy_ans[heavy[i]].lower_bound(p); if (it != heavy_ans[heavy[i]].end()){ if (*it == p){ if (depth[a[*it + 1]] == depth[heavy[i]] + 1){ if (!is_anc(v , heavy[i])) heavy_ans[heavy[i]].erase(it); } else { if (!is_anc(v , heavy[i]) || depth[v] == depth[heavy[i]] + 1) heavy_ans[heavy[i]].erase(it); } } } if (*it == p - 1){ if (!is_anc(v , heavy[i])) heavy_ans[heavy[i]].erase(it); } if (depth[a[p - 1]] == depth[heavy[i]] + 1 && is_anc(v , heavy[i])) heavy_ans[heavy[i]].insert(p); } a[p] = v; } } }

Compilation message (stderr)

treearray.cpp: In function 'int32_t main()':
treearray.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for ( int i = 0 ; i < heavy.size() ; i++ ){
      |                     ~~^~~~~~~~~~~~~~
treearray.cpp:71:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for ( int i = 0 ; i < adj[v].size() ; i++ ){
      |                           ~~^~~~~~~~~~~~~~~
treearray.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |       for ( int i = 0 ; i < heavy.size() ; i++ ){
      |                         ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...