oj.uz

Submission #338692

# Submission time Handle Problem Language Result Execution time Memory
338692 2020-12-23T16:53:10 Z souvenir_vayne Papričice (COCI20_papricice) C++14
110 / 110
 345 ms 21632 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <chrono>
#define pb push_back
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
#define ll long long
#define f first
#define fin cin
#define fout cout
#define s second
#define FAST cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)
#define debug(x) cout << "DEBUG " << x << endl
#define debug2(x, y) cout << "DEBUG " << x << " " << y << endl
#define debug3(x, y, z) cout << "DEBUG " << x << " " << y << " " << z<< endl
#define debug4(x, y, z, o) cout << "DEBUG " << x << " " << y << " " << z<< " " << o << endl
#define all(x) x.begin(), x.end()
#define left vadia
#define lb lower_bound
#define right puta
using namespace std;
using namespace __gnu_pbds;
void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0);
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str( ),"w",stdout);
}
typedef pair<ll, ll> pii;
typedef vector<vector<char>> mat;
typedef pair<int, string> pis;
const ll mod = 1e9+7;
typedef vector<int> vi;
typedef pair<int, pair<int, int>> piii;

const int MAXN = 2e5 + 5;

int sz[MAXN], n, ans = INT_MAX;
vector<int> g[MAXN];

void get(int u, int p) {
    sz[u] = 1;
    for(int &i : g[u])
        if(i != p) {
            get(i, u);
            sz[u] += sz[i];
        }
}

int calc(int x, int y) {
    int a1 = x, a2 = y - x, a3 = n - y;
    return max({abs(a1 - a2), abs(a1 - a3), abs(a2 - a3)});
}

int calc2(int x, int y) {
    int a1 = x, a2 = y, a3 = n - x - y;
    return max({abs(a1 - a2), abs(a1 - a3), abs(a2 - a3)});
}

set<int> a, b;

void dfs(int u, int p) {

    if(u != 1) {
        auto it = a.upper_bound((n + sz[u])/2);
        if(it != a.end())
            ans = min(ans, calc(sz[u], *it));
        if(it != a.begin()) {
            it--;
            ans = min(ans, calc(sz[u], *it));
        }
        auto it2 = b.upper_bound((n - sz[u])/2);
        if(it2 != b.end())
            ans = min(ans, calc2(sz[u], *it2));
        if(it2 != b.begin()) {
            it2--;
            ans = min(ans, calc2(sz[u], *it2));
        }
    }

    a.insert(sz[u]);
    for(int &i : g[u])
        if(i != p)
            dfs(i, u);
    a.erase(sz[u]);
    b.insert(sz[u]);
}

int32_t main() {

    cin >> n;

    for(int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }

    get(1, 1);
    dfs(1, 1);

    cout << ans << endl;


}

Compilation message

papricice.cpp: In function 'void setIO(std::string)':
papricice.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   27 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
papricice.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   28 |   freopen((s+".out").c_str( ),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 4 ms 4972 KB Output is correct
6 Correct 6 ms 5100 KB Output is correct
7 Correct 6 ms 5100 KB Output is correct
8 Correct 5 ms 5100 KB Output is correct
9 Correct 5 ms 5100 KB Output is correct
10 Correct 6 ms 5100 KB Output is correct
11 Correct 317 ms 16492 KB Output is correct
12 Correct 345 ms 16492 KB Output is correct
13 Correct 282 ms 17132 KB Output is correct
14 Correct 293 ms 16748 KB Output is correct
15 Correct 322 ms 16492 KB Output is correct
16 Correct 217 ms 16224 KB Output is correct
17 Correct 330 ms 16620 KB Output is correct
18 Correct 312 ms 21632 KB Output is correct
19 Correct 292 ms 16876 KB Output is correct
20 Correct 321 ms 16620 KB Output is correct