# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
924477 | 2024-02-09T05:15:37 Z | Sir_Ahmed_Imran | Railway (BOI17_railway) | C++17 | 84 ms | 27332 KB |
///~~~LOTA~~~/// #include <bits/stdc++.h> using namespace std; #define ll long long #define append push_back #define add insert #define nl "\n" #define ff first #define ss second #define pii pair<int,int> #define all(x) (x).begin(),(x).end() #define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL) #define N 100001 int k; int s[N]; vector<int> ans; vector<pii> a[N]; vector<int> c[N]; map<int,int> *x[N]; void dfs(int v,int u){ int z=0; for(auto& i:a[v]){ if(i.ss==u) continue; dfs(i.ff,i.ss); if((*x[i.ff]).size()>(*x[z]).size()) z=i.ff; } if(z>0) x[v]=x[z]; else x[v]=new map<int,int>; for(auto &i:a[v]){ if(i.ss==u || i.ff==z) continue; for(auto& j:*x[i.ff]){ (*x[v])[j.ff]+=j.ss; if(s[j.ff]==(*x[v])[j.ff]) (*x[v]).erase(j.ff); } (*x[i.ff]).clear(); } for(auto& i:c[v]){ (*x[v])[i]++; if(s[i]==(*x[v])[i]) (*x[v]).erase(i); } if((*x[v]).size()>=k) ans.append(u); } void solve(){ int n,m,p,q; cin>>n>>m>>k; for(int i=1;i<n;i++){ cin>>p>>q; a[p].append({q,i}); a[q].append({p,i}); } for(int i=0;i<m;i++){ cin>>s[i]; for(int j=0;j<s[i];j++){ cin>>q; c[q].append(i); } } x[0]=new map<int,int>; dfs(1,0); cout<<ans.size()<<nl; for(auto& i:ans) cout<<i<<' '; } int main(){ L0TA; solve(); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 5720 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 5720 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 84 ms | 27332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 72 ms | 23176 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 72 ms | 23176 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 5720 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |