Submission #319317

#TimeUsernameProblemLanguageResultExecution timeMemory
319317BeanZBirthday gift (IZhO18_treearray)C++14
100 / 100
1252 ms89444 KiB
// I_Love_LPL #include <bits/stdc++.h> using namespace std; //#define task "A" #define ll int #define endl '\n' const int N = 2e5 + 5; const int mod = 1e9 + 7; const int lg = 18; ll dp[N][lg + 1], dep[N]; vector<ll> node[N]; struct LCA{ ll lca(ll u, ll v){ if (dep[v] < dep[u]) swap(u, v); ll dis = dep[v] - dep[u]; for (int i = lg; i >= 0; i--){ if (dis & (1 << i)){ v = dp[v][i]; } } if (v == u) return u; for (int i = lg; i >= 0; i--){ if (dp[u][i] != dp[v][i]){ v = dp[v][i]; u = dp[u][i]; } } return dp[u][0]; } void dfs(ll u, ll v){ for (int i = 1; i <= lg; i++) dp[u][i] = dp[dp[u][i - 1]][i - 1]; for (auto j : node[u]){ if (j == v) continue; dep[j] = dep[u] + 1; dp[j][0] = u; dfs(j, u); } } } tree; set<ll> two[N], one[N]; ll a[N]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen(".inp", "r")){ freopen(".inp", "r", stdin); freopen(".out", "w", stdout); } ll n, m, q; cin >> n >> m >> q; for (int i = 1; i < n; i++){ ll u, v; cin >> u >> v; node[u].push_back(v); node[v].push_back(u); } tree.dfs(1, 1); for (int i = 1; i <= m; i++) cin >> a[i]; for (int i = 1; i < m; i++) two[tree.lca(a[i], a[i + 1])].insert(i); for (int i = 1; i <= m; i++) one[a[i]].insert(i); while (q--){ ll task; cin >> task; if (task == 1){ ll x, v; cin >> x >> v; one[a[x]].erase(x); one[v].insert(x); if (x < m) two[tree.lca(a[x], a[x + 1])].erase(x); if (x < m) two[tree.lca(v, a[x + 1])].insert(x); if (x > 1) two[tree.lca(a[x - 1], a[x])].erase(x - 1); if (x > 1) two[tree.lca(a[x - 1], v)].insert(x - 1); a[x] = v; } else { ll l, r, v; cin >> l >> r >> v; if (two[v].lower_bound(l) == two[v].end() || *two[v].lower_bound(l) >= r){ if (one[v].lower_bound(l) == one[v].end() || *one[v].lower_bound(l) > r) cout << -1 << " " << -1 << endl; else cout << *one[v].lower_bound(l) << " " << *one[v].lower_bound(l) << endl; } else cout << *two[v].lower_bound(l) << " " << *two[v].lower_bound(l) + 1 << endl; } } } /* 5 4 4 1 2 3 1 3 4 5 3 4 5 2 3 2 1 3 1 1 3 5 2 3 4 5 2 1 3 1 */

Compilation message (stderr)

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