Submission #57052646

Source Code Expand

/***************************************************
* Author  : Anav Prasad
* Handle  : vrangr
* Created : Sat Aug 24 17:42:13 IST 2024
****************************************************/
#include <bits/stdc++.h>

#define debug(...) (void)42
#ifdef LOCAL
    #undef debug
    #include <algo/debug.hpp>
    const bool DEBUG = true;
#else
    [[maybe_unused]] const bool DEBUG = false;
#endif

using namespace std;

typedef unsigned int uint;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef __int128_t i128;
#define endl "\n"
#define fastIO ios_base::sync_with_stdio(false),cin.tie(0)
#define TEST int T;cin>>T;while(T--)solve();
#define TEST1 solve();
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(v) ((int)(v).size())
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, forsn, debug, forn)(__VA_ARGS__)
#define forn(i, n) for (__typeof(n) i = 0; i < n; i++)
#define forsn(i, st, end, d) for(__typeof(end) i = st; (d>0?i<=end:i>=end); i+=((__typeof(end))d))
#define yes "YES\n"
#define no "NO\n"
template<typename type>inline void print_vec(const vector<type> &v){rep(i,sz(v))cout<<v[i]<<" \n"[i==sz(v)-1];}
void solve();

// IMPORT SNIPPETS HERE

// END OF SNIPPETS

int main() {
	fastIO;
	TEST1;
#ifdef LOCAL
    cout << "\nTime elapsed: " << (double)clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}

void solve() {
    int n, k; cin >> n >> k;
    vector<vector<int>> g(n);
    rep(i,n-1) {
        int u, v; cin >> u >> v;
        g[--u].push_back(--v);
        g[v].push_back(u);
    }
    vector<bool> chs(n,false);
    int root = -1;
    rep(i,k) {
        int u; cin >> u;--u;
        chs[u] = true;
        root = u;
    }
    int sol = 0;
    auto dfs = [&](auto &&self, int u, int p) -> bool {
        bool seen = chs[u];
        for (int &v : g[u]) {
            if (v == p) continue;
            bool vs = self(self,v,u);
            seen |= vs;
        }
        if (!seen) sol++;
        return seen;
    };
    debug(root);
    dfs(dfs,root,-1);
    cout << n-sol << endl;
}

Submission Info

Submission Time
Task D - Minimum Steiner Tree
User vrangr
Language C++ 20 (gcc 12.2)
Score 425
Code Size 2204 Byte
Status AC
Exec Time 57 ms
Memory 18856 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 3
AC × 37
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All min.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
min.txt AC 1 ms 3508 KiB
random_01.txt AC 50 ms 14084 KiB
random_02.txt AC 56 ms 14212 KiB
random_03.txt AC 57 ms 18856 KiB
random_04.txt AC 57 ms 18684 KiB
random_05.txt AC 40 ms 14836 KiB
random_06.txt AC 39 ms 14840 KiB
random_07.txt AC 45 ms 15032 KiB
random_08.txt AC 45 ms 14936 KiB
random_09.txt AC 56 ms 14164 KiB
random_10.txt AC 56 ms 14128 KiB
random_11.txt AC 54 ms 14128 KiB
random_12.txt AC 54 ms 14124 KiB
random_13.txt AC 57 ms 14096 KiB
random_14.txt AC 3 ms 3856 KiB
random_15.txt AC 3 ms 3780 KiB
random_16.txt AC 18 ms 7176 KiB
random_17.txt AC 51 ms 13316 KiB
random_18.txt AC 19 ms 7496 KiB
random_19.txt AC 45 ms 12952 KiB
random_20.txt AC 41 ms 12264 KiB
random_21.txt AC 35 ms 11012 KiB
random_22.txt AC 41 ms 12240 KiB
random_23.txt AC 30 ms 10184 KiB
random_24.txt AC 52 ms 14112 KiB
random_25.txt AC 51 ms 14112 KiB
random_26.txt AC 51 ms 14128 KiB
random_27.txt AC 55 ms 14132 KiB
random_28.txt AC 50 ms 14112 KiB
random_29.txt AC 10 ms 5236 KiB
random_30.txt AC 5 ms 4016 KiB
random_31.txt AC 15 ms 6724 KiB
random_32.txt AC 9 ms 5240 KiB
random_33.txt AC 46 ms 13068 KiB
sample_01.txt AC 1 ms 3364 KiB
sample_02.txt AC 1 ms 3492 KiB
sample_03.txt AC 1 ms 3496 KiB