제출 #1222121

#제출 시각아이디문제언어결과실행 시간메모리
1222121huudaiPapričice (COCI20_papricice)C++20
110 / 110
173 ms39872 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ll long long #define fi first #define se second #define pii pair<int, int> #define pll pair<ll,ll> #define mp make_pair #define pb push_back #define BIT(x,i) (((x)>>(i))&1) #define MASK(i) (1LL<<(i)) template<typename T1, typename T2> bool minimize(T1 &a, T2 b) {if(a>b) a=b; else return 0; return 1;} template<typename T1, typename T2> bool maximize(T1 &a, T2 b) {if(a<b) a=b; else return 0; return 1;} #define file "task" const int maxn = 2e5 + 5; const int MOD = 1e9 + 7; const int oo = 1e9; const ll OO = 1e18; int n; int sz[maxn]; int ans = oo; vector<int> g[maxn]; set<int> ancestor; set<int> s[maxn]; int max(int a, int b, int c){ return max(max(a, b), c); } int min(int a, int b, int c){ return min(min(a, b), c); } void input(){ cin >> n; for(int i = 1; i <= n - 1; i++){ int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } } void prep(int u, int dad){ sz[u] = 1; for(int v : g[u]){ if(v == dad) continue; prep(v, u); sz[u] += sz[v]; } } void get(set<int> &s, int w){ int sum = n - w; auto it = s.lower_bound(sum / 2); if(it != s.end()){ minimize(ans, max(w, (*it), sum - (*it)) - min(w, (*it), sum - (*it))); } if(it != s.begin()){ it--; minimize(ans, max(w, (*it), sum - (*it)) - min(w, (*it), sum - (*it))); } } void dfs(int v, int dad){ for(int u : g[v]){ if(u == dad) continue; dfs(u, v); //dsu on tree if(s[u].size() > s[v].size()) swap(s[u], s[v]); for(int w : s[u]){ get(s[v], w); } for(int w : s[u]){ s[v].insert(w); } } get(s[v], n - sz[v]); s[v].insert(sz[v]); } void proc(){ ans = oo; prep(1, 1); dfs(1, 1); cout << ans; } signed main(){ cin.tie(nullptr)->sync_with_stdio(0); cout.tie(nullptr); if(fopen(file".inp", "r")){ freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); } input(); proc(); return 0; }

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

papricice.cpp: In function 'int main()':
papricice.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(file".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
papricice.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(file".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...