Submission #915415

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

papricice

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define int ll
#define ii pair<int,int>
#define F first
#define S second
#define vi vector<int>
#define vii vector<ii>
#define pb push_back
#define endl '\n'
#define dbg(x) cerr << #x << ": " << x << endl;
#define raya cerr << "------------------" << endl;

const int N = 2020;
vi adj[N];

signed main(){
    int n;
    cin >> n;
    vector<ii> edlist;
    for(int i=1; i<n; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        edlist.pb({u, v});
    }

    vi tam(n+1);

    auto findtam = [&](int x, int forb, auto&& findtam) -> int {
        tam[x] = 1;
        for(auto u : adj[x]){
            if(u == forb) continue;
            tam[x] += findtam(u, x, findtam);
        }
        return tam[x];
    };

    auto findmx = [&](int x, int forb, int orig, auto&& findmx, int otrotam, int &ans) -> void {
        for(auto u : adj[x]){
            if(u == forb) continue;
            // cut [x, u]
            // cerr << "cortando " << x << " y " << u << endl;
            int tamx = orig - tam[u];
            // dbg(tamx);
            // dbg(tam[u]);

            int tmpmn = min({otrotam, tamx, tam[u]});
            int tmpmx = max({otrotam, tamx, tam[u]});
            ans = min(ans, tmpmx - tmpmn);

            findmx(u, x, orig, findmx, otrotam, ans);
        }
    };  

    int ans = n+1;
    for(auto cur : edlist){
        int u = cur.F, v = cur.S;
        int tam1 = findtam(v, u, findtam);
        int tam2 = n - tam1;

        // cerr << "cortando [" << u << ", " << v << "]" << endl;

        // cut on tam1
        if(tam1 > 1){
            findmx(v, u, tam1, findmx, tam2, ans);
        }

        // cut on tam2
        if(tam2 > 1){
            findtam(u, v, findtam);
            findmx(u, v, tam2, findmx, tam1, ans);
        }
        

    }

    cout << ans;

}

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