oj.uz

Submission #705797

# Submission time Handle Problem Language Result Execution time Memory
705797 2023-03-05T09:49:22 Z Abito Papričice (COCI20_papricice) C++14
50 / 110
 612 ms 604 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
typedef unsigned long long ull;
using namespace std;
const int N=2005;
int n,sz[N],d[N];
pair<int,int> e[N];
vector<int> adj[N];
bool vis[N];
void dfs(int node,int dd){
    vis[node]=true;
    d[node]=dd;
    sz[node]=1;
    for (auto u:adj[node]){
        if (vis[u]) continue;
        dfs(u,dd+1);
        sz[node]+=sz[u];
    }return;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n;
    for (int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
        e[i]={x,y};
    }
    int ans=INT_MAX;
    for (int i=1;i<n;i++){
        int x=e[i].F,y=e[i].S;
        for (int i=0;i<adj[x].size();i++){
            if (adj[x][i]==y){
                adj[x].erase(adj[x].begin()+i);
                break;
            }
        }
        for (int i=0;i<adj[y].size();i++){
            if (adj[y][i]==x){
                adj[y].erase(adj[y].begin()+i);
                break;
            }
        }
        for (int i=1;i<=n;i++) vis[i]=false;
        dfs(1,0);
        set<int> v,b;
        for (int i=1;i<=n;i++){
            if (vis[i]) v.ep(i);
            else b.ep(i);
        }
        int h=0;
        for (int i=1;i<=n;i++){
            if (vis[i]) continue;
            dfs(i,0);
            h=i;
            break;
        }
        int a[3];
        adj[x].pb(y);
        adj[y].pb(x);
        for (int j=i+1;j<n;j++){
            x=e[j].F,y=e[j].S;
            if (d[x]>d[y]) swap(x,y);
            if (v.count(x)){
                a[0]=sz[1]-sz[y];
                a[1]=sz[y];
                a[2]=sz[h];
            }
            else{
                a[0]=sz[h]-sz[y];
                a[1]=sz[y];
                a[2]=sz[1];
            }
            sort(a,a+3);
            ans=min(a[2]-a[0],ans);
        }
    }cout<<ans<<endl;
    return 0;
}

Compilation message

papricice.cpp: In function 'int32_t main()':
papricice.cpp:42:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int i=0;i<adj[x].size();i++){
      |                      ~^~~~~~~~~~~~~~
papricice.cpp:48:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int i=0;i<adj[y].size();i++){
      |                      ~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 6 ms 396 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 589 ms 576 KB Output is correct
7 Correct 612 ms 604 KB Output is correct
8 Correct 517 ms 596 KB Output is correct
9 Correct 552 ms 600 KB Output is correct
10 Correct 588 ms 604 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 6 ms 396 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 589 ms 576 KB Output is correct
7 Correct 612 ms 604 KB Output is correct
8 Correct 517 ms 596 KB Output is correct
9 Correct 552 ms 600 KB Output is correct
10 Correct 588 ms 604 KB Output is correct
11 Runtime error 1 ms 516 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -