oj.uz

Submission #538204

# Submission time Handle Problem Language Result Execution time Memory
538204 2022-03-16T09:11:35 Z pavement Meetings 2 (JOI21_meetings2) C++17
0 / 100
 3 ms 5036 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, md, fn, st, sz[200005];
bool on_path[200005];
vector<int> path, adj[200005];

void get_diam(int n, int e = -1, int d = 0) {
	if (d > md) {
		md = d;
		fn = n;
	}
	for (auto u : adj[n]) if (u != e) get_diam(u, n, d + 1);
}

bool get_path(int n, int e = -1) {
	if (n == fn) {
		on_path[n] = 1;
		path.pb(n);
		return 1;
	}
	for (auto u : adj[n]) if (u != e)
		if (get_path(u, n)) {
			on_path[n] = 1;
			path.pb(n);
			return 1;
		}
	return 0;
}

int dfs(int n, int e = -1) {
	sz[n] = 1;
	for (auto u : adj[n]) if (u != e)
		sz[n] += dfs(u, n);
	return sz[n];
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1, u, v; i < N; i++) {
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	md = -1;
	get_diam(1);
	md = -1;
	st = fn;
	get_diam(st);
	// diameter is st --> fn
	get_path(st);
	for (int i = 1; i <= N; i++)
		if (on_path[i]) {
			sz[i] = 1;
			for (auto u : adj[i])
				if (!on_path[u]) sz[i] += dfs(u, i);
		}
	reverse(path.begin(), path.end());
	for (int k = 1, ptr = 0, ptr2 = (int)path.size() - 1; k <= N; k++) {
		if (k & 1) cout << "1\n";
		else {
			if (sz[path[ptr]] == 0) ptr++;
			sz[path[ptr]]--;
			if (sz[path[ptr2]] == 0) ptr2--;
			sz[path[ptr2]]--;
			cout << ptr2 - ptr + 1 << '\n';
		}
	}
}

Compilation message

meetings2.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main() {
      | ^~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5036 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Incorrect 3 ms 5028 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5036 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Incorrect 3 ms 5028 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5036 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Incorrect 3 ms 5028 KB Output isn't correct
7 Halted 0 ms 0 KB -