oj.uz

Submission #914917

# Submission time Handle Problem Language Result Execution time Memory
914917 2024-01-22T21:33:30 Z diegoangulo5 Papričice (COCI20_papricice) C++14
50 / 110
 1000 ms 16384 KB 
#include <bits/stdc++.h>

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag,
// __gnu_pbds::tree_order_statistics_node_update > ordered_set;

// #include "debugging.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define f first
#define s second
#define endl '\n'
#define fr(i, x) for (int i = 0; i < x; i++)
#define fr1(i, x) for (int i = 1; i <= x; i++)
#define FOR(i, x, y) for (ll i = x; i < y; i++)
#define lcm(a, b) (a * b) / __gcd(a, b)
#define sqr(x) ((x) * (x))
#define cube(x) ((x) * (x) * (x))
#define dbg(v) cerr << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
#define show(v) cerr << v << " ";
#define INT(n) \
    int n;     \
    cin >> n;
const int INF = 1e9;
const double PI = acos(-1);
const int MOD = 1e9 + 7;

vvi g(200005, vi());
vector<int> sizes(200005, -1);

vi timein(200005), timeout(200005);

int dfs(int node, int &time) {
    if (sizes[node] != -1)
        return 0;
    timein[node] = time;
    time++;
    sizes[node] = 1;
    for (auto next : g[node]) {
        sizes[node] += dfs(next, time);
    }
    timeout[node] = time;
    time++;
    return sizes[node];
}

// is node2 component inside node1 component
bool is_in(int node1, int node2) {
    return timein[node1] < timein[node2] && timeout[node2] < timeout[node1];
}

int diff(int a, int b, int c) {
    return max(abs(a - b), max(abs(b - c), abs(a - c)));
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, a, b;
    cin >> n;
    int m = n - 1;
    fr(i, m) {
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    int time = 0;
    dfs(1, time);
    int comp1, comp2, comp3;
    int res = 0, final_res = INF;
    for (int i = 2; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (is_in(i, j)) {
                comp1 = sizes[j];
                comp2 = sizes[i] - comp1;
                comp3 = sizes[1] - sizes[i];
            } else if (is_in(j, i)) {
                comp1 = sizes[i];
                comp2 = sizes[j] - comp1;
                comp3 = sizes[1] - sizes[j];
            } else {
                comp1 = sizes[1] - sizes[i] - sizes[j];
                comp2 = sizes[j];
                comp3 = sizes[i];
            }
            res = diff(comp1, comp2, comp3);
            final_res = min(final_res, res);
        }
    }
    cout << final_res << endl;
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 12 ms 7516 KB Output is correct
7 Correct 13 ms 7360 KB Output is correct
8 Correct 12 ms 7516 KB Output is correct
9 Correct 10 ms 7516 KB Output is correct
10 Correct 12 ms 7516 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 12 ms 7516 KB Output is correct
7 Correct 13 ms 7360 KB Output is correct
8 Correct 12 ms 7516 KB Output is correct
9 Correct 10 ms 7516 KB Output is correct
10 Correct 12 ms 7516 KB Output is correct
11 Execution timed out 1051 ms 16384 KB Time limit exceeded
12 Halted 0 ms 0 KB -