Submission #923177

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
923177	2024-02-06T19:42:29 Z	Dzadzo	Ideal city (IOI12_city)	C++17	100 / 100	159 ms	47048 KB

city

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<ll,ll>
#define vi vector <ll>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF LLONG_MAX
#define MOD 1000000000
#define MAXN 1000000
using namespace std;
vvi adj(MAXN+1);
vi a(MAXN+1);
ll ans=0;
int n;
void dfs(ll v,ll p){
	for (int to:adj[v]){
		if (to==p)continue;
		dfs(to,v);
		a[v]+=a[to];
	}
	ans=(ans+(a[v]*(n-a[v]))%MOD)%MOD;
}
int DistanceSum(int N, int X[], int Y[]){
	n=N;
	vp arr;
	map <pii,ll> m;
	for (ll i=0;i<N;i++)arr.pb({1ll*X[i],1ll*Y[i]});
	sort(arr.begin(),arr.end());
	ll cnt=0;
	ll sz=0;
	for (auto &[x,y]:arr){
		if (!m[{x,y-1}]){
			a[cnt]=sz;
			cnt++;
			sz=1;
			if (m[{x-1,y}]){
				adj[cnt].pb(m[{x-1,y}]);
				adj[m[{x-1,y}]].pb(cnt);
			}
		}else{
			sz++;
			if (m[{x-1,y}] && !m[{x-1,y-1}]){
				adj[cnt].pb(m[{x-1,y}]);
				adj[m[{x-1,y}]].pb(cnt);				
			}
		}
		m[{x,y}]=cnt;
	}
	a[cnt]=sz;
	dfs(1,0);
	arr.clear();
	m.clear();
	cnt=sz=0;
	adj.assign(MAXN+1,{});
	a.assign(MAXN+1,0);
	for (ll i=0;i<N;i++)arr.pb({1ll*Y[i],1ll*X[i]});
	sort(arr.begin(),arr.end());
	for (auto &[y,x]:arr){
		if (!m[{x-1,y}]){
			a[cnt]=sz;
			cnt++;
			sz=1;
			if (m[{x,y-1}]){
				adj[cnt].pb(m[{x,y-1}]);
				adj[m[{x,y-1}]].pb(cnt);
			}
		}else{
			sz++;
			if (m[{x,y-1}] && !m[{x-1,y-1}]){
				adj[cnt].pb(m[{x,y-1}]);
				adj[m[{x,y-1}]].pb(cnt);				
			}
		}
		m[{x,y}]=cnt;
	}
	a[cnt]=sz;
	dfs(1,0);
	return ans;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	31576 KB	Output is correct
2	Correct	12 ms	31580 KB	Output is correct
3	Correct	12 ms	31580 KB	Output is correct
4	Correct	12 ms	31576 KB	Output is correct
5	Correct	12 ms	31576 KB	Output is correct
6	Correct	13 ms	31796 KB	Output is correct
7	Correct	12 ms	31580 KB	Output is correct
8	Correct	12 ms	31616 KB	Output is correct
9	Correct	12 ms	31580 KB	Output is correct
10	Correct	12 ms	31788 KB	Output is correct
11	Correct	14 ms	31836 KB	Output is correct

Subtask #2

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	31832 KB	Output is correct
2	Correct	14 ms	31836 KB	Output is correct
3	Correct	15 ms	31960 KB	Output is correct
4	Correct	14 ms	31836 KB	Output is correct
5	Correct	14 ms	31888 KB	Output is correct
6	Correct	14 ms	31836 KB	Output is correct
7	Correct	14 ms	32092 KB	Output is correct
8	Correct	15 ms	31836 KB	Output is correct
9	Correct	15 ms	31832 KB	Output is correct
10	Correct	16 ms	32136 KB	Output is correct

Subtask #3

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	33744 KB	Output is correct
2	Correct	28 ms	33748 KB	Output is correct
3	Correct	59 ms	36560 KB	Output is correct
4	Correct	55 ms	36392 KB	Output is correct
5	Correct	116 ms	41164 KB	Output is correct
6	Correct	103 ms	41172 KB	Output is correct
7	Correct	112 ms	41568 KB	Output is correct
8	Correct	104 ms	41160 KB	Output is correct
9	Correct	97 ms	41428 KB	Output is correct
10	Correct	98 ms	46028 KB	Output is correct

Subtask #4

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	34772 KB	Output is correct
2	Correct	34 ms	34260 KB	Output is correct
3	Correct	79 ms	39292 KB	Output is correct
4	Correct	76 ms	38508 KB	Output is correct
5	Correct	158 ms	46792 KB	Output is correct
6	Correct	124 ms	43464 KB	Output is correct
7	Correct	159 ms	47048 KB	Output is correct
8	Correct	143 ms	43592 KB	Output is correct
9	Correct	124 ms	42952 KB	Output is correct
10	Correct	122 ms	42596 KB	Output is correct