oj.uz

Submission #94058

# Submission time Handle Problem Language Result Execution time Memory
94058 2019-01-15T14:50:07 Z fjzzq2002 Ideal city (IOI12_city) C++14
100 / 100
 495 ms 17824 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 4 ms 3068 KB Output is correct
3 Correct 4 ms 3064 KB Output is correct
4 Correct 4 ms 2940 KB Output is correct
5 Correct 4 ms 3064 KB Output is correct
6 Correct 4 ms 3064 KB Output is correct
7 Correct 14 ms 3192 KB Output is correct
8 Correct 4 ms 3064 KB Output is correct
9 Correct 4 ms 3064 KB Output is correct
10 Correct 4 ms 3064 KB Output is correct
11 Correct 5 ms 3064 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3192 KB Output is correct
2 Correct 5 ms 3192 KB Output is correct
3 Correct 6 ms 3320 KB Output is correct
4 Correct 6 ms 3320 KB Output is correct
5 Correct 6 ms 3320 KB Output is correct
6 Correct 6 ms 3320 KB Output is correct
7 Correct 6 ms 3324 KB Output is correct
8 Correct 7 ms 3320 KB Output is correct
9 Correct 6 ms 3320 KB Output is correct
10 Correct 6 ms 3320 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4728 KB Output is correct
2 Correct 44 ms 4856 KB Output is correct
3 Correct 122 ms 7288 KB Output is correct
4 Correct 105 ms 7108 KB Output is correct
5 Correct 275 ms 11312 KB Output is correct
6 Correct 294 ms 11084 KB Output is correct
7 Correct 299 ms 11516 KB Output is correct
8 Correct 273 ms 11024 KB Output is correct
9 Correct 409 ms 11512 KB Output is correct
10 Correct 495 ms 16052 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6008 KB Output is correct
2 Correct 60 ms 5592 KB Output is correct
3 Correct 152 ms 10304 KB Output is correct
4 Correct 163 ms 9080 KB Output is correct
5 Correct 435 ms 17536 KB Output is correct
6 Correct 316 ms 13560 KB Output is correct
7 Correct 413 ms 17824 KB Output is correct
8 Correct 372 ms 13716 KB Output is correct
9 Correct 377 ms 13176 KB Output is correct
10 Correct 351 ms 12692 KB Output is correct