Submission #94058

#	Time	Username	Problem	Language	Result	Execution time	Memory
94058		fjzzq2002	Ideal city (IOI12_city)	C++14	100 / 100	495 ms	17824 KiB

city

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 233333
Edg
const int MOD=1e9;
int ff[SZ],sz[SZ],N;
int gf(int x) {return ff[x]?ff[x]=gf(ff[x]):x;}
void uni(int a,int b)
{
	a=gf(a),b=gf(b);
	if(a!=b) ff[a]=b;
}
ll ans=0;
void dfs(int x,int f=0)
{
	for esb(x,e,b) if(b!=f)
		dfs(b,x),sz[x]+=sz[b];
	ans+=sz[x]*(ll)(N-sz[x]); ans%=MOD;
}
int calc(int n,int*x,int*y)
{
	--x,--y; M=0; N=n;
	memset(fst,0,sizeof fst);
	memset(ff,0,sizeof ff);
	memset(sz,0,sizeof sz);
	map<pii,int> g;
	for(int i=1;i<=n;++i)
		g[pii(x[i],y[i])]=i;
	set<pii> p;
	for(int i=1;i<=n;++i)
	{
		int s=g[pii(x[i]-1,y[i])];
		if(s) uni(s,i);
	}
	for(int i=1;i<=n;++i)
		++sz[gf(i)];
	for(int i=1;i<=n;++i)
	{
		int s=g[pii(x[i],y[i]+1)];
		if(s)
		{
			int a=gf(s),b=gf(i);
			if(a>b) swap(a,b);
			p.insert(pii(a,b));
		}
	}
	for(auto t:p)
		adde(t.fi,t.se);
	ans=0;
	dfs(gf(1));
	return ans;
}
int DistanceSum(int N, int *X, int *Y)
{return (calc(N,X,Y)+calc(N,Y,X))%MOD;}

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