Submission #1235239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235239		badge881	Spring cleaning (CEOI20_cleaning)	C++20	34 / 100	1095 ms	22088 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 2e5 + 5, inf = 2e9 + 7;
const ll INF = 1e18, mod = 1e9 + 7;

ll a[N], b[N], sz[N];
vector<int> g[N];
int ans = 0;
void go(int v, int p)
{
    sz[v] = 0;
    for (int to : g[v])
        if (to != p)
        {
            go(to, v);
            sz[v] += sz[to];
        }
    while (sz[v] > 2)
        sz[v] -= 2;
    if (sz[v] == 2 && v != 1)
        ans++;
    if (g[v].size() == 1)
        sz[v] = 1;
}
int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i < n; i++)
        scanf("%d%d", &a[i], &b[i]);
    for (int _ = 0; _ < q; _++)
    {
        int k;
        scanf("%d", &k);
        for (int i = 1; i <= n + k; i++)
            g[i].clear();
        for (int i = 1; i < n; i++)
        {
            g[a[i]].push_back(b[i]);
            g[b[i]].push_back(a[i]);
        }
        for (int i = 1; i <= k; i++)
        {
            int a;
            scanf("%d", &a);
            g[a].push_back(i + n);
            g[i + n].push_back(a);
        }
        ll res = 0;
        for (int i = 1; i <= n + k; i++)
            res += (g[i].size() == 1);
        if (res % 2)
        {
            printf("-1\n");
            continue;
        }
        ans = 0;
        go(1, 0);
        printf("%d\n", ans + n + k - 1);
    }
}

Compilation message (stderr)

cleaning.cpp: In function 'int main()':
cleaning.cpp:32:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   32 |         scanf("%d%d", &a[i], &b[i]);
      |                ~^     ~~~~~
      |                 |     |
      |                 int*  long long int*
      |                %lld
cleaning.cpp:32:19: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   32 |         scanf("%d%d", &a[i], &b[i]);
      |                  ~^          ~~~~~
      |                   |          |
      |                   int*       long long int*
      |                  %lld
cleaning.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
cleaning.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d%d", &a[i], &b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d", &k);
      |         ~~~~~^~~~~~~~~~
cleaning.cpp:47:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |             scanf("%d", &a);
      |             ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30