oj.uz

Submission #157534

# Submission time Handle Problem Language Result Execution time Memory
157534 2019-10-12T08:28:56 Z oolimry Ideal city (IOI12_city) C++14
32 / 100
 439 ms 17788 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;
int sz[100005];
int 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]++;
	}

	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]);
		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:40: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 4988 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct
11 Correct 6 ms 4984 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 8 ms 5112 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 5244 KB Output is correct
6 Correct 10 ms 5240 KB Output is correct
7 Correct 10 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
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7032 KB Output is correct
2 Correct 58 ms 7252 KB Output is correct
3 Correct 161 ms 10056 KB Output is correct
4 Correct 160 ms 9976 KB Output is correct
5 Incorrect 439 ms 15492 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7512 KB Output is correct
2 Correct 55 ms 7384 KB Output is correct
3 Correct 157 ms 11084 KB Output is correct
4 Correct 153 ms 11000 KB Output is correct
5 Incorrect 355 ms 17788 KB Output isn't correct
6 Halted 0 ms 0 KB -