oj.uz

Submission #67452

# Submission time Handle Problem Language Result Execution time Memory
67452 2018-08-14T10:04:03 Z WA_TLE Ideal city (IOI12_city) C++14
100 / 100
 680 ms 17984 KB 
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000000;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
pair<int,int> masu[100000];
int Lcdata[100000];
int Rcdata[100000];
int Ucdata[100000];
int Dcdata[100000];
int Ba[100000];
int Da[100000];
int Do[100000];
//LRUDの場所も初めに持っておく
//#include"grader.cpp"
int DistanceSum(int N,int *Xdata,int *Ydata){
	int *Lc=Lcdata;
	int *Rc=Rcdata;
	int *Uc=Ucdata;
	int *Dc=Dcdata;
	int *X=Xdata;
	int *Y=Ydata;
	//O(nlogn) かなり無理がある
	llint ans=0,i,bunum=1;
	vector<int>lis(N);
	queue<tuple<int,int,int>>yaru;
	for(i=0;i<N;i++){lis[i]=i;masu[i]=mp(X[i],Y[i]);}
	sort(masu,masu+N);
	for(i=0;i<N;i++){X[i]=masu[i].fir;Y[i]=masu[i].sec;}
	for(i=0;i<N;i++){
		pair<int,int> Lmo=mp(masu[i].fir-1,masu[i].sec);
		if((*lower_bound(masu,masu+N,Lmo))==Lmo){
			Lc[i]=(lower_bound(masu,masu+N,Lmo)-masu);}
		else{Lc[i]=-1;}
		pair<int,int> Rmo=mp(masu[i].fir+1,masu[i].sec);
		if((*lower_bound(masu,masu+N,Rmo))==Rmo){
			Rc[i]=(lower_bound(masu,masu+N,Rmo)-masu);}
		else{Rc[i]=-1;}
		pair<int,int> Umo=mp(masu[i].fir,masu[i].sec-1);
		if((*lower_bound(masu,masu+N,Umo))==Umo){
			Uc[i]=(lower_bound(masu,masu+N,Umo)-masu);}
		else{Uc[i]=-1;}
		pair<int,int> Dmo=mp(masu[i].fir,masu[i].sec+1);
		if((*lower_bound(masu,masu+N,Dmo))==Dmo){
			Dc[i]=(lower_bound(masu,masu+N,Dmo)-masu);}
		else{Dc[i]=-1;}
	}
	yaru.push(mt(0,N,0));
	mt19937 engine(1333);
	while(yaru.size()){
		int sta=get<0>(yaru.front());
		int num=get<1>(yaru.front());
		int Q=get<2>(yaru.front());
		//cerr<<"sta,num,Q"<<sta<<num<<Q<<endl;
		
		if(engine()%2){
			swap(Lc,Uc);
			swap(Rc,Dc);
			swap(X,Y);
		}
		yaru.pop();
		if(num==1){continue;}
		//if(num==2){ans++;continue;}
		//if(num==3){ans+=4;continue;}
		//木を作って分割線を引く
		vector<int>doco;
		vector<vector<int>>go;
		vector<int>siz;
		vector<int>oya;
		int dasu=0;
		//cerr<<"de"<<__LINE__<<endl;
		for(i=sta;i<sta+num;i++){
			//代表点はどこですか を決める
			int t=lis[i];
			//cerr<<"t="<<t;
			if(Lc[t]<0||Ba[Lc[t]]!=Q){Da[t]=doco.size();siz.pub(1);doco.pub(t);}//はい 代表点です
			else{Da[t]=Da[Lc[t]];siz[Da[t]]++;}
		}
		//cerr<<endl;
		//for(i=sta;i<sta+num;i++){cerr<<"da[i]="<<Da[lis[i]]<<endl;}
		go.res(doco.size());
		//cerr<<"de"<<__LINE__<<endl;
		for(i=0;i<doco.size();i++){
			int it=doco[i];
			if(Uc[it]>=0&&Ba[Uc[it]]==Q){
				int tai=Da[Uc[it]];
				go[Da[it]].pub(tai);
				go[tai].pub(Da[it]);
			}
			if(Dc[it]>=0&&Ba[Dc[it]]==Q&&Da[Dc[it]]!=Dc[it]){
				int tai=Da[Dc[it]];
				go[Da[it]].pub(tai);
				go[tai].pub(Da[it]);
			}
		}
		//cerr<<"de"<<__LINE__<<endl;
		//木が完成した
		oya.res(doco.size());
		for(auto &it:oya){it=-999;}
		oya[0]=-1;
		deque<int>dfque;dfque.pub(0);
		int tgi=0;
		while(tgi<dfque.size()){
			int ter=dfque[tgi];tgi++;
			for(auto it:go[ter]){
				if(oya[it]!=-999){continue;}
				oya[it]=ter;
				dfque.pub(it);
			}
		}
		REV(dfque);
		for(auto it:dfque){
			if(oya[it]==-1){continue;}
			siz[oya[it]]+=siz[it];
		}
		//cerr<<"de"<<__LINE__<<endl;
		//cerr<<"oya[1]="<<oya[1]<<endl;
		pair<int,int>sai=mp(0,-999);//最適な分割点
		
		for(i=0;i<doco.size();i++){maxeq(sai,mp(min(siz[i],siz[0]-siz[i]),(int)i));}
		int has=sai.sec,hbs=oya[sai.sec];
		//cerr<<"ha,hb="<<has<<hbs<<endl;
		if(hbs<0){yaru.push(mt(sta,num,Q));continue;}
		has=doco[has];
		hbs=doco[hbs];
		if(X[has]>X[hbs]){swap(has,hbs);}
		int Xsa=X[hbs]-X[has];
		while(Xsa--){has=Rc[has];}
		
		int naga=0;
		//ここでDaの意味を変更する スタートからの距離にする
		//Doはどこが一番近いですか にする
		queue<int>que;
		for(i=sta;i<sta+num;i++){
			int t=lis[i];
			Da[t]=mod;
			Do[t]=mod;
		}
	
		//cerr<<"has="<<has<<"hbs=="<<hbs<<endl;
		while(-1){
			que.push(has);Da[has]=0;Do[has]=naga;naga++;
			que.push(hbs);Da[hbs]=0;Do[hbs]=naga;naga++;
			if(Rc[has]<0||Ba[Rc[has]]!=Q){break;}has=Rc[has];
			if(Rc[hbs]<0||Ba[Rc[hbs]]!=Q){break;}hbs=Rc[hbs];
		}
		//cerr<<"de"<<__LINE__<<endl;
		while(que.size()){
			int ter=que.front();que.pop();
			//cerr<<"ter="<<ter<<endl;
			if(Rc[ter]>=0&&Ba[Rc[ter]]==Q&&Da[Rc[ter]]==mod){
				int ne=Rc[ter];
				Da[ne]=Da[ter]+1;
				Do[ne]=Do[ter];
				que.push(ne);
			}
			if(Lc[ter]>=0&&Ba[Lc[ter]]==Q&&Da[Lc[ter]]==mod){
				int ne=Lc[ter];
				Da[ne]=Da[ter]+1;
				Do[ne]=Do[ter];
				que.push(ne);
			}
			if(Dc[ter]>=0&&Ba[Dc[ter]]==Q&&Da[Dc[ter]]==mod){
				int ne=Dc[ter];
				Da[ne]=Da[ter]+1;
				Do[ne]=Do[ter];
				que.push(ne);
			}
			if(Uc[ter]>=0&&Ba[Uc[ter]]==Q&&Da[Uc[ter]]==mod){
				int ne=Uc[ter];
				Da[ne]=Da[ter]+1;
				Do[ne]=Do[ter];
				que.push(ne);
			}
		}
		//cerr<<"de"<<__LINE__<<endl;
		vector<llint>kazu(naga);
		vector<llint>tank(naga);
		for(i=sta;i<sta+num;i++){
			int t=lis[i];
			//cerr<<"do,da"<<Do[t]<<" "<<Da[t]<<endl;
			kazu[Do[t]]++;
			tank[Do[t]]+=Da[t];
			Ba[t]=bunum+1-Do[t]%2;
		}
		//cerr<<"de"<<__LINE__<<endl;
		//cerr<<"naga="<<naga<<endl;
		naga/=2;
		llint uesu=0,stsu=0,strui=0;
		for(i=0;i<naga;i++){
			uesu+=kazu[i*2];
			stsu+=kazu[i*2+1];
			strui+=kazu[i*2+1]*i;
		}
		for(i=0;i<naga;i++){
			ans+=stsu*tank[i*2];
			ans+=uesu*tank[i*2+1];
			ans%=mod;
		}
		//cerr<<"de"<<__LINE__<<endl;
		//cerr<<"ans="<<ans<<endl;
		ans+=uesu*stsu;
		for(i=0;i<naga;i++){
			ans+=kazu[i*2]*strui;
			ans%=mod;
			stsu-=kazu[i*2+1]*2;
			strui-=stsu;
		}
		//cerr<<"ans="<<ans<<endl;
		//uesuはそのまま
		vector<int>nulisue;
		vector<int>nulist;
		for(i=sta;i<sta+num;i++){
			int t=lis[i];
			if(Do[t]%2){nulisue.pub(t);}else{nulist.pub(t);}
		}
		for(i=sta;i<sta+nulisue.size();i++){lis[i]=nulisue[i-sta];}
		yaru.push(mt(sta,nulisue.size(),bunum));bunum++;
		sta+=nulisue.size();
		//cerr<<"de"<<__LINE__<<endl;
		for(i=sta;i<sta+nulist.size();i++){lis[i]=nulist[i-sta];}
		yaru.push(mt(sta,nulist.size(),bunum));bunum++;
		//for(i=0;i<N;i++){cerr<<"ba[i]="<<Ba[i]<<endl;}
	}
	return ans%mod;
}

