oj.uz

Submission #24235

# Submission time Handle Problem Language Result Execution time Memory
24235 2017-06-02T21:31:55 Z Hiasat Ideal city (IOI12_city) C++14
100 / 100
 956 ms 20732 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

pii p[100001],mv[4] = {make_pair(0,-1),make_pair(0,1),make_pair(-1,0),make_pair(1,0)};

int dsu[100001],n,sz[100001],dp[100001];
map< pii , int > mp,edge;

const int MOD = 1e9;
vector<int> adj[100001];

ll fn = 0;

int find(int u){
	return u == dsu[u] ? u : dsu[u] = find(dsu[u]);
}

void pre(int u , int p){
	dp[u] = sz[u];
	for (int i = 0; i < adj[u].size(); ++i){
		int v = adj[u][i];
		if(v == p)
			continue;
		pre(v,u);
		dp[u] += dp[v];
	}
}
void dfs(int u , int p){
	if(p != -1){
		fn += (ll) 1ll*dp[u] * 1ll*(n-dp[u]);
		fn %= MOD;
	}
	for (int i = 0; i < adj[u].size(); ++i){
		int v = adj[u][i];
		if(v == p)
			continue;
		dfs(v,u);
	}
}
void solve(){
	edge.clear();
	for (int i = 0; i < n; ++i){
		adj[i].clear();
		dsu[i] = i;
		sz[i] = 0;
	}
	for (int i = 0; i < n; ++i){
		for(int j = 0 ; j < 2 ; j++){
			int newX = mv[j].first + p[i].first;
			int newY = mv[j].second + p[i].second;
			if(mp.find(make_pair(newX,newY)) != mp.end()){
				dsu[find(i)] = find(mp[make_pair(newX,newY)]);
			}
		}
	}
	for (int i = 0; i < n; ++i){
		sz[find(i)]++;
		for(int j = 2 ; j < 4 ; j++){
			int newX = mv[j].first + p[i].first;
			int newY = mv[j].second + p[i].second;
			if(mp.find(make_pair(newX,newY)) != mp.end()){
				int idx = mp[make_pair(newX,newY)];
				if(edge.find(make_pair(find(i),find(idx))) == edge.end()){
					edge[make_pair(find(i),find(idx))] = edge[make_pair(find(idx),find(i))] = 1;
					adj[find(i)].push_back(find(idx));
					adj[find(idx)].push_back(find(i));
				}
			}
		}
	}
	for (int i = 0; i < n; ++i){
		if(find(i) == i){
			pre(i,-1); 
			dfs(i,-1);
			break;
		}
	}
}
int DistanceSum(int N, int *X, int *Y) {
	n = N;
	for (int i = 0; i < N; ++i){
		p[i] = make_pair(X[i],Y[i]);
		mp[p[i]] = i;
	}
	solve();
	swap(mv[0],mv[2]);
	swap(mv[1],mv[3]);
	solve();

	return fn%MOD;
}

Compilation message

city.cpp: In function 'void pre(int, int)':
city.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[u].size(); ++i){
                    ^
city.cpp: In function 'void dfs(int, int)':
city.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[u].size(); ++i){
                    ^

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 7924 KB Output is correct
2 Correct 83 ms 7924 KB Output is correct
3 Correct 273 ms 10020 KB Output is correct
4 Correct 279 ms 10152 KB Output is correct
5 Correct 759 ms 13580 KB Output is correct
6 Correct 719 ms 13712 KB Output is correct
7 Correct 776 ms 13864 KB Output is correct
8 Correct 783 ms 13580 KB Output is correct
9 Correct 859 ms 14100 KB Output is correct
10 Correct 763 ms 20732 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 9244 KB Output is correct
2 Correct 99 ms 8716 KB Output is correct
3 Correct 339 ms 13452 KB Output is correct
4 Correct 363 ms 12160 KB Output is correct
5 Correct 956 ms 20312 KB Output is correct
6 Correct 836 ms 16252 KB Output is correct
7 Correct 896 ms 20508 KB Output is correct
8 Correct 613 ms 16388 KB Output is correct
9 Correct 659 ms 15824 KB Output is correct
10 Correct 773 ms 15428 KB Output is correct