Submission #914798

#	Time	Username	Problem	Language	Result	Execution time	Memory
914798		vjudge1	Papričice (COCI20_papricice)	C++17	15 / 110	1022 ms	604 KiB

papricice

#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(2005, vi());
vii edges;
vector<bool> vis(2005);

int dfs(int node, int not1, int not2) {
    if (vis[node])
        return 0;
    int size = 1;
    vis[node] = true;
    for (auto next : g[node]) {
        if ((next == edges[not1].f && node == edges[not1].s) or
            (next == edges[not1].s && node == edges[not1].f) or
            (next == edges[not2].f && node == edges[not2].s) or
            (next == edges[not2].s && node == edges[not2].f)) {
            continue;
        } else {
            size += dfs(next, not1, not2);
        }
    }
    return size;
}

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;
        edges.pb(mp(a, b));
        g[a].pb(b);
        g[b].pb(a);
    }
    int comp, res, final_res = INF;
    vi sizes;
    fr(i, m) {
        for (int j = i + 1; j < m; j++) {
            sizes.clear();
            vis.assign(2005, false);
            fr1(k, n) {
                comp = dfs(k, i, j);
                if (comp != 0)
                    sizes.pb(comp);
            }
            res = max(abs(sizes[0] - sizes[1]),
                      max(abs(sizes[0] - sizes[2]), abs(sizes[1] - sizes[2])));
            final_res = min(res, final_res);
        }
    }
    cout << final_res << endl;
    return 0;
}

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