oj.uz

Submission #439217

# Submission time Handle Problem Language Result Execution time Memory
439217 2021-06-29T11:51:39 Z LptN21 Papričice (COCI20_papricice) C++14
110 / 110
 282 ms 21064 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4984 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 4944 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4984 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 4944 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 5 ms 5008 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 5 ms 5068 KB Output is correct
10 Correct 5 ms 5000 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4984 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 4944 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 5 ms 5008 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 5 ms 5068 KB Output is correct
10 Correct 5 ms 5000 KB Output is correct
11 Correct 282 ms 12516 KB Output is correct
12 Correct 275 ms 12356 KB Output is correct
13 Correct 221 ms 12892 KB Output is correct
14 Correct 270 ms 12656 KB Output is correct
15 Correct 276 ms 12356 KB Output is correct
16 Correct 168 ms 12992 KB Output is correct
17 Correct 258 ms 12380 KB Output is correct
18 Correct 276 ms 21064 KB Output is correct
19 Correct 232 ms 12516 KB Output is correct
20 Correct 248 ms 12356 KB Output is correct