Submission #569390

#	Time	Username	Problem	Language	Result	Execution time	Memory
569390		nonsensenonsense1	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	787 ms	27540 KiB

reconstruction

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

const int N = 500;
const int M = 100000;
int n, m, q;
std::pair<int, std::pair<int, int> > a[M];
std::vector<std::pair<int, int> > g[N];

int dfs(int v, int to, int pr = -1) {
	if (v == to) return ~(1 << 31);
	for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i].first != pr) {
		int k = dfs(g[v][i].first, to, v);
		if (k != (1 << 31)) return std::min(k, g[v][i].second);
	}
	return 1 << 31;
}

void rm(int u, int v) {
	for (int t = 0; t < 2; ++t) {
		int i;
		for (i = 0; g[u][i].first != v; ++i);
		g[u].erase(g[u].begin() + i);
		std::swap(u, v);
	}
}

void add(int u, int v, int i) {
	for (int t = 0; t < 2; ++t) {
		g[u].push_back(std::make_pair(v, i));
		std::swap(u, v);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
		scanf("%d%d%d", &a[i].second.first, &a[i].second.second, &a[i].first);
		--a[i].second.first;
		--a[i].second.second;
	}
	std::sort(a, a + m);
	std::vector<std::pair<int, std::pair<int, int> > > upd;
	for (int i = 0; i < m; ++i) {
		int e = dfs(a[i].second.first, a[i].second.second);
		if (e == (1 << 31)) upd.push_back({0, {-1, a[i].first}});
		else {
			upd.push_back({a[i].first + a[e].first + 1 >> 1, {-2, a[i].first + a[e].first}});
			rm(a[e].second.first, a[e].second.second);
		}
		add(a[i].second.first, a[i].second.second, i);
		upd.push_back({a[i].first, {2, -2 * a[i].first}});
	}
	std::sort(upd.begin(), upd.end());
	scanf("%d", &q);
	int k = 0;
	long long b = 0;
	for (int i = 0; q; --q) {
		int x;
		scanf("%d", &x);
		while (i < (int)upd.size() && upd[i].first <= x) {
			k += upd[i].second.first;
			b += upd[i].second.second;
			++i;
		}
		printf("%lld\n", (long long)k * x + b);
	}
	return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:49:43: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |    upd.push_back({a[i].first + a[e].first + 1 >> 1, {-2, a[i].first + a[e].first}});
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~^~~
reconstruction.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
reconstruction.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |   scanf("%d%d%d", &a[i].second.first, &a[i].second.second, &a[i].first);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
reconstruction.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23