| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 943525 |
2024-03-11T14:52:24 Z |
Ahmed57 |
Prize (CEOI22_prize) |
C++17 |
|
1393 ms |
270644 KB |
#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "debug.cpp"
#else
#define debug(...)
#endif
int n;
int bit[500015];
void add(int e,int v){
while(e<=n){
bit[e]+=v;
e+=e&-e;
}
}
int sum(int e){
int su = 0;
while(e>=1){
su+=bit[e];
e-=e&-e;
}
return su;
}
int in[500001][2],outt[500001][2],timer = 0;
int P[500001][2][20];
int PR[500001][20],cost[500001][20];
int DEP[500001];
int dep[500001][2];
vector<int> adj[2][500001],vert[500001];
vector<pair<int,int>> lens[500001],computed[500001];
void dfs(int i,int pr,int ty){
in[i][ty] = ++timer;
P[i][ty][0] = pr;
dep[i][ty] = dep[pr][ty]+1;
for(int j = 1;j<20;j++){
P[i][ty][j] = P[P[i][ty][j-1]][ty][j-1];
}
for(auto j:adj[ty][i]){
if(j==pr)continue;
dfs(j,i,ty);
}
outt[i][ty] = timer;
}
bool comp1(int a,int b){
return in[a][0]<in[b][0];
}
bool comp2(int a,int b){
return in[a][1]<in[b][1];
}
int lca(int a,int b,int ty){
if(dep[a][ty]<dep[b][ty])swap(a,b);
for(int i = 19;i>=0;i--){
if(dep[a][ty]-(1<<i)>=dep[b][ty]){
a = P[a][ty][i];
}
}
if(a==b)return a;
for(int i = 19;i>=0;i--){
if(P[a][ty][i]!=P[b][ty][i]){
a = P[a][ty][i];
b = P[b][ty][i];
}
}
return P[a][ty][0];
}
bool upper(int a,int b,int ty){
return in[a][ty]<=in[b][ty]&&outt[a][ty]>=outt[b][ty];
}
void comp(int i,int pr){
for(auto j:vert[i]){
comp(j,i);
}
sort(vert[i].begin(),vert[i].end(),comp1);
vector<pair<int,int>> lol;
for(auto j:lens[i]){
lol.push_back({in[j.first][0],j.second});
}
sort(lol.begin(),lol.end());
int it = 0;
for(auto j:vert[i]){
while(lol[it].first<in[j][0])it++;
int diff = lol[it].second-sum(lol[it].first);
computed[i].push_back({j,diff});
add(in[j][0],diff);
add(outt[j][0]+1,-diff);
}
}
void dfs2(int i,int pr,int dist){
PR[i][0] = pr;
cost[i][0] = dist;
DEP[i] = DEP[pr]+1;
for(int j = 1;j<20;j++){
PR[i][j] = PR[PR[i][j-1]][j-1];
cost[i][j] = cost[i][j-1]+cost[PR[i][j-1]][j-1];
}
for(auto j:computed[i]){
if(j.first==pr)continue;
dfs2(j.first,i,j.second);
}
}
int lca2(int a,int b,int ty){
if(DEP[a]<DEP[b])swap(a,b);
int summ = 0;
for(int i = 19;i>=0;i--){
if(DEP[a]-(1<<i)>=DEP[b]){
summ+=cost[a][i];
a = PR[a][i];
}
}
if(a==b)return summ;
for(int i = 19;i>=0;i--){
if(PR[a][i]!=PR[b][i]){
summ+=cost[a][i];
summ+=cost[b][i];
a = P[a][ty][i];
b = P[b][ty][i];
}
}
return summ+cost[a][0]+cost[b][0];
}
void query(int a,int b){
cout<<"? "<<a<<" "<<b<<endl;
//int x,y,z,e;
//cin>>x>>y>>z>>e;
//return {x,y,z,e};
}
signed main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int k,g,t;
cin>>n>>k>>g>>t;
int root1 , root2;
for(int i = 1;i<=n;i++){
int x;cin>>x;
if(x==-1){
root1 = i;
}else{
adj[0][x].push_back(i);
adj[0][i].push_back(x);
}
}
for(int i = 1;i<=n;i++){
int x;cin>>x;
if(x==-1){
root2 = i;
}else{
adj[1][x].push_back(i);
adj[1][i].push_back(x);
}
}
dfs(root1,0,0);
timer = 0;
dfs(root2,0,1);
for(int i = 1;i<=k;i++){
cout<<i<<" ";
}
cout<<endl;
vector<int> v;
for(int i = 1;i<=k;i++){
v.push_back(i);
}
sort(v.begin(),v.end(),comp1);
for(int i = 1;i<k;i++){
query(v[i-1],v[i]);
//lens[lca(v[i],v[i-1],0)].push_back({v[i-1],lol[0]});
//lens[lca(v[i],v[i-1],0)].push_back({v[i],lol[1]});
v.push_back(lca(v[i],v[i-1],0));
}
cout<<"!"<<endl;
for(int i = 1;i<k;i++){
int x,y,z,e;cin>>x>>y>>z>>e;
lens[lca(v[i],v[i-1],0)].push_back({v[i-1],x});
lens[lca(v[i],v[i-1],0)].push_back({v[i],y});
}
sort(v.begin(),v.end(),comp1);
v.erase(unique(v.begin(),v.end()),v.end());
vector<int> st;
st.push_back(v[0]);
for(int i = 1;i<v.size();i++){
while(st.size()>1&&!upper(st.back(),v[i],0)){
vert[st[st.size()-2]].push_back(st.back());
st.pop_back();
}
st.push_back(v[i]);
}
while(st.size()>1){
vert[st[st.size()-2]].push_back(st.back());
st.pop_back();
}
timer = 0;
comp(st[0],0);
dfs2(st[0],0,0);
vector<pair<int,int>> queries;
while(t--){
int a,b;cin>>a>>b;
queries.push_back({a,b});
}
for(auto i:queries){
int a = i.first , b = i.second;
cout<<lca2(a,b,0)<<" "<<lca2(a,b,0)<<endl;
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:180:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | for(int i = 1;i<v.size();i++){
| ~^~~~~~~~~
Main.cpp:152:8: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
152 | dfs(root1,0,0);
| ~~~^~~~~~~~~~~
Main.cpp:154:8: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
154 | dfs(root2,0,1);
| ~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1393 ms |
241944 KB |
Output is correct |
| 2 |
Correct |
1336 ms |
251640 KB |
Output is correct |
| 3 |
Runtime error |
887 ms |
270644 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1284 ms |
248348 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
956 ms |
227404 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
811 ms |
255308 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
862 ms |
238444 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
