Submission #705797

#	Time	Username	Problem	Language	Result	Execution time	Memory
705797		Abito	Papričice (COCI20_papricice)	C++14	50 / 110	612 ms	604 KiB

papricice

#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 (stderr)

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 / 15
• Subtask 2: 35 / 35
• Subtask 3: 0 / 60