Submission #422971

#	Time	Username	Problem	Language	Result	Execution time	Memory
422971		Bill_00	Ideal city (IOI12_city)	C++14	32 / 100	25 ms	6684 KiB

city

#include <bits/stdc++.h>
typedef long long ll;
const ll maxvalue=3000000000; 
using namespace std;
ll timer,n,x[100005],y[100005],weight[100005],sz[100005],ansx,ansy;
vector<ll>adj[100005];
unordered_map<ll,ll>um,vis;
void dfs(ll x,ll y,ll from){
	timer++;
	if(from!=-1){
		adj[timer].push_back(from);
		adj[from].push_back(timer);
	}
	ll Y1=y,Y2=y;
	while(um[x*maxvalue+Y1-1]==1){
		Y1--;
	}
	while(um[x*maxvalue+Y2+1]==1){
		Y2++;
	}
	for(ll i=Y1;i<=Y2;i++){
		vis[x*maxvalue+i]=timer;
		weight[timer]++;
	}
	ll to=timer;
	for(ll i=Y1;i<=Y2;i++){
		if(vis[(x-1)*maxvalue+i]==0 && um[(x-1)*maxvalue+i]==1){
			dfs(x-1,i,to);
		}
		if(vis[(x+1)*maxvalue+i]==0 && um[(x+1)*maxvalue+i]==1){
			dfs(x+1,i,to);
		}
	}
}
void dfs1(ll x,ll y,ll from){
	timer++;
	if(from!=-1){
		adj[timer].push_back(from);
		adj[from].push_back(timer);
	}
	ll X1=x,X2=x;
	while(um[(X1-1)*maxvalue+y]==1){
		X1--;
	}
	while(um[(X2+1)*maxvalue+y]==1){
		X2++;
	}
	for(ll i=X1;i<=X2;i++){
		vis[i*maxvalue+y]=timer;
		weight[timer]++;
	}
	ll to=timer;
	for(ll i=X1;i<=X2;i++){
		if(vis[(i*maxvalue)+y-1]==0 && um[i*maxvalue+y-1]==1){
			dfs1(i,y-1,to);
		}
		if(vis[i*maxvalue+y+1]==0 && um[i*maxvalue+y+1]==1){
			dfs1(i,y+1,to);
		}
	}
}
void solve(ll node,bool f,ll par=-1){
	// cout << node << ' ' << weight[node] << '\n';
	sz[node]=weight[node];
	for(ll to:adj[node]){
		if(to==par) continue;
		solve(to,f,node);
		sz[node]+=sz[to];
		if(f==0){
			ansx+=(sz[to]*(n-sz[to]));
		}
		else ansy+=(sz[to]*(n-sz[to]));
	}
}
int DistanceSum(int N, int *X, int *Y) {
	n=(ll)N;
	for(ll i=0;i<n;i++){
		x[i]=(ll)X[i];
		y[i]=(ll)Y[i];
	}
	for(ll i=0;i<n;i++) um[x[i]*maxvalue+y[i]]=1;
	for(ll i=0;i<n;i++){
		if(vis[x[i]*maxvalue+y[i]]==0){
			dfs(x[i],y[i],-1);
		}
	}
	solve(1,0);
	for(ll i=0;i<n;i++) vis[x[i]*maxvalue+y[i]]=0;
	for(ll i=1;i<=timer;i++){
		weight[i]=0;
		adj[i].clear();
	}
	timer=0;
	for(ll i=0;i<n;i++){
		if(vis[x[i]*maxvalue+y[i]]==0){
			dfs1(x[i],y[i],-1);
		}
	}
	solve(1,1);
	return ansx+ansy;
}

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