Submission #785036

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

citymapping

#include<bits/stdc++.h>
#include "citymapping.h"
using namespace std;
const int N = 1000;
long long distances[N][N];
long long get_dst(int x, int y) {
	if (x > y) {
		swap(x, y);
	}
	auto &ret = distances[x][y];
	if (~ret)
		return ret;
	}
	return ret = get_distance(x + 1, y + 1);
}
long long &dist(int x, int y) {
	if (x > y) {
		swap(x, y);
	}
	return distances[x][y];
}
int sizeSubtree[N];
int counter;
vector<pair<int, int> > children[N];
bool visited[N];
vector<pair<int, int> > heavy;
void dfs(int u, int p) {
	sizeSubtree[u] = 1;
	counter++;
	for (pair<int, int> x : adj[u]){
        int v = x.first;
		if (!visited[v]) {
			dist(p, v) = dist(p, u) + to.second;
			dfs(v, p);
			sizeSubtree[u] += sizeSubtree[v];
		}
	}
}
int dfs2(int u) {
	pair<int, int> maxVal = {-1, -1};
	for (pair<int, int> x : children[u]){
        int v = x.first;
		if (!visited[v] && (mx.first == -1 || sizeSubtree[maxVal.first] < sizeSubtree[v])) {
			maxVal = to;
		}
	}
	if (~maxVal.first) {
		heavy.push_back(maxVal);
		return dfs2(mx.first);
	}
	return u;
}
void find_roads(int n, int q, int a[], int b[], int w[]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			distances[i][j] = -1;
		}
	}
	for (int i = 0; i < n; i++) {
		dist(i, i) = 0;
	}
	vector<pair<long long, int>> ds;
	for (int i = 1; i < n; i++) {
		ds.push_back({get_dst(0, i), i});
	}
	sort(ds.begin(), ds.end());
	int m = 0;
	for (auto &x: ds) {
		int r = 0;
		while (true) {
			counter = 0;
			dfs(r, r);
			if (counter == 1) {
				break;
			}
			int l = dfs2(r);
			long long xl = get_dst(x.second, l), rm = (get_dst(r, x.second) + get_dst(r, l) - xl) / 2;
			for (auto &y: lst) {
				visited[y.first] = 1;
			}
			int i = 0;
			while (rm > 0) {
				rm -= lst[i++].second;
			}
			int M = (i ? lst[i - 1].first: r);
		    dist(M, x.second) = (get_dst(r, x.second) + get_dst(l, x.second) - get_dst(r, l)) / 2;
			lst.clear();
			r = M;
		}
		a[m] = 1 + r;
        b[m] = 1 + x.second;
        w[m] = dist(r, x.second);
		children[r].push_back({b[m] - 1, w[m]});
		dist(r, b[m] - 1) = w[m];
		m++;
		for (int i = 0; i < n; i++) {
			visited[i] = 0;
		}
	}

}

Compilation message (stderr)

citymapping.cpp:14:2: error: expected unqualified-id before 'return'
   14 |  return ret = get_distance(x + 1, y + 1);
      |  ^~~~~~
citymapping.cpp:15:1: error: expected declaration before '}' token
   15 | }
      | ^
citymapping.cpp: In function 'void dfs(int, int)':
citymapping.cpp:30:26: error: 'adj' was not declared in this scope
   30 |  for (pair<int, int> x : adj[u]){
      |                          ^~~
citymapping.cpp:33:30: error: 'to' was not declared in this scope; did you mean 'tm'?
   33 |    dist(p, v) = dist(p, u) + to.second;
      |                              ^~
      |                              tm
citymapping.cpp: In function 'int dfs2(int)':
citymapping.cpp:43:23: error: 'mx' was not declared in this scope; did you mean 'x'?
   43 |   if (!visited[v] && (mx.first == -1 || sizeSubtree[maxVal.first] < sizeSubtree[v])) {
      |                       ^~
      |                       x
citymapping.cpp:44:13: error: 'to' was not declared in this scope; did you mean 'tm'?
   44 |    maxVal = to;
      |             ^~
      |             tm
citymapping.cpp:49:15: error: 'mx' was not declared in this scope
   49 |   return dfs2(mx.first);
      |               ^~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:78:18: error: 'lst' was not declared in this scope
   78 |    for (auto &y: lst) {
      |                  ^~~
citymapping.cpp:83:11: error: 'lst' was not declared in this scope
   83 |     rm -= lst[i++].second;
      |           ^~~
citymapping.cpp:85:17: error: 'lst' was not declared in this scope
   85 |    int M = (i ? lst[i - 1].first: r);
      |                 ^~~
citymapping.cpp: In function 'long long int get_dst(int, int)':
citymapping.cpp:13:2: warning: control reaches end of non-void function [-Wreturn-type]
   13 |  }
      |  ^