Submission #963469

#	Time	Username	Problem	Language	Result	Execution time	Memory
963469		vjudge1	City Mapping (NOI18_citymapping)	C++17	Compilation error	0 ms	0 KiB

citymapping

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

static int N, Q, S, twok[1005][11], depth[1005], curQ, target = 6500;
static long long dist[1005];
static vector< pair<int, int> > adjlist[1005];
static vector< pair< pair<int, int>, int > > edgelist, user_edgelist;

static void dfs(int x, int p, long long d, int dep) {
	dist[x] = d;
	depth[x] = dep;
	twok[x][0] = p;
	for (int i = 1; i <= 10; i++) {
		if (twok[x][i - 1] == -1) break;
		twok[x][i] = twok[twok[x][i - 1]][i - 1];
	}
	for (int i = 0; i < (int)adjlist[x].size(); i++) {
		if (adjlist[x][i].first == p) continue;
		dfs(adjlist[x][i].first, x, d + adjlist[x][i].second, dep + 1);
	}
}

static int lca(int x, int y) {
	if (depth[x] > depth[y]) swap(x, y);
	int dd = depth[y] - depth[x];
	for (int i = 0; i <= 10; i++) if (dd & (1 << i)) y = twok[y][i];
	if (x == y) return x;
	for (int i = 10; i >= 0; i--) {
		if (twok[x][i] != twok[y][i]) {
			x = twok[x][i];
			y = twok[y][i];
		}
	}
	return twok[x][0];
}

long long get_distance(int X, int Y) {
	if (X <= 0 || X > N || Y <= 0 || Y > N) {
		printf("Wrong Answer: get_distance() arguments out of range.\n");
		exit(0);
	}
	curQ++;
	if (curQ > Q) {
		printf("Wrong Answer: Too many calls to get_distance().\n");
		exit(0);
	}
	return dist[X-1] + dist[Y-1] - dist[lca(X-1, Y-1)] * 2;
}
	

int main() {
	if (scanf("%d%d%d", &N, &Q, &S) != 3) {
		printf("Wrong Input Format\n");
		exit(0);
	}
	for (int i = 0; i < N - 1; i++) {
		int a, b, w;
		if (scanf("%d%d%d", &a, &b, &w) != 3) {
			printf("Wrong Input Format\n");
			return 0;
		}
		a--;
		b--;
		adjlist[a].push_back(make_pair(b, w));
		adjlist[b].push_back(make_pair(a, w));
		edgelist.push_back(make_pair(make_pair(min(a, b) + 1, max(a, b) + 1), w));
	}
	sort(edgelist.begin(), edgelist.end());
	memset(twok, -1, sizeof(twok));
	dfs(0, -1, 0, 0);
	int A[N-1], B[N-1], W[N-1];
	memset(A, 0, sizeof(A));
	memset(B, 0, sizeof(B));
	memset(W, 0, sizeof(W));
	find_roads(N, Q, A, B, W);
	for (int i = 0; i < N-1; i++) user_edgelist.push_back(make_pair(make_pair(min(A[i], B[i]), max(A[i], B[i])), W[i]));
	sort(user_edgelist.begin(), user_edgelist.end());
	if (edgelist != user_edgelist) {
		printf("Wrong Answer: Reported list of edges differ from actual.\n");
		exit(0);
	}
	if (S <= 4) {
		printf("Score: 100.00%%\nCorrect: %d out of %d queries used.\n", curQ, Q);
		exit(0);
	} else {
		if (curQ <= target) printf("Score: 100.00%%\nCorrect: %d out of %d queries used.\n", curQ, Q);
		else if (curQ >= 12000) printf("Score: %.2lf%%\nCorrect: %d out of %d queries used.\n", (10.0-10.0*((double)(curQ - 12000) / 13000)) / 43 * 100, curQ, Q);
		else printf("Score: %.2lf%%\nCorrect: %d out of %d queries used.\n", (40.0-30.0*((double)(curQ - target) / (12000 - target))) / 43 * 100, curQ, Q);
	}
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccVL1OYg.o: in function `get_distance(int, int)':
grader.cpp:(.text+0x470): multiple definition of `get_distance(int, int)'; /tmp/ccElkjLj.o:citymapping.cpp:(.text+0x470): first defined here
/usr/bin/ld: /tmp/ccVL1OYg.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccElkjLj.o:citymapping.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccElkjLj.o: in function `main':
citymapping.cpp:(.text.startup+0x3b2): undefined reference to `find_roads(int, int, int*, int*, int*)'
/usr/bin/ld: /tmp/ccVL1OYg.o: in function `main':
grader.cpp:(.text.startup+0x39a): undefined reference to `find_roads(int, int, int*, int*, int*)'
collect2: error: ld returned 1 exit status