oj.uz

Submission #883718

# Submission time Handle Problem Language Result Execution time Memory
883718 2023-12-05T19:39:12 Z HossamHero7 Papričice (COCI20_papricice) C++14
15 / 110
 1000 ms 5212 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4952 KB Output is correct
2 Correct 42 ms 4952 KB Output is correct
3 Correct 37 ms 4956 KB Output is correct
4 Correct 37 ms 4952 KB Output is correct
5 Correct 41 ms 4956 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4952 KB Output is correct
2 Correct 42 ms 4952 KB Output is correct
3 Correct 37 ms 4956 KB Output is correct
4 Correct 37 ms 4952 KB Output is correct
5 Correct 41 ms 4956 KB Output is correct
6 Execution timed out 1070 ms 5212 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4952 KB Output is correct
2 Correct 42 ms 4952 KB Output is correct
3 Correct 37 ms 4956 KB Output is correct
4 Correct 37 ms 4952 KB Output is correct
5 Correct 41 ms 4956 KB Output is correct
6 Execution timed out 1070 ms 5212 KB Time limit exceeded
7 Halted 0 ms 0 KB -