oj.uz

Submission #316609

# Submission time Handle Problem Language Result Execution time Memory
316609 2020-10-26T22:53:52 Z DanerZein Papričice (COCI20_papricice) C++14
15 / 110
 1000 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX=1000000000;
typedef pair<int,int> ii;
typedef vector<ii> vi;
vector<vi> G;
int m[2010],vis[2010];
int dfs(int u){
  vis[u]=1;
  int ans=0;
  for(auto &v:G[u]){
    if(!vis[v.first] && m[v.second]){
      ans+=dfs(v.first)+1;
    }
  }
  return ans;
}
int main(){
  int n;
  cin>>n;
  G.resize(n+1);
  for(int i=0;i<n-1;i++){
    int a,b;
    cin>>a>>b;
    a--; b--;
    m[i]=1;
    G[a].push_back(ii(b,i));
    G[b].push_back(ii(a,i));
  }
  int mi=MAX;
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n-1;j++){
      m[i]=0;
      m[j]=0;
      memset(vis,0,sizeof vis);
      int pa,pe;
      pa=-1;
      pe=MAX;
      for(int k=0;k<n;k++){
	if(!vis[k]){
	  int aux=dfs(k)+1;
	  pa=max(aux,pa);
	  pe=min(aux,pe);
	}
      }
      m[i]=1;
      m[j]=1;
      mi=min(mi,pa-pe);
    }
  }
  cout<<mi<<endl;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 384 KB Output is correct
2 Correct 46 ms 504 KB Output is correct
3 Correct 46 ms 384 KB Output is correct
4 Correct 48 ms 384 KB Output is correct
5 Correct 45 ms 384 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 384 KB Output is correct
2 Correct 46 ms 504 KB Output is correct
3 Correct 46 ms 384 KB Output is correct
4 Correct 48 ms 384 KB Output is correct
5 Correct 45 ms 384 KB Output is correct
6 Execution timed out 1094 ms 384 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 384 KB Output is correct
2 Correct 46 ms 504 KB Output is correct
3 Correct 46 ms 384 KB Output is correct
4 Correct 48 ms 384 KB Output is correct
5 Correct 45 ms 384 KB Output is correct
6 Execution timed out 1094 ms 384 KB Time limit exceeded
7 Halted 0 ms 0 KB -