Submission #883718

#	Time	Username	Problem	Language	Result	Execution time	Memory
883718		HossamHero7	Papričice (COCI20_papricice)	C++14	15 / 110	1070 ms	5212 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 2e5 + 5;
int n;
vector<pair<int,int>> adj[N];
vector<bool> can;
vector<bool> vis;
int cnt = 0;
void dfs(int node){
    vis[node] = 1;
    cnt ++;
    for(auto [e,ch] : adj[node]){
        if(can[e] && !vis[ch]) dfs(ch);
    }
}
int ans = 1e9;
void calc(){
    for(int i=1;i<=n;i++) vis[i] = 0;
    vector<int> comps;
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        cnt = 0;
        dfs(i);
        comps.push_back(cnt);
    }
    sort(comps.begin(),comps.end());
    ans = min(ans , comps.back() - comps[0]);
}
void solve(){
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back({i,b});
        adj[b].push_back({i,a});
    }
    can.resize(n-1,1);
    vis.resize(n+1);
    for(int i=0;i<n-1;i++){
        can[i] = 0;
        for(int j=i+1;j<n-1;j++){
            can[j] = 0;
            calc();
            can[j] = 1;
        }
        can[i] = 1;
    }
    cout<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

papricice.cpp: In function 'void dfs(int)':
papricice.cpp:14:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for(auto [e,ch] : adj[node]){
      |              ^

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