제출 #1125489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125489		duyhoanho	Cat in a tree (BOI17_catinatree)	C++20	0 / 100	8 ms	11328 KiB

catinatree

#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 10;
int n , d[N] , st[N] , ed[N] , f[N][30] , k;
vector<int> ad[N];

priority_queue<pii,vector<pii> , greater<pii>> q[N];
bool anc(int u,int v){
  return st[u] <= st[v] && ed[v] <= ed[u];
}

int lca(int u,int v){
  if(anc(u , v)) return u;
  if(anc(v , u)) return v;
  for(int i = 19; i >= 0; i--) if(!anc(f[u][i] , v)) u = f[u][i];
  return f[u][0];
}

int it;

void pre_dfs(int u,int p = 0){
  st[u] = ++it;
  for(int i = 1; i <= 19; i++) f[u][i] = f[f[u][i - 1]][i - 1];
  for(int v : ad[u]){
    if(v == p) continue;
    f[v][0] = u;
    d[v] = d[u] + 1;
    pre_dfs(v , u);
  }
  ed[u] = it;
}

int len(int u,int v){
  return d[u] + d[v] - 2 * d[lca(u , v)];
}

void dfs(int u,int  p = 0){
  q[u].push({d[u] , u});
  for(int v : ad[u]){
    if(v == p) continue;
    dfs(v , u);
    if(q[v].size() > q[u].size()) swap(q[u] , q[v]);
    while(q[v].size()){
      auto dinh = q[v].top(); q[v].pop();
      q[u].push(dinh);
    }
    while(q[u].size() > 1){
      auto [du , nu] = q[u].top(); q[u].pop();
      auto [dv , nv] = q[u].top(); q[u].pop();
      q[u].push({dv,nv});
      if(len(nu , nv) >= k) q[u].push({du,nu});
      break;
    }
  }
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #define task "task"
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    if(fopen("task.inp","r"))
    {
        freopen("task.inp","r",stdin);
        freopen("task.out","w",stdout);
    }
  cin >> n >> k;
  for(int i = 1; i < n; i++){
    int u,v;
    cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
  }
  f[1][0] = 1;
  pre_dfs(1);
  dfs(1);
  cout<<q[1].size()<<"\n";
  while(q[1].size()){
    auto dinh = q[1].top();q[1].pop();
    cout<<dinh.se<<" ";
  }


}

컴파일 시 표준 에러 (stderr) 메시지

catinatree.cpp: In function 'int32_t main()':
catinatree.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen("task.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen("task.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 40
• Subtask 3: 0 / 49