Submission #1270643

#TimeUsernameProblemLanguageResultExecution timeMemory
1270643goldencheemsSpring cleaning (CEOI20_cleaning)C++20
0 / 100
31 ms2120 KiB
/*DEP TRAI CO J SAI*/
/* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@%%##***************************+++++++++++++++++++++++++++++++++++++++++++++++***************************######%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
   Template header: dùng cho mọi code C++ theo yêu cầu.
*/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#define fi first
#define se second
#define pu emplace_back
#define ll long long

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, Q;
    if(!(cin >> n >> Q)) return 0;
    vector<int> deg(n+1, 0);
    for(int i=0;i<n-1;i++){
        int u,v; cin>>u>>v;
        deg[u]++; deg[v]++;
    }
    // For each query: read Di and then Di integers (attachment nodes)
    for(int qi=0; qi<Q; qi++){
        int Di; cin>>Di;
        vector<int> addList(Di);
        for(int i=0;i<Di;i++) cin>>addList[i];
        // compute degrees after additions
        bool ok = true;
        // we can update by counting freq
        unordered_map<int,int> freq;
        freq.reserve(Di*2+10);
        for(int x: addList) freq[x]++;
        for(auto &p: freq){
            int node = p.first;
            // Note: node in range 1..n
        }
        // check all vertices 1..n
        for(int v=1; v<=n; v++){
            int newdeg = deg[v] + (freq.count(v) ? freq[v] : 0);
            if(newdeg > 1 && (newdeg % 2 == 1)){
                ok = false; break;
            }
        }
        if(!ok) cout << -1 << '\n';
        else cout << ( (n-1) + Di ) << '\n';
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...