Compilation message

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:129:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<doco.size();i++){
           ~^~~~~~~~~~~~
city.cpp:149:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(tgi<dfque.size()){
         ~~~^~~~~~~~~~~~~
city.cpp:166:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<doco.size();i++){maxeq(sai,mp(min(siz[i],siz[0]-siz[i]),(int)i));}
           ~^~~~~~~~~~~~
city.cpp:263:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=sta;i<sta+nulisue.size();i++){lis[i]=nulisue[i-sta];}
             ~^~~~~~~~~~~~~~~~~~~
city.cpp:267:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=sta;i<sta+nulist.size();i++){lis[i]=nulist[i-sta];}
             ~^~~~~~~~~~~~~~~~~~
city.cpp:116:7: warning: unused variable 'dasu' [-Wunused-variable]
   int dasu=0;
       ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 4 ms 520 KB Output is correct
4 Correct 3 ms 520 KB Output is correct
5 Correct 3 ms 520 KB Output is correct
6 Correct 4 ms 560 KB Output is correct
7 Correct 3 ms 628 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 636 KB Output is correct
10 Correct 4 ms 684 KB Output is correct
11 Correct 3 ms 744 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 824 KB Output is correct
2 Correct 6 ms 1004 KB Output is correct
3 Correct 9 ms 1004 KB Output is correct
4 Correct 9 ms 1004 KB Output is correct
5 Correct 15 ms 1004 KB Output is correct
6 Correct 14 ms 1004 KB Output is correct
7 Correct 12 ms 1004 KB Output is correct
8 Correct 11 ms 1004 KB Output is correct
9 Correct 12 ms 1016 KB Output is correct
10 Correct 12 ms 1028 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 2064 KB Output is correct
2 Correct 88 ms 2192 KB Output is correct
3 Correct 203 ms 4244 KB Output is correct
4 Correct 210 ms 4628 KB Output is correct
5 Correct 461 ms 7884 KB Output is correct
6 Correct 611 ms 8688 KB Output is correct
7 Correct 436 ms 9536 KB Output is correct
8 Correct 429 ms 10280 KB Output is correct
9 Correct 556 ms 11128 KB Output is correct
10 Correct 657 ms 13896 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 13896 KB Output is correct
2 Correct 86 ms 13896 KB Output is correct
3 Correct 280 ms 13896 KB Output is correct
4 Correct 230 ms 13896 KB Output is correct
5 Correct 525 ms 16312 KB Output is correct
6 Correct 495 ms 16312 KB Output is correct
7 Correct 680 ms 17884 KB Output is correct
8 Correct 564 ms 17884 KB Output is correct
9 Correct 470 ms 17884 KB Output is correct
10 Correct 468 ms 17984 KB Output is correct