Submission #982144

#	Time	Username	Problem	Language	Result	Execution time	Memory
982144		aaaaaarroz	Village (BOI20_village)	C++17	50 / 100	87 ms	14676 KiB

Village

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>ans;
vector<vector<int>>graph;
int respuesta=0;
void dfs(int nodo, int p){
  for(int u:graph[nodo]){
    if(u!=p){
      dfs(u,nodo);
    }
  }
  if(ans[nodo]==nodo){
    respuesta+=2;
    if(p){
      swap(ans[nodo],ans[p]);
    }
    else{
      swap(ans[nodo],ans[graph[nodo][0]]);
    }
  }
}
int main() {
  ll n;
  cin>>n;
  graph.resize(n+1,vector<int>());
  for(int i=0;i<n-1;i++){
    int a, b;
    cin>>a>>b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  ans.resize(n+1);
  for(int i=1;i<=n;i++){
    ans[i]=i;
  }
  dfs(1,0);
  cout<<respuesta<<" "<<respuesta<<"\n";
  for(int i=1;i<=n;i++){
    cout<<ans[i]<<" ";
  }
  cout<<"\n";
  for(int i=1;i<=n;i++){
    cout<<ans[i]<<" ";
  }
  cout<<"\n";
}

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50