Submission #662499

#TimeUsernameProblemLanguageResultExecution timeMemory
662499fatemetmhrPrize (CEOI22_prize)C++17
29 / 100
3580 ms406952 KiB
// heiy ... ye rooze jadid ... #include <bits/stdc++.h> using namespace std; typedef long long ll; #define all(x) x.begin(), x.end() #define pb push_back #define fi first #define se second const int maxn5 = 1e6 + 10; const int maxnt = 1e6 + 10; const int lg = 22; ll h[maxn5], ans[maxn5], dis[maxn5], out[maxn5]; vector <pair<int, ll>> adj[maxn5]; int par[lg + 1][maxn5]; pair<int, ll> pr[maxn5], have[maxn5]; int st[maxn5], ti = 0; vector <int> av, adj1[maxn5], adj2[maxn5]; bool mark[maxn5]; int st1[maxn5], st2[maxn5], ti1 = 0, ti2 = 0; ll dd1[maxn5], dd2[maxn5], dd3[maxn5], dd4[maxn5]; int q1[maxn5], q2[maxn5], dp1[maxn5], dp2[maxn5], last1[maxn5], last2[maxn5]; int pre1[maxn5], pre2[maxn5], a[maxn5]; void dfs_lca(int v){ st[v] = ++ti; if(par[0][v] == -1) dis[v] = 0; for(int i = 1; i < lg && par[i - 1][v] != -1; i++) par[i][v] = par[i - 1][par[i - 1][v]]; //cout << "aha " << v << ' ' << h[v] << ' ' << dis[v] << ' ' << par[0][v] << endl; for(auto [u, len] : adj[v]){ h[u] = h[v] + 1; dis[u] = dis[v] + len; par[0][u] = v; dfs_lca(u); } } inline int lca(int a, int b){ if(h[a] < h[b]) swap(a, b); int d = h[a] - h[b]; //cout << "ok " << a << ' ' << b << ' ' << d << ' ' << h[a] << ' ' << h[b] << endl; for(int i = 0; i < lg; i++) if((d >> i)&1) a = par[i][a]; //cout << "and " << a << endl; if(a == b) return a; for(int i = lg - 1; i >= 0; i--) if(par[i][a] != par[i][b]){ a = par[i][a]; b = par[i][b]; } return par[0][a]; } inline void solve(int n, int k, int t, int root){ memset(par, -1, sizeof par); memset(mark, false, sizeof mark); ti = 0; h[root] = dis[root] = 0; dfs_lca(root); for(int i = 0; i < n; i++){ pr[i].fi = -1; pr[i].se = 0; } av.clear(); av.pb(have[0].se); for(int i = 1; i < k; i++){ int v = have[i - 1].se, u = have[i].se; int c = lca(have[i - 1].se, have[i].se); ll d1 = dd1[i], d2 = dd2[i]; //cout << "its " << u << ' ' << v << ' ' << c << endl; mark[u] = mark[v] = mark[c] = true; while(av.size() && h[c] < h[av.back()]){ v = av.back(); av.pop_back(); d1 -= pr[v].se; //cout << "pop " << v << endl; } //cout << "ok " << v << ' ' << u << ' ' << c << ' ' << d1 << endl; if(v != c){ d1 += pr[v].se; if(av.size() && av.back() != c){ pr[c] = {av.back(), pr[v].se - d1}; //cout << "oh par " << pr[c].fi << ' ' << pr[c].se << endl; } if(av.empty() || av.back() != c) av.pb(c); pr[v] = {c, d1}; //cout << "here " << d1 << endl; } if(c != u){ av.pb(u); pr[u] = {c, d2}; } } for(int i = 0; i < n; i++) adj[i].clear(); for(int i = 0; i < n; i++){ if(pr[i].fi != -1) adj[pr[i].fi].pb({i, pr[i].se}); else if(mark[i]) root = i; } //cout << "SECOND TREE " << endl; memset(par, -1, sizeof par); h[root] = 0; //return 0; dfs_lca(root); for(int i = 0; i < t; i++){ int a = q1[i], b = q2[i]; int c = lca(a, b); ans[i] = dis[a] + dis[b] - 2 * dis[c]; } } void dfs_st2(int v){ st2[v] = ti2++; for(auto u : adj2[v]) dfs_st2(u); } void dfs_st1(int v){ st1[v] = ti1++; for(auto u : adj1[v]) dfs_st1(u); } inline bool cmp(int i, int j){return st1[i] < st1[j];} int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, k, q, t; cin >> n >> k >> q >> t; int root1, root2; for(int i = 0; i < n; i++){ int p; cin >> p; p--; if(p != -2) adj1[p].pb(i); else root1 = i; } for(int i = 0; i < n; i++){ int p; cin >> p; p--; if(p != -2) adj2[p].pb(i); else root2 = i; } dfs_st1(root1); dfs_st2(root2); for(int i = 0; i < n; i++) a[i] = i; sort(a, a + n, cmp); // bar hasbe st1 fill(dp1, dp1 + n + 5, 1e9); fill(dp2, dp2 + n + 5, 1e9); int ans1 = 0, ans2 = 0; int good1, good2; memset(last1, -1, sizeof last1); memset(last2, -1, sizeof last2); for(int i = 0; i < n; i++){ int p1 = lower_bound(dp1 + 1, dp1 + n + 3, st2[a[i]]) - dp1; int p2 = lower_bound(dp2 + 1, dp2 + n + 3, -st2[a[i]]) - dp2; pre1[i] = last1[p1 - 1]; pre2[i] = last2[p2 - 1]; dp1[p1] = st2[a[i]]; dp2[p2] = -st2[a[i]]; last1[p1] = last2[p2] = i; if(p1 > ans1){ good1 = i; ans1 = p1; } if(p2 > ans2){ good2 = i; ans2 = p2; } } //cout << "ok " << ans1 << ' ' << ans2 << endl; if(ans1 > ans2){ int v = good1; for(int i = 0; i < k; i++){ have[i] = {0, a[v]}; v = pre1[v]; } } else{ int v = good2; for(int i = 0; i < k; i++){ have[i] = {0, a[v]}; v = pre2[v]; } } for(int i = 0; i < k; i++){ cout << have[i].se + 1 << ' '; } cout << endl; for(int i = 1; i < k; i++){ cout << "? " << have[i - 1].se + 1 << ' ' << have[i].se + 1 << '\n'; } cout << "!" << endl; for(int i = 1; i < k; i++) cin >> dd1[i] >> dd2[i] >> dd3[i] >> dd4[i]; for(int i = 0; i < t; i++){ cin >> q1[i] >> q2[i]; q1[i]--; q2[i]--; } for(int i = 0; i < n; i++){ adj[i].clear(); for(auto u : adj1[i]) adj[i].pb({u, 1}); } solve(n, k, t, root1); for(int i = 0; i < t; i++) out[i] = ans[i]; for(int i = 0; i < n; i++){ adj[i].clear(); for(auto u : adj2[i]) adj[i].pb({u, 1}); } for(int i = 1; i < k; i++){ swap(dd1[i], dd3[i]); swap(dd2[i], dd4[i]); } solve(n, k, t, root2); for(int i = 0; i < t; i++) cout << out[i] << ' ' << ans[i] << '\n'; cout << endl; } /* 9 3 2 3 2 -1 2 1 1 5 1 4 5 9 4 5 5 7 3 -1 3 7 0 3 0 3 3 1 3 1 */

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:202:15: warning: 'good2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  202 |             v = pre2[v];
      |             ~~^~~~~~~~~
Main.cpp:195:15: warning: 'good1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  195 |             v = pre1[v];
      |             ~~^~~~~~~~~
Main.cpp:225:10: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  225 |     solve(n, k, t, root1);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:237:10: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  237 |     solve(n, k, t, root2);
      |     ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...