| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 662505 |
2022-11-26T10:21:07 Z |
fatemetmhr |
Prize (CEOI22_prize) |
C++17 |
|
3500 ms |
403036 KB |
// heiy ... ye rooze jadid ...
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
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 = 21;
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(max(ans1, ans2) < k)
return 0;
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
Main.cpp: In function 'int main()':
Main.cpp:206:15: warning: 'good2' may be used uninitialized in this function [-Wmaybe-uninitialized]
206 | v = pre2[v];
| ~~^~~~~~~~~
Main.cpp:199:15: warning: 'good1' may be used uninitialized in this function [-Wmaybe-uninitialized]
199 | v = pre1[v];
| ~~^~~~~~~~~
Main.cpp:229:10: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
229 | solve(n, k, t, root1);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:241:10: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
241 | solve(n, k, t, root2);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1805 ms |
288696 KB |
Output is correct |
| 2 |
Correct |
1859 ms |
290156 KB |
Output is correct |
| 3 |
Correct |
1130 ms |
231904 KB |
Output is correct |
| 4 |
Correct |
1044 ms |
231584 KB |
Output is correct |
| 5 |
Correct |
1072 ms |
232904 KB |
Output is correct |
| 6 |
Correct |
1703 ms |
244476 KB |
Output is correct |
| 7 |
Correct |
1775 ms |
244324 KB |
Output is correct |
| 8 |
Correct |
1658 ms |
244136 KB |
Output is correct |
| 9 |
Correct |
1075 ms |
231864 KB |
Output is correct |
| 10 |
Correct |
1079 ms |
232504 KB |
Output is correct |
| 11 |
Correct |
1116 ms |
231188 KB |
Output is correct |
| 12 |
Correct |
1128 ms |
232320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
661 ms |
132300 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1721 ms |
284352 KB |
Output is correct |
| 2 |
Correct |
1837 ms |
284472 KB |
Output is correct |
| 3 |
Correct |
855 ms |
235352 KB |
Output is correct |
| 4 |
Correct |
900 ms |
235316 KB |
Output is correct |
| 5 |
Correct |
876 ms |
235488 KB |
Output is correct |
| 6 |
Correct |
1357 ms |
245280 KB |
Output is correct |
| 7 |
Correct |
1341 ms |
245272 KB |
Output is correct |
| 8 |
Correct |
1345 ms |
245336 KB |
Output is correct |
| 9 |
Correct |
1190 ms |
244128 KB |
Output is correct |
| 10 |
Correct |
1105 ms |
244072 KB |
Output is correct |
| 11 |
Correct |
1102 ms |
244320 KB |
Output is correct |
| 12 |
Correct |
1077 ms |
244032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3616 ms |
403036 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1377 ms |
186084 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
