oj.uz

답안 #157536

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
157536 2019-10-12T08:31:35 Z oolimry 이상적인 도시 (IOI12_city) C++14
100 / 100
 413 ms 22316 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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4956 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 4984 KB Output is correct
8 Correct 6 ms 4984 KB Output is correct
9 Correct 6 ms 4984 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

# 결과 실행 시간 메모리 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 5240 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
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 7388 KB Output is correct
2 Correct 60 ms 7380 KB Output is correct
3 Correct 157 ms 10516 KB Output is correct
4 Correct 161 ms 10460 KB Output is correct
5 Correct 382 ms 16248 KB Output is correct
6 Correct 381 ms 15832 KB Output is correct
7 Correct 351 ms 15864 KB Output is correct
8 Correct 413 ms 16376 KB Output is correct
9 Correct 365 ms 15876 KB Output is correct
10 Correct 336 ms 22316 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 7672 KB Output is correct
2 Correct 55 ms 7544 KB Output is correct
3 Correct 170 ms 11480 KB Output is correct
4 Correct 143 ms 10872 KB Output is correct
5 Correct 351 ms 17800 KB Output is correct
6 Correct 313 ms 16120 KB Output is correct
7 Correct 353 ms 18040 KB Output is correct
8 Correct 360 ms 15864 KB Output is correct
9 Correct 327 ms 15204 KB Output is correct
10 Correct 334 ms 15096 KB Output is correct