?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
74663766 |
Practice: Heisenberg1744 |
1328E - 12 | C++14 (GCC 6-32) | Runtime error on test 100 | 1481 ms | 53908 KB | 2020-03-28 20:40:34 | 2020-03-28 20:40:34 |
#include<bits/stdc++.h> #define ll long long #define mp(a,b) make_pair(a,b) #define pb(a) push_back(a) #define f(i,n) for(ll i=0;i<n;i++) using namespace std; void dfs(vector<int>*parent,int level[],vector<int>*v,int j) { for(int i=0;i<v[j].size();i++) { if(level[v[j][i]]==0) { level[v[j][i]]=level[j]+1; parent[v[j][i]][0]=j; dfs(parent,level,v,v[j][i]); } } } void parent_arr(vector<int>*parent,int n) { for(int i=1;i<=floor(log2(n));i++) { for(int j=1;j<n;j++) { if(parent[j][i-1]!=0) { parent[j][i]=parent[parent[j][i-1]][i-1]; } } } } int lca(int a,int b,vector<int>*c,int level1,int level2) { if(level1==level2) { if(a!=b) return 1; else return 0; } else { a=c[a][log2(level1-level2)]; int d=log2(level1-level2); level1-=(ll)pow(2,d); lca(a,b,c,level1,level2); } } int main() { int n,k; cin>>n>>k; vector< int >v[n+1],v1[n+1]; vector<int>parent[n+1];int level[n+1]={0}; for(int i=1;i<=n;i++) { for(int j=0;j<=log2(n)+1;j++) { parent[i].push_back(0); } } for(int i=1;i<n;i++) { int a,b; cin>>a>>b; v[a].pb(b); v[b].pb(a); } level[1]=1; dfs(parent,level,v,1); parent_arr(parent,n); while(k--) { int a,check=0; vector< pair<int,int> >v2; cin>>a; for(int i=0;i<a;i++){ int b; cin>>b; if(b!=1) v2.push_back(make_pair(level[parent[b][0]],parent[b][0])); } sort(v2.begin(),v2.end()); if(v2.size()>1) { for(int i=v2.size()-1;i>0;i--) { int val1=v2[i].second,val2=v2[i-1].second,l1=v2[i].first,l2=v2[i-1].first; if(lca(val1,val2,parent,l1,l2)) { cout<<"NO\n"; goto ij; } } } cout<<"YES\n"; ij:; } }
?
?
?
?