Submission #61089838

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<vector<int>> adj(n);
  vector<int> deg(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
    deg[u]++, deg[v]++;
  }
  int ans = 0;
  for (int u = 0; u < n; u++) {
    vector<int> a;
    for (int v : adj[u]) {
      if (deg[v] > 1) a.push_back(deg[v] - 1);
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < (int)a.size(); i++) {
      int x = (int)a.size() - i;
      int y = a[i];
      int res = 1 + x + x * y;
      ans = max(ans, res);
    }
  }
  cout << n - ans << '\n';

  return 0;
}

Submission Info

Submission Time
Task E - Snowflake Tree
User xindubawukong
Language C++ 20 (gcc 12.2)
Score 450
Code Size 837 Byte
Status AC
Exec Time 170 ms
Memory 22768 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 3
AC × 29
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 02_handmade_01.txt, 02_handmade_02.txt, 02_handmade_03.txt, 02_handmade_04.txt, 02_handmade_05.txt, 02_handmade_06.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 1 ms 3520 KiB
00_sample_02.txt AC 1 ms 3516 KiB
00_sample_03.txt AC 1 ms 3452 KiB
01_random_01.txt AC 159 ms 21048 KiB
01_random_02.txt AC 83 ms 13424 KiB
01_random_03.txt AC 170 ms 21028 KiB
01_random_04.txt AC 47 ms 10476 KiB
01_random_05.txt AC 166 ms 20972 KiB
01_random_06.txt AC 10 ms 5236 KiB
01_random_07.txt AC 160 ms 21012 KiB
01_random_08.txt AC 67 ms 12304 KiB
01_random_09.txt AC 166 ms 20936 KiB
01_random_10.txt AC 134 ms 18172 KiB
01_random_11.txt AC 130 ms 21696 KiB
01_random_12.txt AC 116 ms 18376 KiB
01_random_13.txt AC 134 ms 21916 KiB
01_random_14.txt AC 121 ms 17916 KiB
01_random_15.txt AC 155 ms 21004 KiB
01_random_16.txt AC 88 ms 18276 KiB
01_random_17.txt AC 118 ms 21824 KiB
01_random_18.txt AC 121 ms 19844 KiB
01_random_19.txt AC 159 ms 21212 KiB
01_random_20.txt AC 97 ms 17128 KiB
02_handmade_01.txt AC 101 ms 21956 KiB
02_handmade_02.txt AC 121 ms 22768 KiB
02_handmade_03.txt AC 110 ms 21652 KiB
02_handmade_04.txt AC 105 ms 21904 KiB
02_handmade_05.txt AC 144 ms 20748 KiB
02_handmade_06.txt AC 138 ms 20752 KiB