제출 #317795

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

city

//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9;
int n, ans;
vector<pair<int, int > > ps;
vector<vector<int > > edges;
vector<pair<int, pair<int, int > > > cur;

int dfs(int u,int p){
	int size = cur[u].second.second - cur[u].second.first + 1;
	for(auto x:edges[u]){
		if(x==p) continue;
		size += dfs(x, u);
	}
	ans = (ans + (n-size)*size) % mod;
	return size;
}

void build_tree(){
	cur.clear();
	sort(ps.begin(), ps.end());

	for(int i=0;i<n;i++){
		int j=i;
		while(j+1 < n && ps[i].first == ps[j+1].first && ps[j].second+1 == ps[j+1].second) j++;
		cur.push_back({ps[i].first, {ps[i].second, ps[j].second}});
		i=j;
	}

	edges.clear();
	edges.resize(n);
	int j=0; 

	for(int i=0;i<cur.size();i++){
		while(j < cur.size() && cur[j].first < cur[i].first+1) j++;
		if(j == cur.size()) break;
		while(j<n-1 && cur[j].second.second < cur[i].second.first && cur[j].first == cur[i].first+1 ) j++;
		while(j<=n-1 && cur[j].second.second <= cur[i].second.second && cur[j].first == cur[i].first+1 ){
			edges[i].push_back(j);
			edges[j].push_back(i);
			j++;
		}
		if(j != n && cur[j].second.first <= cur[i].second.second && cur[i].first+1 == cur[j].first){
			edges[i].push_back(j);
			edges[j].push_back(i);
		}
	}
	dfs(0, 0);
}
int DistanceSum(int N, int *x, int *y) {
	n=N;
	ps.resize(n);
	for(int i=0;i<n;i++)
		ps[i] = {x[i], y[i]};
	build_tree();
	for(int i=0;i<n;i++)
		swap(ps[i].first, ps[i].second);
	build_tree();
	return ans;
}

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

city.cpp: In function 'void build_tree()':
city.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<cur.size();i++){
      |              ~^~~~~~~~~~~
city.cpp:37:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   while(j < cur.size() && cur[j].first < cur[i].first+1) j++;
      |         ~~^~~~~~~~~~~~
city.cpp:38:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   if(j == cur.size()) break;
      |      ~~^~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45