oj.uz

Submission #197036

# Submission time Handle Problem Language Result Execution time Memory
197036 2020-01-18T09:11:40 Z dennisstar Ideal city (IOI12_city) C++11
100 / 100
 94 ms 10060 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define sq(X) ((X)*(X))
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
#define unq(V) (V).erase(unique(all(V)), (V).end())
using namespace std;
typedef long long ll;
typedef vector<ll> vlm;
typedef vector<int> vim;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

const ll MOD=1000000000ll;
int N; vector<pii> P;
inline int Find(pii p) {
	int lb=lower_bound(all(P), p)-P.begin();
	return (lb<P.size()&&P[lb]==p)?lb:-1;
}
vim adj[100010]; int ar[100010], sz[100010], vis[100010]; ll D[100010];
//d1 : 부분트리의 크기, d2 : 부분트리에서의 값

ll ans=0;
void dfs1(int now) {
	vis[now]=1; D[now]=sz[now];
	for (int i:adj[now]) if (!vis[i]) {
		dfs1(i);
		D[now]+=D[i];
	}
}
void dfs2(int now, ll s) {
	vis[now]=1;
	for (int i:adj[now]) if (!vis[i]) {
		dfs2(i, s+D[now]-D[i]);
		ans+=(s+D[now]-D[i])*D[i];
		ans%=MOD;
	}
}

void init() {
	sort(all(P));
	memset(ar, 0, sizeof(ar));
	memset(sz, 0, sizeof(sz));
	memset(vis, 0, sizeof(vis));
	memset(D, 0, sizeof(D));
	for (int i=0; i<=100000; i++) adj[i].clear();
}
void solve() {
	init(); int C=0;
	for (int i=0; i<N; i++) {
		C++;
		ar[i]=C;
		int j; for (j=i+1; j<N; j++) {
			if (P[j].fi!=P[i].fi||P[j].se!=P[j-1].se+1) break;
			ar[j]=C;
		}
		i=j-1;
	}
	for (int i=0; i<N; i++) sz[ar[i]]++;
	for (int i=0; i<N; i++) {
		int r=Find(pii(P[i].fi+1, P[i].se));
		if (r!=-1&&(!adj[ar[i]].size()||adj[ar[i]].back()!=ar[r])) adj[ar[i]].eb(ar[r]);
	}
	for (int i=0; i<N; i++) {
		int r=Find(pii(P[i].fi-1, P[i].se));
		if (r!=-1&&(!adj[ar[i]].size()||adj[ar[i]].back()!=ar[r])) adj[ar[i]].eb(ar[r]);
	}
	memset(vis, 0, sizeof(vis)); dfs1(1);
	memset(vis, 0, sizeof(vis)); dfs2(1, 0);
}

int DistanceSum(int n, int *X, int *Y) {
	N=n; for (int i=0; i<N; i++) P.eb(X[i], Y[i]);
	solve(); for (auto &i:P) swap(i.fi, i.se); solve();
	return (int)ans;
}

Compilation message

city.cpp: In function 'int Find(pii)':
city.cpp:20:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return (lb<P.size()&&P[lb]==p)?lb:-1;
          ~~^~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5364 KB Output is correct
2 Correct 21 ms 5364 KB Output is correct
3 Correct 41 ms 6004 KB Output is correct
4 Correct 42 ms 6004 KB Output is correct
5 Correct 77 ms 7280 KB Output is correct
6 Correct 80 ms 7280 KB Output is correct
7 Correct 79 ms 7408 KB Output is correct
8 Correct 77 ms 7152 KB Output is correct
9 Correct 79 ms 7280 KB Output is correct
10 Correct 81 ms 10060 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5464 KB Output is correct
2 Correct 22 ms 5492 KB Output is correct
3 Correct 48 ms 6516 KB Output is correct
4 Correct 46 ms 6384 KB Output is correct
5 Correct 94 ms 8460 KB Output is correct
6 Correct 84 ms 7792 KB Output is correct
7 Correct 94 ms 8596 KB Output is correct
8 Correct 84 ms 7792 KB Output is correct
9 Correct 80 ms 7408 KB Output is correct
10 Correct 81 ms 7536 KB Output is correct