제출 #157533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
157533		oolimry	이상적인 도시 (IOI12_city)	C++14	32 / 100	384 ms	15944 KiB

city

#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[10005];
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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45