# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
883718 | 2023-12-05T19:39:12 Z | HossamHero7 | Papričice (COCI20_papricice) | C++14 | 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
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 | - |
# | 결과 | 실행 시간 | 메모리 | 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 | - |