oj.uz

Submission #317761

# Submission time Handle Problem Language Result Execution time Memory
317761 2020-10-30T10:34:33 Z amunduzbaev Ideal city (IOI12_city) C++14
32 / 100
 61 ms 6896 KB 
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2005, mod= 1e9;
int n;
ll 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 += (n-size)*size % mod;
	ans%=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[j].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}});
		//cout<<ps[i].first<<" "<<ps[i].second << " "<<ps[j].second<<"\n";
		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) 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;
	edges.resize(n);
	for(int i=0;i<n;i++)
		ps.push_back({x[i], y[i]});

	build_tree();
	for(int i=0;i<n;i++)
		swap(ps[i].first, ps[i].second);
	build_tree();
	return ans;

}

/*

11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6

ans 174


15
3 1
4 1
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
2 4
3 4
4 4
5 4



*/

Compilation message

city.cpp: In function 'void build_tree()':
city.cpp:35: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]
   35 |  for(int i=0;i<cur.size();i++){
      |              ~^~~~~~~~~~~
city.cpp:36:10: 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 |   while(j<cur.size() && cur[j].first <= cur[i].first) j++;
      |         ~^~~~~~~~~~~
city.cpp:37: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]
   37 |   if(j == cur.size()) break;
      |      ~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1536 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 26 ms 2944 KB Output is correct
4 Correct 24 ms 2944 KB Output is correct
5 Incorrect 46 ms 5492 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1660 KB Output is correct
2 Correct 11 ms 1660 KB Output is correct
3 Correct 31 ms 3700 KB Output is correct
4 Correct 27 ms 3324 KB Output is correct
5 Incorrect 61 ms 6896 KB Output isn't correct
6 Halted 0 ms 0 KB -