Submission #993510

#TimeUsernameProblemLanguageResultExecution timeMemory
993510Savu_Stefan_CatalinPrize (CEOI22_prize)C++14
10 / 100
2487 ms637688 KiB
#include <iostream> #include <algorithm> #include <vector> #define int long long using namespace std; const int NMAX=1e6+505; int cnt,ine[2][NMAX+5],lv[2][NMAX+5],n,t[2][NMAX+5],cen[2],invine[2][NMAX+5],k,q,T,id[NMAX+5],dp[NMAX+5],rmq[2][25][NMAX+5],imp[NMAX+5],invid[NMAX+5],rr[2][NMAX+5]; vector <int> v[2][NMAX+5]; pair<pair<int,int>,pair<int,int>> ras[NMAX+5]; int sz[NMAX+5],ap[NMAX+5],tt[NMAX+5],tv[NMAX+5],dp2[NMAX+5]; vector <pair<int,int>> vv[NMAX+5]; void dfs(int nod,int tata,int ind) { ++cnt; ine[ind][nod]=cnt; lv[ind][nod]=lv[ind][tata]+1; for (int i=0;i<v[ind][nod].size();++i) { dfs(v[ind][nod][i],nod,ind); } } void read(int ind) { for (int i=1;i<=n;++i) { cin>>t[ind][i]; if (t[ind][i]==-1) cen[ind]=i; else {v[ind][t[ind][i]].push_back(i);} } cnt=0; dfs(cen[ind],0,ind); for (int i=1;i<=n;++i) { invine[ind][ine[ind][i]]=i; } } int cmp(int x,int y) { return ine[1][x]<ine[1][y]; } int lca(int x,int y,int ind) { if (lv[ind][x]>lv[ind][y]) swap(x,y); for (int i=20;i>=0;--i) {if (lv[ind][x]+(1<<i)<=lv[ind][y]) {y=rmq[ind][i][y];}} if (x==y) return x; for (int i=20;i>=0;--i) {if (rmq[ind][i][x]!=rmq[ind][i][y]) {x=rmq[ind][i][x]; y=rmq[ind][i][y];}} return t[ind][x]; } void bfs(int nod) { sz[nod]=ap[nod]; for (int i=0;i<v[1][nod].size();++i) { bfs(v[1][nod][i]); sz[nod]+=sz[v[1][nod][i]]; } } void mfs(int nod,int tata) { for (int i=0;i<v[1][nod].size();++i) { if (sz[nod]==sz[v[1][nod][i]]) {mfs(v[1][nod][i],tata); return ;} } vv[tata].push_back({nod,0}); tt[nod]=tata; for (int i=0;i<v[1][nod].size();++i) { if (sz[v[1][nod][i]]) { mfs(v[1][nod][i],nod); } } } int findfirst(int x) { if (ap[x]==1) return x; return findfirst(vv[x][0].first); } int findlast(int x) { if (vv[x].size()==0) return x; return findlast(vv[x][vv[x].size()-1].first); } int sum(int x,int stop) { if (x==stop) return 0; return tv[x]+sum(tt[x],stop); } void lfs(int nod) { if (vv[nod].size()==0) { return ; } for (int i=0;i<vv[nod].size();++i) { lfs(vv[nod][i].first); if (i) { int x=findlast(vv[nod][i-1].first); int y=findfirst(vv[nod][i].first); int xx=invid[x],yy=invid[y]; vv[nod][i-1].second=ras[xx].second.first-sum(x,vv[nod][i-1].first); tv[vv[nod][i-1].first]=vv[nod][i-1].second; vv[nod][i].second=ras[xx].second.second-sum(y,vv[nod][i].first); tv[vv[nod][i].first]=vv[nod][i].second; } } if (vv[nod].size()==1) { int xx=invid[nod]; vv[nod][0].second=ras[xx].second.second; tv[vv[nod][0].first]=vv[nod][0].second; } } void ylf(int nod) { for (int i=0;i<vv[nod].size();++i) { dp2[vv[nod][i].first]=dp2[nod]+vv[nod][i].second; ylf(vv[nod][i].first); } } void solve1() { for (int i=1;i<=k;++i) { ap[id[i]]=1; } bfs(cen[1]); mfs(cen[1],0); int ce=vv[0][0].first; lfs(ce); ylf(ce); } void solve0() { int ii=0; for (int i=1;i<=k;++i) { if (id[i]==cen[0]) {ii=i;} } dp[ii]=0; for (int i=ii+1;i<=k;++i) { dp[id[i]]=dp[id[i-1]]-ras[i-1].first.first+ras[i-1].first.second; } for (int i=ii-1;i>=1;--i) { dp[id[i]]=dp[id[i+1]]-ras[i].first.second+ras[i].first.first; } } void makermq(int ind) { for (int i=1;i<=n;++i) { if (t[ind][i]==-1) rmq[ind][0][i]=0; else rmq[ind][0][i]=t[ind][i]; } for (int j=1;j<=20;++j) { for (int i=1;i<=n;++i) { rmq[ind][j][i]=rmq[ind][j-1][rmq[ind][j-1][i]]; } } } signed main() { cin>>n>>k>>q>>T; read(0); read(1); for (int i=1;i<=k;++i) { imp[i]=invine[0][i]; cout<<imp[i]<<" "; } cout<<endl; for (int i=1;i<=k;++i) { id[i]=imp[i]; } sort(id+1,id+k+1,cmp); for (int i=1;i<=k;++i) { invid[id[i]]=i; } for (int i=1;i<k;++i) { cout<<"? "<<id[i]<<" "<<id[i+1]<<endl; } cout<<"!"<<endl; for (int i=1;i<k;++i) { cin>>ras[i].first.first>>ras[i].first.second>>ras[i].second.first>>ras[i].second.second; } solve0(); makermq(0); makermq(1); solve1(); for (int i=1;i<=T;++i) { int x,y; cin>>x>>y; rr[1][i]=dp2[x]+dp2[y]-2*dp2[lca(x,y,1)]; rr[0][i]=dp[x]+dp[y]-2*dp[lca(x,y,0)]; } for (int i=1;i<=T;++i) cout<<rr[0][i]<<" "<<rr[1][i]<<'\n'; cout.flush(); return 0; }

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int, long long int, long long int)':
Main.cpp:17:19: 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]
   17 |     for (int i=0;i<v[ind][nod].size();++i)
      |                  ~^~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void bfs(long long int)':
Main.cpp:52:19: 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]
   52 |     for (int i=0;i<v[1][nod].size();++i)
      |                  ~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'void mfs(long long int, long long int)':
Main.cpp:60:19: 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]
   60 |     for (int i=0;i<v[1][nod].size();++i)
      |                  ~^~~~~~~~~~~~~~~~~
Main.cpp:66:19: 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]
   66 |     for (int i=0;i<v[1][nod].size();++i)
      |                  ~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'void lfs(long long int)':
Main.cpp:95:19: 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]
   95 |     for (int i=0;i<vv[nod].size();++i)
      |                  ~^~~~~~~~~~~~~~~
Main.cpp:102:29: warning: unused variable 'yy' [-Wunused-variable]
  102 |             int xx=invid[x],yy=invid[y];
      |                             ^~
Main.cpp: In function 'void ylf(long long int)':
Main.cpp:118:19: 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]
  118 |     for (int i=0;i<vv[nod].size();++i)
      |                  ~^~~~~~~~~~~~~~~
#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...