oj.uz

Submission #915415

# Submission time Handle Problem Language Result Execution time Memory
915415 2024-01-23T20:16:00 Z vjudge1 Papričice (COCI20_papricice) C++17
50 / 110
 123 ms 604 KB 
#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.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 108 ms 604 KB Output is correct
7 Correct 123 ms 600 KB Output is correct
8 Correct 59 ms 604 KB Output is correct
9 Correct 83 ms 604 KB Output is correct
10 Correct 118 ms 604 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 108 ms 604 KB Output is correct
7 Correct 123 ms 600 KB Output is correct
8 Correct 59 ms 604 KB Output is correct
9 Correct 83 ms 604 KB Output is correct
10 Correct 118 ms 604 KB Output is correct
11 Runtime error 1 ms 600 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -