Submission #439217

#	Time	Username	Problem	Language	Result	Execution time	Memory
439217		LptN21	Papričice (COCI20_papricice)	C++14	110 / 110	282 ms	21064 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define FF first
#define SS second
#define pb push_back
#define sz(x) (int)x.size()
//#define oo 2e18
#define eps 1e-9
#define PI acos(-1.0)
#define lb lower_bound
#define ub upper_bound
#define all(a) (a).begin(), (a).end()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<int, ii> i3;
const int N = 2e5+7, M=448;
const int MOD = 1e9+7;
const int oo=1e9+1;

int n, m, k, t;

vector<int> adj[N];
int vsz[N];
set<int> in, out;

vector<int> closest(const set<int> &s, int v) {
    vector<int> ans;
    set<int>::iterator it=s.ub(v);
    if(it!=s.end()) ans.pb(*it);
    if(it!=s.begin()) {--it; ans.pb(*it);}
    return ans;
}

int dfs(int u, int p=0) {
    vsz[u]=1;
    for(int v:adj[u]) if(v!=p) vsz[u]+=dfs(v, u);
    return vsz[u];
}
int diff(int a, int b, int c) {return max({a, b, c})-min({a, b, c});}
int dfs2(int u, int p=0) {
    int ans=n;
    for(int szv:closest(in, (n+vsz[u])/2))
        ans=min(ans, diff(vsz[u], szv-vsz[u], n-szv));
    for(int szv:closest(out, (n-vsz[u])/2))
        ans=min(ans, diff(vsz[u], szv, n-vsz[u]-szv));
    in.insert(vsz[u]);
    for(int v:adj[u]) if (v!=p) ans=min(ans, dfs2(v, u));
    in.erase(vsz[u]), out.insert(vsz[u]);
    return ans;
}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    //fastIO;
    scanf("%d", &n);
    int u, v;
    for(int i=1;i<n;i++) {
        scanf("%d%d", &u, &v);
        adj[u].pb(v), adj[v].pb(u);
    }
    dfs(1);
    printf("%d", dfs2(1));
    return 0;
}
/* stuff you should look for
    - int overflow, array bounds
    - special cases (n=1?)
    - do smth instead of do nothing and stay organized
    - WRITE STUFF DOWN
    - DONT JUST STICK ON ONE APPROACH
*/

Compilation message (stderr)

papricice.cpp: In function 'int main()':
papricice.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
papricice.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

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