oj.uz

Submission #59241

# Submission time Handle Problem Language Result Execution time Memory
59241 2018-07-21T10:03:20 Z TadijaSebez Ideal city (IOI12_city) C++11
100 / 100
 617 ms 29024 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#define mp make_pair
#define pb push_back
#define ll long long 
const int N=100050;
const int mod=1e9;
int comp[N],cnt;
map<pair<int,int> ,int> id;
vector<int> E[N];
int weg[N],sz[N],n;
int x[N],y[N],p[N];
void init(){ for(int i=0;i<N;i++) p[i]=i;}
int Find(int x){ return x==p[x]?x:p[x]=Find(p[x]);}
void Union(int x, int y){ p[Find(x)]=Find(y);}
int dep[N];
ll ans;
void DFS(int u, int p)
{
	int i;
	//printf("DFS:%i %i\n",u,p);
	sz[u]=weg[u];
	dep[u]=dep[p]+1;
	for(i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		if(v!=p) DFS(v,u),sz[u]+=sz[v];
	}
	ll mul=0;
	//int sub=0;
	for(i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		if(v!=p)
		{
			mul+=(ll)sz[v]*(sz[u]-sz[v])%mod;
			mul%=mod;
			//sub+=sz[v];
		}
	}
	mul+=(ll)weg[u]*(weg[u]-1)%mod;
	mul%=mod;
	ans-=(ll)mul*dep[u]%mod;
	if(ans<0) ans+=mod;
	ans+=(ll)(n-sz[u]+weg[u]-1)*weg[u]%mod*dep[u]%mod;
	ans%=mod;
	//printf("u:%i -mul:%lld +mul:%lld weg:%lld sz:%lld\n",u,mul,(n-sz[u]+weg[u]-1)*weg[u],weg[u],sz[u]);
}
int SolveTree()
{
	ans=0;
	DFS(1,0);
	return ans%mod;
}
int DistanceSum(int M, int X[], int Y[])
{
	n=M;
	int i,j;
	for(i=1;i<=n;i++) x[i]=X[i-1],y[i]=Y[i-1];
	for(i=1;i<=n;i++) id[mp(x[i],y[i])]=i;
	for(i=1;i<=n;i++)
	{
		if(!comp[i])
		{
			cnt++;
			comp[i]=cnt;
			weg[cnt]=1;
			j=1;
			while(id.count(mp(x[i],y[i]+j))) comp[id[mp(x[i],y[i]+j)]]=cnt,j++,weg[cnt]++;
			j=1;
			while(id.count(mp(x[i],y[i]-j))) comp[id[mp(x[i],y[i]-j)]]=cnt,j++,weg[cnt]++;
		}
	}
	//for(i=1;i<=n;i++) printf("%i ",comp[i]);printf("\n");
	//for(i=1;i<=cnt;i++) printf("%i ",weg[i]);printf("\n");
	init();
	for(i=1;i<=n;i++)
	{
		int u=id[mp(x[i]+1,y[i])];
		if(u && Find(comp[i])!=Find(comp[u]))
		{
			//printf("(%i - %i)\n",comp[i],comp[u]);
			E[comp[i]].pb(comp[u]);
			E[comp[u]].pb(comp[i]);
			Union(comp[i],comp[u]);
		}
		u=id[mp(x[i]-1,y[i])];
		if(u && Find(comp[i])!=Find(comp[u]))
		{
			//printf("(%i - %i)\n",comp[i],comp[u]);
			E[comp[i]].pb(comp[u]);
			E[comp[u]].pb(comp[i]);
			Union(comp[i],comp[u]);
		}
	}
	int sol=SolveTree();
	//printf("->%i\n",sol);
	for(i=1;i<=n;i++) comp[i]=0;
	for(i=1;i<=cnt;i++) E[i].clear();
	cnt=0;
	for(i=1;i<=n;i++)
	{
		if(!comp[i])
		{
			cnt++;
			comp[i]=cnt;
			weg[cnt]=1;
			j=1;
			while(id[mp(x[i]+j,y[i])]) comp[id[mp(x[i]+j,y[i])]]=cnt,j++,weg[cnt]++;
			j=1;
			while(id[mp(x[i]-j,y[i])]) comp[id[mp(x[i]-j,y[i])]]=cnt,j++,weg[cnt]++;
		}
	}
	//for(i=1;i<=n;i++) printf("%i ",comp[i]);printf("\n");
	init();
	for(i=1;i<=n;i++)
	{
		int u=id[mp(x[i],y[i]+1)];
		if(u && Find(comp[i])!=Find(comp[u]))
		{
			//printf("(%i - %i)\n",comp[i],comp[u]);
			E[comp[i]].pb(comp[u]);
			E[comp[u]].pb(comp[i]);
			Union(comp[i],comp[u]);
		}
		u=id[mp(x[i],y[i]-1)];
		if(u && Find(comp[i])!=Find(comp[u]))
		{
			//printf("(%i - %i)\n",comp[i],comp[u]);
			E[comp[i]].pb(comp[u]);
			E[comp[u]].pb(comp[i]);
			Union(comp[i],comp[u]);
		}
	}
	sol+=SolveTree();
	sol%=mod;
	return sol;
}

Compilation message

city.cpp: In function 'void DFS(int, int)':
city.cpp:27:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<E[u].size();i++)
          ~^~~~~~~~~~~~
city.cpp:34:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<E[u].size();i++)
          ~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3532 KB Output is correct
2 Correct 6 ms 3540 KB Output is correct
3 Correct 8 ms 3692 KB Output is correct
4 Correct 6 ms 3704 KB Output is correct
5 Correct 8 ms 3884 KB Output is correct
6 Correct 8 ms 3884 KB Output is correct
7 Correct 9 ms 4064 KB Output is correct
8 Correct 10 ms 4064 KB Output is correct
9 Correct 9 ms 4064 KB Output is correct
10 Correct 11 ms 4064 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5624 KB Output is correct
2 Correct 49 ms 6024 KB Output is correct
3 Correct 135 ms 8844 KB Output is correct
4 Correct 200 ms 9248 KB Output is correct
5 Correct 542 ms 14056 KB Output is correct
6 Correct 499 ms 14872 KB Output is correct
7 Correct 333 ms 15912 KB Output is correct
8 Correct 543 ms 16308 KB Output is correct
9 Correct 520 ms 17532 KB Output is correct
10 Correct 611 ms 24692 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 24692 KB Output is correct
2 Correct 56 ms 24692 KB Output is correct
3 Correct 217 ms 24692 KB Output is correct
4 Correct 165 ms 24692 KB Output is correct
5 Correct 495 ms 26928 KB Output is correct
6 Correct 450 ms 26928 KB Output is correct
7 Correct 598 ms 29024 KB Output is correct
8 Correct 617 ms 29024 KB Output is correct
9 Correct 479 ms 29024 KB Output is correct
10 Correct 497 ms 29024 KB Output is correct