Submission #608790

#TimeUsernameProblemLanguageResultExecution timeMemory
608790messiuuuuuBirthday gift (IZhO18_treearray)C++14
100 / 100
1259 ms85504 KiB
///https://codeforces.com/group/Chft8wRRWW/contest/391796/problem/D ///https://oj.uz/problem/submit/IZhO18_treearray #include<bits/stdc++.h> #define task "C" #define ll long long #define ld long double #define fi first #define se second #define pb push_back using namespace std; const int MAXN = 2e5 + 5; const ll INF = 1e18 + 5; const int LOGN = 18; int n, m, q; vector<int> Adj[MAXN]; int a[MAXN]; void Input() { cin >> n >> m >> q; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; Adj[u].pb(v); Adj[v].pb(u); } for (int i = 1; i <= m; i++) { cin >> a[i]; } } int P[MAXN][LOGN], dep[MAXN]; void DFS(int u, int par) { for (int v : Adj[u]) { if (v == par) { continue; } dep[v] = dep[u] + 1; P[v][0] = u; DFS(v, u); } } int LCA(int u, int v) { if (dep[u] > dep[v]) swap(u, v); for (int i = LOGN - 1; i >= 0; i--) { if (dep[u] <= dep[P[v][i]]) { v = P[v][i]; } } for (int i = LOGN - 1; i >= 0; i--) { if (P[u][i] != P[v][i]) { u = P[u][i]; v = P[v][i]; } } if (u != v) { u = P[u][0]; } return u; } set<int> S[MAXN], S1[MAXN]; void Solve() { dep[1] = 1; DFS(1, 0); for (int i = 1; i < LOGN; i++) for (int j = 1; j <= n; j++) P[j][i] = P[P[j][i - 1]][i - 1]; for (int i = 1; i <= m; i++) { S[a[i]].insert(i); if (i < m) S1[LCA(a[i], a[i + 1])].insert(i); } while (q-- > 0) { int t, l, r; cin >> t >> l >> r; if (t == 1) { S[a[l]].erase(l); S[r].insert(l); if (l < m) { S1[LCA(a[l], a[l + 1])].erase(l); S1[LCA(r, a[l + 1])].insert(l); } if (l > 1) { S1[LCA(a[l - 1], a[l])].erase(l - 1); S1[LCA(a[l - 1], r)].insert(l - 1); } a[l] = r; } else { int k; cin >> k; auto it = S[k].lower_bound(l); if (it != S[k].end() && *it <= r) { cout << *it << ' ' << *it << '\n'; } else { it = S1[k].lower_bound(l); if (it != S1[k].end() && *it + 1 <= r) { cout << *it << ' ' << *it + 1 << '\n'; } else cout << -1 << ' ' << -1 << '\n'; } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); if (fopen(task".INP","r")) { freopen(task".INP","r",stdin); //freopen(task".OUT","w",stdout); } Input(); Solve(); }

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...