oj.uz

Submission #1624

# Submission time Handle Problem Language Result Execution time Memory
1624 2013-07-10T17:54:54 Z model_code Ideal city (IOI12_city) C++
100 / 100
 94 ms 16972 KB 
/*
  O(N*logN) solution for City.

  Author: Giovanni Paolini
*/

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Point {
	int x;
	int y;
	
	Point() {}
	
	Point(int _x, int _y) {
		x = _x;
		y = _y;
	}
};

bool operator< (const Point &a, const Point &b) {
	if ( a.x != b.x ) return ( a.x < b.x );
	return ( a.y < b.y );
}

int const MAXN = 1000005;

int n;
Point squares[MAXN];

void read(int N, int *X, int *Y) {
	
	n = N;
	
	for (int i=0; i<n; ++i) {
	  squares[i] = Point(X[i], Y[i]);
	}
	
}

void exchange() { // Exchanges the x and y coordinates of all the points.
	for (int i=0; i<n; ++i) {
		squares[i] = Point( squares[i].y, squares[i].x );
	}
}

struct Node {
	int x;
	int ymin;
	int ymax;
	vector<int> neighbours;
	
	Node () {}
	
	Node (int _x, int _ymin, int _ymax) {
		x = _x;
		ymin = _ymin;
		ymax = _ymax;
	}
};

vector<Node> nodes;


void make_tree() { // Builds the tree of vertically/horizontally-collapsed nodes
	
	sort( squares, squares + n );
	nodes.clear();
	
	// Create nodes
	
	int cont = 0;
	while ( cont < n ) {
		int x = squares[cont].x;
		int ymin = squares[cont].y;
		
		int y = ymin;
		
		int i;
		for (i=cont+1; i<n; ++i) {
			if ( squares[i].y == y+1 ) y++;
			else break;
		}
		
		int ymax = y;
		cont = i;
		
		nodes.push_back( Node( x, ymin, ymax ) );
	}
	
	// Create edges
	
	int cont1,cont2;
	
	cont1 = 0;
	for ( cont2 = 1; cont2 < nodes.size(); cont2++ ) {
		while ( ( nodes[cont1].x + 1 < nodes[cont2].x ) || ( nodes[cont1].x + 1 == nodes[cont2].x && nodes[cont1].ymax < nodes[cont2].ymin ) ) cont1++;
		
		int numedges = 0;
		while ( nodes[cont1].x + 1 == nodes[cont2].x && nodes[cont1].ymin <= nodes[cont2].ymax ) {
			numedges++;
			nodes[cont1].neighbours.push_back(cont2);
			nodes[cont2].neighbours.push_back(cont1);
			cont1++;
		}
		if ( numedges > 0 ) cont1--;
	}
	
}

int weight (int i) {
	return nodes[i].ymax - nodes[i].ymin + 1;
}

bool visited[MAXN];
long long int s; // sum of all weights
long long int tot; // required total
long long int const MOD = 1000000000;

long long int dfs (int k) {
	if ( visited[k] ) return 0;
	
	visited[k] = 1;
	
	long long int w = weight(k);
	for (int i=0; i<nodes[k].neighbours.size(); ++i) {
		w += dfs( nodes[k].neighbours[i] );
		w %= MOD;
	}
	
	tot += w * (s - w);
	tot %= MOD;
	
	return w;
}

long long int sum () {
	make_tree();
	
	s = 0;
	tot = 0;
	for (int i=0; i<nodes.size(); ++i) {
		s += weight(i);
		s %= MOD;
		visited[i] = 0;
	}
	
	dfs(0);
	
	return tot;
}

int DistanceSum(int N, int *X, int *Y) {
	
	read(N, X, Y);
	
	// Find the horizontal sum
	long long int first = sum();
	
	exchange();
	
	// Find the vertical sum
	long long int second = sum();
	
	long long int sol = first + second;
	sol %= MOD;
	
	return sol;
	
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10396 KB Output is correct
2 Correct 11 ms 10560 KB Output is correct
3 Correct 25 ms 10716 KB Output is correct
4 Correct 24 ms 10884 KB Output is correct
5 Correct 52 ms 11108 KB Output is correct
6 Correct 64 ms 11276 KB Output is correct
7 Correct 66 ms 11288 KB Output is correct
8 Correct 62 ms 11108 KB Output is correct
9 Correct 53 ms 11512 KB Output is correct
10 Correct 69 ms 14748 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11180 KB Output is correct
2 Correct 15 ms 11180 KB Output is correct
3 Correct 38 ms 13604 KB Output is correct
4 Correct 38 ms 12116 KB Output is correct
5 Correct 94 ms 16972 KB Output is correct
6 Correct 75 ms 12508 KB Output is correct
7 Correct 82 ms 16972 KB Output is correct
8 Correct 60 ms 12508 KB Output is correct
9 Correct 72 ms 12508 KB Output is correct
10 Correct 68 ms 12508 KB Output is correct