Submission #2911

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
2911	2013-08-03T09:56:52 Z	astein	Game (IOI13_game)	C++	Compilation error	0 ms	0 KB

game

#include "game.h"
#include <cstring>
#include <queue>
#include <cstdio>
#include <cassert>

using namespace std;

struct Node {
	Node *lu, *ld, *ru, *rd;
	Node* parent;

	int sx, sy, ex, ey;
	long long value;

	Node(int x1, int y1, int x2, int y2, long long v) : sx(x1), sy(y1), ex(x2), ey(y2), value(v) { lu = 0, ld = 0, ru = 0, rd = 0; }
};

Node* root;

void init(int R, int C) {
  root = new Node(0, 0, R - 1, C - 1, 0);
}

void update(int x, int y, long long v) {
	Node* next = root;
	while (true) {
		int sx = next->sx, sy = next->sy, ex = next->ex, ey = next->ey;
		if (sx == ex && sy == ey && x == sx && y == sy) {
			//printf("%d, %d - %d, %d : %lld\n", sx, sy, ex, ey, v);
			next->value = v;
			break;
		}

		int mx = (sx + ex) / 2;
		int my = (sy + ey) / 2;

		if (sx <= x && x <= mx) {
			if (sy <= y && y <= my) {
				// lu
				if (!next->lu) { 
					Node* child = new Node(sx, sy, mx, my, 0);
					child->parent = next;
					next->lu = child;
				}
				next = next->lu;
			} else {
				// ru
				if (!next->ru) { 
					Node* child = new Node(sx, my + 1, mx, ey, 0);
					child->parent = next;
					next->ru = child;
				}
				next = next->ru;
			}
		} else {
			if (sy <= y && y <= my) {
				// ld
				if (!next->ld) { 
					Node* child = new Node(mx + 1, sy, ex, my, 0);
					child->parent = next;
					next->ld = child;
				}
				next = next->ld;
			} else {
				// rd
				if (!next->rd) {
					Node* child = new Node(mx + 1, my + 1, ex, ey, 0);
					child->parent = next;
					next->rd = child;
				}
				next = next->rd;
			}
		}
	}

	Node* up;
	while (next != root) {
		next = next->parent;

		long long g = 0;
		if (next->lu) g = gcd2(next->lu->value, g);
		if (next->ru) g = gcd2(next->ru->value, g);
		if (next->ld) g = gcd2(next->ld->value, g);
		if (next->rd) g = gcd2(next->rd->value, g);
		next->value = g;
		//printf("%d, %d - %d, %d : %lld\n", next->sx, next->sy, next->ex, next->ey, next->value);
	}
}

long long go(int x1, int y1, int x2, int y2, Node* now) {
  long long g = 0;
	if (x1 <= now->sx && y1 <= now->sy && now->ex <= x2 && now->ey <= y2) {
	  return now->value;
	}
	if (now->sx > x2 || now->sy > y2) return 0;
	if (now->ex < x1 || now->ey < y1) return 0;

	if (now->lu) g = gcd2(g, go(x1, y1, x2, y2, now->lu));
	if (now->ld) g = gcd2(g, go(x1, y1, x2, y2, now->ld));
	if (now->ru) g = gcd2(g, go(x1, y1, x2, y2, now->ru));
	if (now->rd) g = gcd2(g, go(x1, y1, x2, y2, now->rd));

  return g;
}

long long calculate(int x1, int y1, int x2, int y2) {
  return go(x1, y1, x2, y2, root);
/*  long long g = 0;

	queue<Node*> Q;
	Q.push(root);

	long long g = 0;
	while (!Q.empty()) {
		Node* now = Q.front(); Q.pop();
		if (x1 <= now->sx && y1 <= now->sy && now->ex <= x2 && now->ey <= y2) {
			g = gcd2(now->value, g);
			continue;
		}
		if (now->sx > x2) continue;
		if (now->sy > y2) continue;
		if (now->ex < x1) continue;
		if (now->ey < y1) continue;

		if (now->lu) Q.push(now->lu);
		if (now->ld) Q.push(now->ld);
		if (now->ru) Q.push(now->ru);
		if (now->rd) Q.push(now->rd);
	}

	return g;*/
}

void clear(Node* now) {
	queue<Node*> Q;
	Q.push(now);
	int numNode = 0;
	while (!Q.empty()) {
		now = Q.front(); Q.pop();

		if (now->lu) Q.push(now->lu);
		if (now->ld) Q.push(now->ld);
		if (now->ru) Q.push(now->ru);
		if (now->rd) Q.push(now->rd);
		now->parent = 0;
		numNode++;
		delete now;
	}
//	printf("total memory = %d\n", numNode * sizeof(Node));
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
game.cpp: In function 'void update(int, int, long long int)':
game.cpp:82:44: error: 'gcd2' was not declared in this scope
game.cpp:83:44: error: 'gcd2' was not declared in this scope
game.cpp:84:44: error: 'gcd2' was not declared in this scope
game.cpp:85:44: error: 'gcd2' was not declared in this scope
game.cpp:77:8: warning: unused variable 'up' [-Wunused-variable]
game.cpp: In function 'long long int go(int, int, int, int, Node*)':
game.cpp:99:54: error: 'gcd2' was not declared in this scope
game.cpp:100:54: error: 'gcd2' was not declared in this scope
game.cpp:101:54: error: 'gcd2' was not declared in this scope
game.cpp:102:54: error: 'gcd2' was not declared in this scope