oj.uz

Submission #735640

# Submission time Handle Problem Language Result Execution time Memory
735640 2023-05-04T12:24:57 Z myrcella Ideal city (IOI12_city) C++17
100 / 100
 120 ms 15180 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000000
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
 
const int maxn = 1e5+10;
 
pii city[maxn];
int ans = 0;
int n;
vector <int> edge[maxn];
int sz[maxn];
map <pii,int> id;
int vis[maxn];
 
void dfs(int u) {
	vis[u] = 1;
	for (int v:edge[u]) {
		if (vis[v]==1) continue;
		dfs(v);
		sz[u] += sz[v];
	}
//	debug(sz[u]);
	inc(ans,1ll*sz[u]*(n-sz[u])%mod);
}
 
void solve() {
	memset(vis,0,sizeof(vis));
	rep(i,0,maxn) while (!edge[i].empty()) edge[i].pop_back();
	id.clear();
	sort(city,city+n);
	int tot = 0,cnt=1;
	id[city[0]] = 0;
	rep(i,1,n) {
		if (city[i].fi == city[i-1].fi and city[i].se-1 == city[i-1].se) cnt++;
		else sz[tot++] = cnt,cnt = 1;
		id[city[i]] = tot;
		if (id.find(MP(city[i].fi-1,city[i].se))!=id.end()) {
			int tmp = id[MP(city[i].fi-1,city[i].se)];
			edge[tmp].pb(tot);
			edge[tot].pb(tmp);
		}
	}
	sz[tot++] = cnt;
	dfs(0);
}
 
int DistanceSum(int N, int *X, int *Y) {
	n = N;
	rep(i,0,n) city[i] = {X[i],Y[i]};
	solve();
//	debug(ans);
	rep(i,0,n) swap(city[i].fi,city[i].se);
	solve();
  return ans;
 
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4892 KB Output is correct
2 Correct 18 ms 5100 KB Output is correct
3 Correct 46 ms 7628 KB Output is correct
4 Correct 46 ms 8044 KB Output is correct
5 Correct 92 ms 12236 KB Output is correct
6 Correct 91 ms 13136 KB Output is correct
7 Correct 91 ms 12996 KB Output is correct
8 Correct 89 ms 12208 KB Output is correct
9 Correct 90 ms 12872 KB Output is correct
10 Correct 98 ms 15180 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5016 KB Output is correct
2 Correct 20 ms 5332 KB Output is correct
3 Correct 48 ms 8284 KB Output is correct
4 Correct 49 ms 8476 KB Output is correct
5 Correct 112 ms 13636 KB Output is correct
6 Correct 117 ms 13744 KB Output is correct
7 Correct 120 ms 13752 KB Output is correct
8 Correct 105 ms 13664 KB Output is correct
9 Correct 107 ms 13556 KB Output is correct
10 Correct 106 ms 13592 KB Output is correct