Submission #578694

#	Time	Username	Problem	Language	Result	Execution time	Memory
578694		WongChun1234	Ideal city (IOI12_city)	C++14	100 / 100	578 ms	47496 KiB

city

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100050;
const ll MOD=1000000000;
const bool DEBUG=0;
int n,cx,cnt[N],grpcnt,ingrp[N];
ll ans,dist[N];
vector<pair<int,int>> curr,grps[N];
pair<int,int> coord[N];
map<int,vector<pair<int,int>>> mp;
map<pair<int,int>,int> hv;
ll f(ll num){
	return (1+num)*num/2%MOD;
}
void dfs(int nde,int par,pair<int,int> connection,bool up){
	vector<array<ll,2>> frntsum,frntcnt,bcksum,bckcnt;
	int cx=coord[grps[nde][0].second-1].first,cy=INT_MAX,cz=grps[nde].size();
	ll csum=0,ccnt=0,lzsum=0,lzcnt=0,dup=0;
	frntsum.resize(cz); frntcnt.resize(cz); bcksum.resize(cz); bckcnt.resize(cz);
	if (DEBUG) cerr<<"dfs"<<cx<<"::"<<connection.first<<","<<connection.second<<"\n";
	for (auto i:grps[nde]){
		if (!hv[{cx+1,i.first}]) continue;
		if (ingrp[hv[{cx+1,i.first}]]==par) continue;
		cy=min(cy,i.first);
		if (hv[{cx+1,i.first+1}]&&i!=grps[nde].back()) continue;
		dfs(ingrp[hv[{cx+1,i.first}]],nde,{cy,i.first},0);
		cy=INT_MAX;
	}
	cy=INT_MAX;
	for (auto i:grps[nde]){
		if (!hv[{cx-1,i.first}]) continue;
		if (ingrp[hv[{cx-1,i.first}]]==par) continue;
		cy=min(cy,i.first);
		if (hv[{cx-1,i.first+1}]&&i!=grps[nde].back()) continue;
		dfs(ingrp[hv[{cx-1,i.first}]],nde,{cy,i.first},1);
		cy=INT_MAX;
	}
	// down down, up up
	if (DEBUG) cerr<<"PROCESSING"<<ans<<"\n";
	for (auto i:grps[nde]){
		if (DEBUG) cerr<<cx<<","<<i.first<<"\n";
		csum+=ccnt;
		csum%=MOD;
		lzsum+=lzcnt;
		lzsum%=MOD;
		if (DEBUG) cerr<<csum<<","<<ccnt<<";"<<lzsum<<","<<lzcnt<<":"<<ans<<"\n";
		if (hv[{cx-1,i.first}]&&ingrp[hv[{cx-1,i.first}]]!=par){
			lzcnt+=cnt[hv[{cx-1,i.first}]];
			lzsum+=dist[hv[{cx-1,i.first}]]+cnt[hv[{cx-1,i.first}]];
			lzcnt%=MOD; lzsum%=MOD;
			ans+=ccnt*(dist[hv[{cx-1,i.first}]]+cnt[hv[{cx-1,i.first}]]);
			ans+=csum*cnt[hv[{cx-1,i.first}]];
			ans%=MOD;
			if (DEBUG) cerr<<ans<<"::\n";
		}else{
			csum+=lzsum;
			csum%=MOD;
			ccnt+=lzcnt;
			ccnt%=MOD;
			lzsum=lzcnt=0;
		}
	}
	csum=lzsum=ccnt=lzcnt=0;
	for (auto i:grps[nde]){
		if (DEBUG) cerr<<cx<<","<<i.first<<"\n";
		csum+=ccnt;
		csum%=MOD;
		lzsum+=lzcnt;
		lzsum%=MOD;
		if (DEBUG) cerr<<csum<<","<<ccnt<<";"<<lzsum<<","<<lzcnt<<":"<<ans<<"\n";
		if (hv[{cx+1,i.first}]&&ingrp[hv[{cx+1,i.first}]]!=par){
			lzcnt+=cnt[hv[{cx+1,i.first}]];
			lzsum+=dist[hv[{cx+1,i.first}]]+cnt[hv[{cx+1,i.first}]];
			lzcnt%=MOD; lzsum%=MOD;
			ans+=ccnt*(dist[hv[{cx+1,i.first}]]+cnt[hv[{cx+1,i.first}]]);
			ans+=csum*cnt[hv[{cx+1,i.first}]];
			ans%=MOD;
			if (DEBUG) cerr<<ans<<"::\n";
		}else{
			csum+=lzsum;
			csum%=MOD;
			ccnt+=lzcnt;
			ccnt%=MOD;
			lzsum=lzcnt=0;
		}
	}
	// down to up
	for (int i=0;i<cz;i++){
		if (i){
			frntsum[i][0]=(frntsum[i-1][0]+frntcnt[i-1][0])%MOD;
			frntcnt[i][0]=frntcnt[i-1][0];
			frntsum[i][1]=(frntsum[i-1][1]+frntcnt[i-1][1])%MOD;
			frntcnt[i][1]=frntcnt[i-1][1];
		}
		dup+=ccnt;
		ccnt+=i+1;
		ccnt%=MOD; dup%=MOD;
		if (hv[{cx-1,grps[nde][i].first}]&&ingrp[hv[{cx-1,grps[nde][i].first}]]!=par){
			frntcnt[i][0]+=cnt[hv[{cx-1,grps[nde][i].first}]];
			frntsum[i][0]+=dist[hv[{cx-1,grps[nde][i].first}]]+cnt[hv[{cx-1,grps[nde][i].first}]];
			frntsum[i][0]%=MOD;
		}
		if (hv[{cx+1,grps[nde][i].first}]&&ingrp[hv[{cx+1,grps[nde][i].first}]]!=par){
			frntcnt[i][1]+=cnt[hv[{cx+1,grps[nde][i].first}]];
			frntsum[i][1]+=dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]];
			frntsum[i][1]%=MOD;
		}
	}
	for (int i=cz-1;~i;i--){
		if (i!=cz-1){
			bcksum[i][0]=(bcksum[i+1][0]+bckcnt[i+1][0])%MOD;
			bckcnt[i][0]=bckcnt[i+1][0];
			bcksum[i][1]=(bcksum[i+1][1]+bckcnt[i+1][1])%MOD;
			bckcnt[i][1]=bckcnt[i+1][1];
		}
		if (hv[{cx-1,grps[nde][i].first}]&&ingrp[hv[{cx-1,grps[nde][i].first}]]!=par){
			bckcnt[i][0]+=cnt[hv[{cx-1,grps[nde][i].first}]];
			bcksum[i][0]+=dist[hv[{cx-1,grps[nde][i].first}]]+cnt[hv[{cx-1,grps[nde][i].first}]];
			bcksum[i][0]%=MOD;
		}
		if (hv[{cx+1,grps[nde][i].first}]&&ingrp[hv[{cx+1,grps[nde][i].first}]]!=par){
			bckcnt[i][1]+=cnt[hv[{cx+1,grps[nde][i].first}]];
			bcksum[i][1]+=dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]];
			bcksum[i][1]%=MOD;
		}
	}
	if (DEBUG) for (int i=0;i<cz;i++) cerr<<frntsum[i][0]<<" "<<frntsum[i][1]<<" "<<frntcnt[i][0]<<" "<<frntcnt[i][1]<<"\n";
	for (int i=0;i<cz;i++){
		ans+=bcksum[i][0]+bcksum[i][1];
		ans%=MOD;
		if (i) ans+=frntsum[i-1][0]+frntsum[i-1][1]+frntcnt[i-1][0]+frntcnt[i-1][1];
		ans%=MOD;
		if (DEBUG) cerr<<cx<<","<<grps[nde][i].first<<":"<<ans<<"\n";
		if (!hv[{cx+1,grps[nde][i].first}]||ingrp[hv[{cx+1,grps[nde][i].first}]]==par) continue;
		ans+=(dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]])%MOD*bckcnt[i][0];
		ans%=MOD;
		ans+=bcksum[i][0]*cnt[hv[{cx+1,grps[nde][i].first}]];
		ans%=MOD;
		if (i){
			ans+=(dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]])%MOD*frntcnt[i-1][0];
			ans%=MOD;
			ans+=(frntsum[i-1][0]+frntcnt[i-1][0])*cnt[hv[{cx+1,grps[nde][i].first}]];
			ans%=MOD;
		}
		if (DEBUG) cerr<<cx<<","<<grps[nde][i].first<<":"<<ans<<"\n";
	}
	for (int i=0;i<cz;i++){
		if (up){
			cnt[hv[{cx,grps[nde][i].first}]]=cnt[hv[{cx-1,grps[nde][i].first}]]+1;
			dist[hv[{cx,grps[nde][i].first}]]=dist[hv[{cx-1,grps[nde][i].first}]]+cnt[hv[{cx-1,grps[nde][i].first}]];
			dist[hv[{cx,grps[nde][i].first}]]%=MOD;
		}else{
			cnt[hv[{cx,grps[nde][i].first}]]=cnt[hv[{cx+1,grps[nde][i].first}]]+1;
			dist[hv[{cx,grps[nde][i].first}]]=dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]];
			dist[hv[{cx,grps[nde][i].first}]]%=MOD;
		}
		if (grps[nde][i].first==connection.first){
			if (i){
				cnt[hv[{cx,grps[nde][i].first}]]+=frntcnt[i-1][0]+frntcnt[i-1][1]+i;
				dist[hv[{cx,grps[nde][i].first}]]+=frntsum[i-1][0]+frntsum[i-1][1]+frntcnt[i-1][0]+frntcnt[i-1][1]+f(i);
				dist[hv[{cx,grps[nde][i].first}]]%=MOD;
			}
		}
		if (grps[nde][i].first==connection.second){
			if (i<cz-1){
				cnt[hv[{cx,grps[nde][i].first}]]+=bckcnt[i+1][0]+bckcnt[i+1][1]+cz-i-1;
				dist[hv[{cx,grps[nde][i].first}]]+=bcksum[i+1][0]+bcksum[i+1][1]+bckcnt[i+1][0]+bckcnt[i+1][1]+f(cz-i-1);
				dist[hv[{cx,grps[nde][i].first}]]%=MOD;
			}
		}
		if (DEBUG) cerr<<cx<<":::"<<grps[nde][i].first<<":"<<cnt[hv[{cx,grps[nde][i].first}]]<<","<<dist[hv[{cx,grps[nde][i].first}]]<<"\n";
	}
	for (int i=0;i<cz;i++) ans+=f(i);
}
void addgrp(){
	grps[++grpcnt]=curr;
	for (auto i:curr) ingrp[i.second]=grpcnt;
	curr.clear();
}
int DistanceSum(int _N, int *x, int *y) {
	n=_N;
	for (int i=0;i<n;i++) coord[i]={x[i],y[i]};
	sort(coord,coord+n);
	for (int i=0;i<n;i++){
		hv[coord[i]]=i+1;
		mp[coord[i].first].push_back({coord[i].second,i+1});
	}
	for (auto i:mp){
		cx=i.first;
		curr.clear();
		for (auto j:i.second){
			if (curr.empty()||j.first==curr.back().first+1){
				curr.push_back(j);
			}else{
				addgrp();
				curr.push_back(j);
			}
		}
		if (curr.size()) addgrp();
	}
	dfs(1,1,{-1,-1},0);
	return ans;
}

/*
6
1 1
2 1
2 3
3 1
3 2
3 3
*/

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45