oj.uz

Submission #157535

# Submission time Handle Problem Language Result Execution time Memory
157535 2019-10-12T08:30:48 Z oolimry Ideal city (IOI12_city) C++14
100 / 100
 447 ms 22852 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
long long ans = 0, cnt = -1;
typedef pair<long long, long long> ii;

map<ii, bool> vis;
long long sz[100005];
long long deg[100005];
set<int> adj[100005];
queue<int> leaf;
void dfs(ii u, int p){
	if(vis.find(u) == vis.end()) return;
	if(vis[u]) return;
	ii v = u;
	cnt++;
	vector<ii> arr;
	while(vis.find(v) != vis.end()){
		vis[v] = true;
		arr.push_back(v);
		v.first++;
	}
	v = ii(u.first-1,u.second);
	while(vis.find(v) != vis.end()){
		vis[v] = true;
		arr.push_back(v);
		v.first--;
	}
	int curcnt = cnt;
	sz[curcnt] = arr.size();
	
	if(p != -1){
		adj[curcnt].insert(p);
		adj[p].insert(curcnt);
		deg[curcnt]++;
		deg[p]++;
	}
	/*
	cout << curcnt << " " << p << "\n";
	cout << cnt << ": ";
	for(int i = 0;i < arr.size();i++){
		cout << "(" << arr[i].first << ", " << arr[i].second << ") ";
	}
	cout << "\n";
	*/
	for(int i = 0;i < arr.size();i++){
		ii u = arr[i];
		dfs(ii(u.first,u.second+1),curcnt);
		dfs(ii(u.first,u.second-1),curcnt);
	}
	
}
void calculate(int *X, int *Y){
	cnt = -1;
	fill(sz,sz+n,0);
	fill(deg,deg+n,0);
	
	vis.clear();
	vector<ii> arr;
	for(int i = 0;i < n;i++){
		vis[ii(X[i],Y[i])] = false;
		adj[i].clear();
	}
	dfs(ii(X[0],Y[0]),-1);
	for(int i = 0;;i++){
		if(deg[i] == 0) break;
		if(deg[i] == 1) leaf.push(i);
	}
	
	while(true){
		int u = leaf.front();
		leaf.pop();
		if(adj[u].size() != 1) break;
		
		int v = *adj[u].begin();
		adj[v].erase(u);
		
		ans += sz[u] * (n - sz[u]);
		ans %= 1000000000ll;
		sz[v] += sz[u];
		if(adj[v].size() == 1){
			leaf.push(v);
		}
	}
}
int DistanceSum(int N, int *X, int *Y) {
	n = N;
	calculate(X,Y);
	calculate(Y,X);
	return ans % 1000000000ll;
}

Compilation message

city.cpp: In function 'void dfs(ii, int)':
city.cpp:47:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < arr.size();i++){
                ~~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7288 KB Output is correct
2 Correct 59 ms 7376 KB Output is correct
3 Correct 163 ms 10488 KB Output is correct
4 Correct 166 ms 10360 KB Output is correct
5 Correct 385 ms 16184 KB Output is correct
6 Correct 375 ms 16376 KB Output is correct
7 Correct 347 ms 16648 KB Output is correct
8 Correct 447 ms 17144 KB Output is correct
9 Correct 361 ms 16588 KB Output is correct
10 Correct 427 ms 22852 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7668 KB Output is correct
2 Correct 57 ms 7544 KB Output is correct
3 Correct 182 ms 11512 KB Output is correct
4 Correct 173 ms 10896 KB Output is correct
5 Correct 353 ms 17820 KB Output is correct
6 Correct 337 ms 16872 KB Output is correct
7 Correct 360 ms 18948 KB Output is correct
8 Correct 338 ms 16692 KB Output is correct
9 Correct 342 ms 15736 KB Output is correct
10 Correct 361 ms 15644 KB Output is correct