Submission #1016326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016326		amirhoseinfar1385	Ideal city (IOI12_city)	C++17	0 / 100	8 ms	4564 KiB

city

#include<bits/stdc++.h>
using namespace std;
const long long maxn=2000+10;
long long n,mod=1e9,vis[maxn];
vector<pair<long long,long long>>all;
vector<long long>adj[maxn],adja[maxn];
map<pair<long long,long long>,long long>mp;
long long mainres=0;

struct dsu{
	long long par[maxn],sz[maxn];
	dsu(){
		for(long long i=0;i<maxn;i++){
			par[i]=i;
			sz[i]=1;
		}
	}
	long long root(long long u){
		if(u==par[u]){
			return u;
		}
		return par[u]=root(par[u]);
	}
	long long con(long long u,long long v){
		long long rootu=root(u),rootv=root(v);
		if(rootu!=rootv){
			par[rootu]=rootv;
			sz[rootv]+=sz[rootu];
			return 1;
		}
		return 0;
	}
}ds1,ds2;

void bfs(long long u){
	vector<long long>vis(n+1),high(n+1),bf;
	bf.push_back(u);
	vis[u]=1;
	for(long long i=0;i<(long long)bf.size();i++){
		for(auto x:adj[bf[i]]){
			if(vis[x]==0){
				vis[x]=1;
				high[x]=high[bf[i]]+1;
				bf.push_back(x);
				if(x>=u)
				mainres+=high[x];
				mainres%=mod;
			}
		}
	}
}

long long dfs(long long u,long long par=-1){
	vis[u]=1;
	long long ret=ds1.sz[u];
	for(auto x:adj[u]){
		if(x!=par){
			ret+=dfs(x,u);
		}
	}
	mainres+=(n-ret)*ret;
	return ret;
}

long long solve2(){
	for(long long i=0;i<n;i++){
		mp[all[i]]=i;
	}
	for(long long i=0;i<n;i++){
		if(mp.count(make_pair(all[i].first,all[i].second+1))!=0){
			ds1.con(mp[make_pair(all[i].first,all[i].second+1)],i);
		}
		if(mp.count(make_pair(all[i].first+1,all[i].second))!=0){
			ds2.con(mp[make_pair(all[i].first+1,all[i].second)],i);
		}
	}
	for(long long i=0;i<n;i++){
		if(mp.count(make_pair(all[i].first,all[i].second+1))!=0){
			long long u=ds1.root(i);
			long long v=ds1.root(mp[make_pair(all[i].first,all[i].second+1)]);
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		if(mp.count(make_pair(all[i].first+1,all[i].second))!=0){
			long long u=ds2.root(i);
			long long v=ds2.root(mp[make_pair(all[i].first+1,all[i].second)]);
			adja[u].push_back(v);
			adja[v].push_back(u);
		}
	}
	for(long long i=0;i<n;i++){
		if(vis[i]==0){
			dfs(i);
		}
	}
	for(long long i=0;i<n;i++){
		vis[i]=0;
		swap(ds1.sz[i],ds2.sz[i]);
		swap(adj[i],adja[i]);
	}
	for(long long i=0;i<n;i++){
		if(vis[i]==0){
			dfs(i);
		}
	}
	mainres%=mod;
	return mainres;
}

int DistanceSum(int N,int *X,int *Y){
	n=N;
	for(long long i=0;i<n;i++){
		all.push_back(make_pair(X[i],Y[i]));
	}
	return solve2();
}

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