oj.uz

Submission #24234

# Submission time Handle Problem Language Result Execution time Memory
24234 2017-06-02T21:30:51 Z Hiasat Ideal city (IOI12_city) C++14
32 / 100
 983 ms 20312 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;

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 += dp[u] * (n-dp[u]);
	}
	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%1000000000;
}

Compilation message

city.cpp: In function 'void pre(int, int)':
city.cpp:23: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:35: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 3 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 3 ms 6724 KB Output is correct
4 Correct 3 ms 6592 KB Output is correct
5 Correct 6 ms 6724 KB Output is correct
6 Correct 6 ms 6592 KB Output is correct
7 Correct 6 ms 6724 KB Output is correct
8 Correct 6 ms 6592 KB Output is correct
9 Correct 6 ms 6592 KB Output is correct
10 Correct 6 ms 6592 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 7924 KB Output is correct
2 Correct 83 ms 7924 KB Output is correct
3 Correct 269 ms 10020 KB Output is correct
4 Correct 276 ms 10152 KB Output is correct
5 Incorrect 696 ms 13580 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 9244 KB Output is correct
2 Correct 99 ms 8716 KB Output is correct
3 Correct 399 ms 13452 KB Output is correct
4 Correct 313 ms 12156 KB Output is correct
5 Incorrect 983 ms 20312 KB Output isn't correct
6 Halted 0 ms 0 KB -