Submission #943589

#TimeUsernameProblemLanguageResultExecution timeMemory
943589Ahmed57Prize (CEOI22_prize)C++17
10 / 100
2123 ms656748 KiB
#include "bits/stdc++.h" using namespace std; #define int long long #ifdef LOCAL #include "debug.cpp" #else #define debug(...) #endif int n; int bit[2][600015]; void add(int e,int v,int ty){ while(e<=n){ bit[ty][e]+=v; e+=e&-e; } } int sum(int e,int ty){ int su = 0; while(e>=1){ su+=bit[ty][e]; e-=e&-e; } return su; } int in[600001][2],outt[600001][2],timer = 0; int P[600001][2][20]; int PR[600001][2][20],cost[600001][2][20]; int DEP[600001][2]; int dep[600001][2]; vector<int> adj[2][600001],vert[600001][2]; vector<pair<int,int>> lens[600001][2],computed[600001][2]; 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,int ty){ for(auto j:vert[i][ty]){ comp(j,i,ty); } sort(vert[i][ty].begin(),vert[i][ty].end(),comp1); vector<pair<int,int>> lol; for(auto j:lens[i][ty]){ if(j.first!=i)lol.push_back({in[j.first][ty],j.second}); } sort(lol.begin(),lol.end()); int it = 0; for(auto j:vert[i][ty]){ if(it==lol.size()){ cout<<"a333"<<endl; exit(0); } while(lol[it].first<in[j][ty])it++; if(it==lol.size()){ cout<<"a333"<<endl; exit(0); } int diff = lol[it].second-sum(lol[it].first,ty); computed[i][ty].push_back({j,diff}); add(in[j][ty],diff,ty); add(outt[j][ty]+1,-diff,ty); } } void dfs2(int i,int pr,int dist,int ty){ PR[i][ty][0] = pr; cost[i][ty][0] = dist; DEP[i][ty] = DEP[pr][ty]+1; for(int j = 1;j<20;j++){ PR[i][ty][j] = PR[PR[i][ty][j-1]][ty][j-1]; cost[i][ty][j] = cost[i][ty][j-1]+cost[PR[i][ty][j-1]][ty][j-1]; } for(auto j:computed[i][ty]){ if(j.first==pr)continue; dfs2(j.first,i,j.second,ty); } } int lca2(int a,int b,int ty){ if(DEP[a][ty]<DEP[b][ty])swap(a,b); int summ = 0; for(int i = 19;i>=0;i--){ if(DEP[a][ty]-(1<<i)>=DEP[b][ty]){ summ+=cost[a][ty][i]; a = PR[a][ty][i]; } } if(a==b)return summ; for(int i = 19;i>=0;i--){ if(PR[a][ty][i]!=PR[b][ty][i]){ summ+=cost[a][ty][i]; summ+=cost[b][ty][i]; a = PR[a][ty][i]; b = PR[b][ty][i]; } } return summ+cost[a][ty][0]+cost[b][ty][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}; } vector<pair<int,int>> queries; vector<int> v1,st1,v2,st2;set<int> loli,loli2; signed main() { ios_base::sync_with_stdio(false);cin.tie(0); //freopen("prize.in.1c","r",stdin); 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 = n-k+1;i<=n;i++){ cout<<i<<" "; } cout<<endl; for(int i = n-k+1;i<=n;i++){ v1.push_back(i); v2.push_back(i); } sort(v1.begin(),v1.end(),comp1); sort(v2.begin(),v2.end(),comp2); for(int i = 1;i<k;i++){ query(v1[i-1],v1[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]}); v1.push_back(lca(v1[i],v1[i-1],0)); } for(int i = 1;i<k;i++){ query(v2[i-1],v2[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]}); v2.push_back(lca(v2[i],v2[i-1],1)); } cout<<"!"<<endl; for(int i = 1;i<k;i++){ int x,y,z,e;cin>>x>>y>>z>>e; lens[lca(v1[i],v1[i-1],0)][0].push_back({v1[i-1],x}); lens[lca(v1[i],v1[i-1],0)][0].push_back({v1[i],y}); } for(int i = 1;i<k;i++){ int x,y,z,e;cin>>x>>y>>z>>e; lens[lca(v2[i],v2[i-1],1)][1].push_back({v2[i-1],z}); lens[lca(v2[i],v2[i-1],1)][1].push_back({v2[i],e}); } sort(v1.begin(),v1.end(),comp1); for(auto i:v1)loli.insert(i); v1.clear(); for(auto i:loli)v1.push_back(i); sort(v1.begin(),v1.end(),comp1); st1.push_back(v1[0]); for(int i = 1;i<v1.size();i++){ while(st1.size()>1&&!upper(st1.back(),v1[i],0)){ vert[st1[st1.size()-2]][0].push_back(st1.back()); st1.pop_back(); } st1.push_back(v1[i]); } while(st1.size()>1){ vert[st1[st1.size()-2]][0].push_back(st1.back()); st1.pop_back(); } sort(v2.begin(),v2.end(),comp2); for(auto i:v2)loli2.insert(i); v2.clear(); for(auto i:loli2)v2.push_back(i); sort(v2.begin(),v2.end(),comp2); st2.push_back(v2[0]); for(int i = 1;i<v2.size();i++){ while(st2.size()>1&&!upper(st2.back(),v2[i],1)){ vert[st2[st2.size()-2]][1].push_back(st2.back()); st2.pop_back(); } st2.push_back(v2[i]); } while(st2.size()>1){ vert[st2[st2.size()-2]][1].push_back(st2.back()); st2.pop_back(); } timer = 0; comp(st1[0],0,0); comp(st2[0],0,1); dfs2(st1[0],0,0,0); dfs2(st2[0],0,0,1); 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,1)<<endl; } }

Compilation message (stderr)

Main.cpp: In function 'void comp(long long int, long long int, long long int)':
Main.cpp:84:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         if(it==lol.size()){
      |            ~~^~~~~~~~~~~~
Main.cpp:89:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         if(it==lol.size()){
      |            ~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:206:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |     for(int i = 1;i<v1.size();i++){
      |                   ~^~~~~~~~~~
Main.cpp:223:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |     for(int i = 1;i<v2.size();i++){
      |                   ~^~~~~~~~~~
Main.cpp:164:8: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  164 |     dfs(root1,0,0);
      |     ~~~^~~~~~~~~~~
Main.cpp:166:8: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  166 |     dfs(root2,0,1);
      |     ~~~^~~~~~~~~~~
#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...