Submission #23435

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
23435	2017-05-09T11:55:21 Z	ztrong	Park (BOI16_park)	C++14	Compilation error	0 ms	0 KB

park

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i)
#define REP(i, a) for (int i = 0, _a = a; i < _a; ++i)
#define llint long long
#define sz(x) (x.size())
#define LL(x) (x * 2)
#define RR(x) (x * 2 + 1)
#define fi first
#define se second
#define db(x) cout << #x << " = " << x << endl;
#define BIT(x, i) ((x >> i) & 1)
#define MASK(i) (1ll << i)
#define times clock() * 1.0 / CLOCKS_PER_SEC

void openFile() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
//	freopen("park.inp", "r", stdin);
//	freopen("park.out", "w", stdout);
}

const int maxN = 2e3 + 5;
const int maxM = 1e5 + 5;
const llint INF = 1e9 + 7;

int N, M;
int W, H;
struct tree {
	int x, y, r;
} a[maxN];
struct guess {
	int r, e, id;

	bool operator < (const guess &a) const {
		return r < a.r;
	}
} g[maxM];
struct edge {
	int u, v;
	llint len;

	bool operator < (const edge &a) const {
		return len < a.len;
	}
};
vector<edge> e;
string res[maxM];
int lab[maxN];

void enter() {
	scanf("%d %d", &N, &M);
	scanf("%d %d", &W, &H);
	FOR(i, 1, N) {
		scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].r);
	}
	FOR(i, 1, M) {
		scanf("%d %d", &g[i].r, &g[i].e);
		g[i].r = g[i].r * 2;
		g[i].id = i;
	}
}

llint dist(tree a, tree b) {
	return ceil(sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y))
		- a.r - b.r);
}

llint dist(llint x, llint y, llint u, llint v, llint r) {
	return ceil(sqrt(max(0.0, 1.0 * (x - u) * (x - u) + (y - v) * (y - v)) - r));
}

cedge getEdge(int u, int v) {
	return (edge) {u, v, dist(a[u], a[v])};
}

void addEdgeWall(int u) {
	e.push_back({u, N + 1, dist(a[u].x, a[u].y, a[u].x, 0, a[u].r)});
	e.push_back({u, N + 2, dist(a[u].x, a[u].y, W, a[u].y, a[u].r)});
	e.push_back({u, N + 3, dist(a[u].x, a[u].y, a[u].x, H, a[u].r)});
	e.push_back({u, N + 4, dist(a[u].x, a[u].y, 0, a[u].y, a[u].r)});
}

int find(int u) {
	return (lab[u] <= 0 ? u : lab[u] = find(lab[u]));
}

void Union(int s, int t) {
	if (lab[s] < lab[t]) {
		lab[t] = s;
	}
	else {
		if (lab[s] == lab[t]) --lab[t];
		lab[s] = t;
	}
}

void update(const edge &x) {
	int s = find(x.u), t = find(x.v);
	if (s != t) {
		Union(s, t);
	}
}

void solve() {
	FOR(i, 1, N) {
		FOR(j, i + 1, N) {
			e.push_back(getEdge(i, j));
		}
		addEdgeWall(i);
	}
	sort(e.begin(), e.end());
	sort(g + 1, g + M + 1);
	
	int j = 0;
	FOR(i, 1, M) {
		while (j < e.size() && e[j].len <= g[i].r) {
			update(e[j]);
			++j;
		}
		string RES = "";
		int x = find(N + 1), y = find(N + 2), z = find(N + 3), t = find(N + 4);
		if (g[i].e == 1) {
			RES = RES + '1';
			if (x != y && x != z && x != t) RES = RES + '2';
			if (y != z && y != t && t != x && z != y) RES = RES + '3';
			if (t != z && t != y && t != x) RES = RES + '4';
		}
		else if (g[i].e == 2) {
			if (x != t && x != z && x != y) RES = RES + '1';
			RES = RES + '2';
			if (y != z && y != t && y != x) RES = RES + '3';
			if (x != z && y != t && t != z && x != y) RES = RES + '4';
		}
		else if (g[i].e == 3) {
			if (x != t && z != y && t != y && z != x) RES = RES + '1';
			if (y != x && y != t && y != z) RES = RES + '2';
			RES = RES + '3';
			if (z != t && z != x && z != y) RES = RES + '4';
		}
		else {
			if (t != x && t != y && t != z) RES = RES + '1';
			if (x != z && t != y && t != z && x != y) RES = RES + '2';
			if (z != t && z != x && z != y) RES = RES + '3';
			RES = RES + '4';
		}
		res[g[i].id] = RES;
	}
	FOR(i, 1, M) {
		cout << res[i] << endl;
	}
}

int main() {
	openFile();
	enter();
	solve();
	return 0;
}

Compilation message

park.cpp:75:1: error: 'cedge' does not name a type
 cedge getEdge(int u, int v) {
 ^
park.cpp: In function 'void solve()':
park.cpp:110:28: error: 'getEdge' was not declared in this scope
    e.push_back(getEdge(i, j));
                            ^
park.cpp:119:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < e.size() && e[j].len <= g[i].r) {
            ^
park.cpp: In function 'void enter()':
park.cpp:54:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
                        ^
park.cpp:55:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &W, &H);
                        ^
park.cpp:57:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].r);
                                               ^
park.cpp:60:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &g[i].r, &g[i].e);
                                   ^