oj.uz

Submission #763499

# Submission time Handle Problem Language Result Execution time Memory
763499 2023-06-22T11:32:06 Z fanwen Papričice (COCI20_papricice) C++17
110 / 110
 198 ms 23360 KB 
/**
 *      author : pham van sam
 *      created : 22 June 2023 (Thursday)
 **/

#include <bits/stdc++.h>

using namespace std;
using namespace chrono;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

template <typename U, typename V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <typename U, typename V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }

const int MAXN = 2e5 + 5;

int N, num_child[MAXN], ans;
vector <int> adj[MAXN];

void dfs(int u, int p) {
	num_child[u] = 1;
	for (auto v : adj[u]) if(v != p) {
		dfs(v, u);
		num_child[u] += num_child[v];
	}
}

int get(int a, int b, int c) {
	if(a > b) swap(a, b);
	return max(b, c) - min(a, c);
}
set <int> same, diff;

vector <int> optimize(set <int> &s, int res) {
	auto it = s.upper_bound(res);
	vector <int> ans;
	if(it != s.end()) ans.push_back(*it);
	if(it != s.begin()) it--, ans.push_back(*it);
	return ans;
}

void calc(int u, int p) {
	for (auto x : optimize(same, (N + num_child[u]) / 2)) minimize(ans, get(num_child[u], x - num_child[u], N - x));
	for (auto x : optimize(diff, (N - num_child[u]) / 2)) minimize(ans, get(num_child[u], x, N - num_child[u] - x));
	same.insert(num_child[u]);
	for (auto v : adj[u]) if(v != p) calc(v, u);
	same.erase(num_child[u]);
	
	diff.insert(num_child[u]);
}

void process(void) {
	cin >> N;
	FOR(i, 2, N) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, 0);
	ans = N;
	calc(1, 0);
	cout << ans;
}

signed main() {

    #define TASK "TASK"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    auto start_time = steady_clock::now();
    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; ++i) {
        process();
        // cout << '\n';
    }

    auto end_time = steady_clock::now();

    cerr << "\nExecution time : " << duration_cast<milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

Compilation message

papricice.cpp: In function 'int main()':
papricice.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
papricice.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 151 ms 12232 KB Output is correct
12 Correct 117 ms 14680 KB Output is correct
13 Correct 89 ms 15036 KB Output is correct
14 Correct 126 ms 14860 KB Output is correct
15 Correct 112 ms 14680 KB Output is correct
16 Correct 91 ms 14552 KB Output is correct
17 Correct 102 ms 14724 KB Output is correct
18 Correct 198 ms 23360 KB Output is correct
19 Correct 94 ms 14764 KB Output is correct
20 Correct 113 ms 14744 KB Output is correct