oj.uz

Submission #923173

# Submission time Handle Problem Language Result Execution time Memory
923173 2024-02-06T19:20:16 Z Dzadzo Ideal city (IOI12_city) C++17
32 / 100
 26 ms 8144 KB 
#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 1000000007
#define MAXN 100000
using namespace std;
vvi adj(MAXN+1);
vi f(MAXN+1),g(MAXN+1);
vi a(MAXN+1);
ll ans=0;
void dfs(ll v,ll p){
	g[v]=a[v];
	for (ll to:adj[v]){
		if (to==p)continue;
		dfs(to,v);
		g[v]+=g[to];
		f[v]+=f[to]+g[to];
	}
}
void reroot(ll v,ll p){
	ans+=f[v]*a[v];
	for (ll to :adj[v]){
		if (to==p)continue;
		ll fto=f[to],fv=f[v],gv=g[v],gto=g[to];
		g[v]-=g[to];
		f[v]-=f[to]+g[to];
		f[to]+=g[v]+f[v];
		g[to]+=g[v];
		reroot(to,v);
		f[to]=fto;
		f[v]=fv;
		g[v]=gv;
		g[to]=gto;
	}
}
int DistanceSum(int N, int X[], int Y[]){
	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);
	reroot(1,0);
	arr.clear();
	m.clear();
	cnt=sz=0;
	adj.assign(MAXN+1,{});
	f.assign(MAXN+1,0);
	g.assign(MAXN+1,0);
	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);
	reroot(1,0);
	return ans/2;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 3 ms 5016 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 5032 KB Output is correct
5 Correct 3 ms 4952 KB Output is correct
6 Correct 3 ms 4952 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 3 ms 4956 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 3 ms 4952 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5212 KB Output is correct
2 Correct 4 ms 5212 KB Output is correct
3 Correct 4 ms 5212 KB Output is correct
4 Correct 4 ms 5212 KB Output is correct
5 Correct 5 ms 5468 KB Output is correct
6 Correct 4 ms 5212 KB Output is correct
7 Correct 6 ms 5492 KB Output is correct
8 Correct 4 ms 5208 KB Output is correct
9 Correct 4 ms 5212 KB Output is correct
10 Correct 4 ms 5212 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 7100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 8144 KB Output isn't correct
2 Halted 0 ms 0 KB -