Submission #587281

#TimeUsernameProblemLanguageResultExecution timeMemory
587281mosiashvililukaIdeal city (IOI12_city)C++14
100 / 100
179 ms23908 KiB
#include<bits/stdc++.h> using namespace std; long long a,b,c,d,e,i,j,ii,jj,zx,xc,cnt,lf[100009],rg[100009],id[100009],X[100009],Y[100009],J,I,mod=1000000000LL,pas,dp[100009]; vector <pair <long long, long long> > v[100009]; map <long long, vector <pair <long long, long long> > > m; map <long long, vector <pair <long long, long long> > >::iterator it; map <pair <long long, long long>, long long> n,EDGE; map <pair <long long, long long>, long long>::iterator tt; vector <pair <long long, long long> > vv; long long jami(long long q){ long long qw=q*(q+1)/2LL;qw%=mod; return qw; } void dfsst(int q, int w){ dp[q]=rg[q]-lf[q]+1; for(vector <pair <long long, long long> >::iterator it=v[q].begin(); it!=v[q].end(); it++){ if((*it).first==w) continue; dfsst((*it).first,q); dp[q]+=dp[(*it).first]; } } void dfs(int q, int w){ for(vector <pair <long long, long long> >::iterator it=v[q].begin(); it!=v[q].end(); it++){ if((*it).first==w) continue; dfs((*it).first,q); zx=dp[(*it).first]*(a-dp[(*it).first]);zx%=mod; pas+=zx;pas%=mod; } } long long fun(long long l, long long r, long long L, long long R){ long long jm=0; /*for(long long h=L; h<=R; h++){ if(l<=h&&h<=r){ jm+=jami(h-l)+jami(r-h)+r-l+1;jm%=mod; continue; } if(r<h){ jm+=jami(h-l-(h-r))+(r-l+1)*(h-r+1);jm%=mod; continue; } if(l>h){ jm+=jami(r-h-(l-h))/+(r-l+1)*(l-h+1);jm%=mod; continue; } }*/ jm=(r-l+1)*(R-L+1);jm%=mod; return jm; } int DistanceSum(int NN, int *XX, int *YY) { a=NN; for(i=1; i<=a; i++){ c=XX[i-1];d=YY[i-1]; X[i]=c;Y[i]=d; m[c].push_back({d,i}); } for(it=m.begin(); it!=m.end(); it++){ sort((*it).second.begin(),(*it).second.end()); } for(it=m.begin(); it!=m.end(); it++){ vv=(*it).second; cnt++; id[vv[0].second]=cnt; lf[cnt]=rg[cnt]=vv[0].first; i=(*it).first;j=vv[0].first; n[{i,j}]=cnt; for(jj=1; jj<vv.size(); jj++){ if(vv[jj-1].first+1==vv[jj].first){ rg[cnt]=vv[jj].first; }else{ cnt++; lf[cnt]=rg[cnt]=vv[jj].first; } id[vv[jj].second]=cnt; i=(*it).first;j=vv[jj].first; n[{i,j}]=cnt; } } for(it=m.begin(); it!=m.end(); it++){ vv=(*it).second; for(J=0; J<vv.size(); J++){ i=(*it).first;j=vv[J].first; c=n[{i,j}]; ii=i-1;jj=j; d=n[{ii,jj}]; if(d==0) continue; //cout<<c<<" EDGE "<<d<<"\n"; /*for(I=lf[c]; I<=rg[c]; I++){ zx=jami(I-lf[d])+jami(rg[d]-I)+rg[d]-lf[d]+1;zx%=mod; EDGE[{c,d}]+=zx;EDGE[{c,d}]%=mod; }*/ if(EDGE[{c,d}]==1) continue; EDGE[{c,d}]=1; e=fun(lf[c],rg[c],lf[d],rg[d]); v[c].push_back({d,e}); v[d].push_back({c,e}); //cout<<c<<" "<<d<<" "<<e<<" FR "<<lf[c]<<" "<<rg[c]<<" "<<lf[d]<<" "<<rg[d]<<"\n"; } } /*for(tt=EDGE.begin(); tt!=EDGE.end(); tt++){ v[(*tt).first.first].push_back({(*tt).first.second,(*tt).second}); v[(*tt).first.second].push_back({(*tt).first.first,(*tt).second}); cout<<(*tt).first.first<<" "<<(*tt).first.second<<" "<<(*tt).second<<"\n"; }*/ dfsst(1,0); dfs(1,0); // m.clear();cnt=0;n.clear();EDGE.clear(); for(i=0; i<=a+1; i++){ v[i].clear(); } for(i=1; i<=a; i++){ c=XX[i-1];d=YY[i-1]; swap(c,d); X[i]=c;Y[i]=d; m[c].push_back({d,i}); } for(it=m.begin(); it!=m.end(); it++){ sort((*it).second.begin(),(*it).second.end()); } for(it=m.begin(); it!=m.end(); it++){ vv=(*it).second; cnt++; id[vv[0].second]=cnt; lf[cnt]=rg[cnt]=vv[0].first; i=(*it).first;j=vv[0].first; n[{i,j}]=cnt; for(jj=1; jj<vv.size(); jj++){ if(vv[jj-1].first+1==vv[jj].first){ rg[cnt]=vv[jj].first; }else{ cnt++; lf[cnt]=rg[cnt]=vv[jj].first; } id[vv[jj].second]=cnt; i=(*it).first;j=vv[jj].first; n[{i,j}]=cnt; } } for(it=m.begin(); it!=m.end(); it++){ vv=(*it).second; for(J=0; J<vv.size(); J++){ i=(*it).first;j=vv[J].first; c=n[{i,j}]; ii=i-1;jj=j; d=n[{ii,jj}]; if(d==0) continue; //cout<<c<<" EDGE "<<d<<"\n"; /*for(I=lf[c]; I<=rg[c]; I++){ zx=jami(I-lf[d])+jami(rg[d]-I)+rg[d]-lf[d]+1;zx%=mod; EDGE[{c,d}]+=zx;EDGE[{c,d}]%=mod; }*/ if(EDGE[{c,d}]==1) continue; EDGE[{c,d}]=1; e=fun(lf[c],rg[c],lf[d],rg[d]); v[c].push_back({d,e}); v[d].push_back({c,e}); //cout<<c<<" "<<d<<" "<<e<<" SC "<<lf[c]<<" "<<rg[c]<<" "<<lf[d]<<" "<<rg[d]<<"\n"; } } /*for(tt=EDGE.begin(); tt!=EDGE.end(); tt++){ v[(*tt).first.first].push_back({(*tt).first.second,(*tt).second}); v[(*tt).first.second].push_back({(*tt).first.first,(*tt).second}); cout<<(*tt).first.first<<" "<<(*tt).first.second<<" "<<(*tt).second<<"\n"; }*/ dfsst(1,0); dfs(1,0); // int PAS=pas; return PAS; }

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:66:21: 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]
   66 |         for(jj=1; jj<vv.size(); jj++){
      |                   ~~^~~~~~~~~~
city.cpp:80: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]
   80 |         for(J=0; J<vv.size(); J++){
      |                  ~^~~~~~~~~~
city.cpp:135:21: 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]
  135 |         for(jj=1; jj<vv.size(); jj++){
      |                   ~~^~~~~~~~~~
city.cpp:149: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]
  149 |         for(J=0; J<vv.size(); J++){
      |                  ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...