제출 #1004284

#제출 시각아이디문제언어결과실행 시간메모리
1004284ayankarimovaRailway (BOI17_railway)C++14
8 / 100
1094 ms34132 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long const ll sz=1e5+5; ll p[sz], used[sz]; vector<ll>g[sz]; set<ll>s; map<pair<ll, ll> , ll>mp; map<pair<ll, ll>, ll>m1; /* {} [] */ void dfs(ll u) { used[u]=1; //cout<<u<<' '; for(auto v:g[u]){ if(!used[v]){ p[v]=u; dfs(v); } } } int main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); ll n, m, k; cin>>n>>m>>k; for(int i=1; i<n; i++){ ll a, b; cin>>a>>b; g[a].push_back(b); g[b].push_back(a); m1[{a, b}]=i; m1[{b, a}]=i; } for(int i=1; i<=m; i++){ ll x; cin>>x; ll k[x+1]; for(int j=1; j<=x; j++){ cin>>k[j]; } set<pair<ll, ll>>cur; for(int j=2; j<=x; j++){ dfs(k[j-1]); ll x=k[j-1], y=k[j]; while(p[y]!=x){ ll a=y, b=p[y]; ll c=a, d=b; if(c>d) swap(c, d); cur.insert({c, d}); y=b; } ll a=y, b=p[y]; ll c=a, d=b; if(c>d) swap(c, d); cur.insert({c, d}); for(int t=0; t<=n; t++){ p[t]=0; used[t]=0; } } for(auto i:cur){ mp[{i.first, i.second}]++; } } for(auto i:mp){ if(i.second>=k){ s.insert(m1[{i.first.first, i.first.second}]); } } cout<<s.size()<<endl; for(auto i:s) cout<<i<<' '; } /* {} [] */
#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...