제출 #316609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
316609		DanerZein	Papričice (COCI20_papricice)	C++14	15 / 110	1094 ms	504 KiB

papricice

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