제출 #1026227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1026227		AdamGS	Meetings 2 (JOI21_meetings2)	C++17	4 / 100	4085 ms	5212 KiB

meetings2

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
vector<int>V[LIM];
int ans[2*LIM], ile[LIM], akt;
void DFS(int x, int o) {
  for(auto i : V[x]) if(i!=o) {
    DFS(i, x);
    ile[x]+=ile[i];
  }
}
void DFS2(int x, int o) {
  if(2*ile[x]==ile[0]) ++akt;
  for(auto i : V[x]) if(i!=o) DFS2(i, x);
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  rep(i, n-1) {
    int a, b;
    cin >> a >> b; --a; --b;
    V[a].pb(b);
    V[b].pb(a);
  }
  rep(i, 1<<n) {
    rep(j, n) if(i&(1<<j)) ile[j]=1; else ile[j]=0;
    DFS(0, 0);
    akt=1;
    DFS2(0, 0);
    ans[ile[0]]=max(ans[ile[0]], akt);
  }
  rep(i, n) cout << ans[i+1] << '\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80