oj.uz

답안 #1011882

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1011882 2024-07-01T10:30:40 Z Dedibeat Papričice (COCI20_papricice) C++17
15 / 110
 9 ms 1116 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e3 + 5;
vector<int> adj[N + 5];
vector<int> child[N+5];
int sz[N + 5];
void dfs(int v, int last){
     sz[v] = 1;
     child[v].push_back(v);
     for(auto u : adj[v]){
            if(u != last) dfs(u , v);
     }
     for(auto u : adj[v]){
            if(u == last) continue;
            sz[v] += sz[u];
            for(auto it : child[u]){
                   child[v].push_back(it);
            }
     }
 }

int main(){
       int n;
       cin >> n;
       for(int i = 1; i<n; i++){
           int x, y;
           cin >> x >> y;
           adj[x].push_back(y);
           adj[y].push_back(x);
       }
       dfs(1, 1);
       int ans = n;
       for(int i = 2; i<=n; i++){
           // cout << sz[i] << endl;
                bool c[n+5];
                for(int j = 0; j<=n; j++){
                     c[j] = false;
                }
                for(auto u : child[i])  c[u] = true;
                int A, B, C;
                for(int j = 2; j<=n; j++){
                      if(c[j]) C = sz[j], B = sz[i] - sz[j], A = n - sz[i];
                      else C = sz[j], B = sz[i], A = n - sz[i] - sz[j];
                      ans = min(ans, max(abs(A - B), max(abs(A - C), abs(B - C))));
                    //  cout << i << " " << j << " " << A << " " << B << " " << C << endl;
                }
       }
       cout << ans << endl;




}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 9 ms 600 KB Output is correct
7 Incorrect 9 ms 1116 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 9 ms 600 KB Output is correct
7 Incorrect 9 ms 1116 KB Output isn't correct
8 Halted 0 ms 0 KB -