oj.uz

Submission #569389

# Submission time Handle Problem Language Result Execution time Memory
569389 2022-05-27T11:07:34 Z nonsensenonsense1 Reconstruction Project (JOI22_reconstruction) C++17
3 / 100
 3 ms 340 KB 
#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[N];
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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 3 ms 212 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 3 ms 212 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Incorrect 1 ms 340 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 320 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 3 ms 212 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Incorrect 1 ms 340 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 3 ms 212 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Incorrect 1 ms 340 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 3 ms 212 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Incorrect 1 ms 340 KB Output isn't correct
21 Halted 0 ms 0 KB -