제출 #1287250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287250		akari310	Papričice (COCI20_papricice)	C++17	50 / 110	1095 ms	15356 KiB

papricice

// Akari - nna310
/*
   Link: https://oj.vnoi.info/problem/coci2021_r1_papricice
*/

// #pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define G(i, a, b) for(int x, y, i = (int)(a); i <= (int)(b); ++i)
#define L(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
#define R(i, a, b) for(int i = (int)(a); i >= (int)(b); --i)
#define F(x, c) for(auto &x : c)
#define umap unordered_map
#define pb push_back
#define ve vector
#define se second
#define fi first
#define pe pair
using namespace std;
using ll = long long;
const int N = 200005;
const ll INF = 1e17 + 5;
const int MOD = 1000000007;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n, timer, in[N], out[N], sz[N], res = MOD;
pe<int, int> uv[N];
ve<int> g[N];
namespace sub2 {
void DFS(int u, int p) {
	in[u] = ++timer;
	sz[u] = 1;
	for (int v : g[u]) {
		if (v != p) {
			DFS(v, u);
			sz[u] += sz[v];
		}
	}
	out[u] = timer;
}
void sol() {
	DFS(1, -1);
	L(i, 2, n) {
		L(j, i + 1, n) {
			if (i != j) {
				if (in[i] <= in[j] && in[j] <= out[i]) {
					int a = sz[j];
					int b = sz[i] - a;
					int c = n - sz[i];
					res = min(res, max({a, b, c}) - min({a, b, c}));
				} else if (in[j] <= in[i] && in[i] <= out[j]) {
					int a = sz[i];
					int b = sz[j] - a;
					int c = n - sz[j];
					res = min(res, max({a, b, c}) - min({a, b, c}));
				} else {
					int a = sz[i];
					int b = sz[j];
					int c = n - a - b;
					res = min(res, max({a, b, c}) - min({a, b, c}));
				}
			}
		}
	}
}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	auto t_start = chrono::high_resolution_clock::now();
	if (fopen("papricice.inp", "r")) {
		freopen("papricice.inp", "r", stdin);
		freopen("papricice.out", "w", stdout);
	}
	cin >> n;
	L(i, 1, n - 1) {
		cin >> uv[i].fi >> uv[i].se;
		g[uv[i].fi].pb(uv[i].se);
		g[uv[i].se].pb(uv[i].fi);
	}

	sub2::sol();

	cout << res;

	auto t_end = chrono::high_resolution_clock::now();
	auto elapsed = chrono::duration_cast<chrono::milliseconds>(t_end - t_start).count();
	cerr << "\n\nElapsed time: " << elapsed << " ms\n";
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 0 / 60