Submission #695254

#	Time	Username	Problem	Language	Result	Execution time	Memory
695254		HossamHero7	Railway (BOI17_railway)	C++14	0 / 100	1092 ms	167860 KiB

railway

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define endl '\n'
void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<pair<int,int>> edges(n-1);
    vector<vector<int>> adj(n+1);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(i);
        adj[b].push_back(i);
        edges[i] = {a,b};
    }
    int st = 0;
    int en = 0;
    for(int i=1;i<=n;i++){
        if(adj[i].size() == 1 && st == 0) st = i;
        else if(adj[i].size() == 1) en = i;
    }
    map<int,int> nodes;
    int node = st;
    int cnt = 1;
    map<int,int> mpEdge;
    while(1){
        nodes[node] = cnt;
        cnt ++;
        if(adj[node].size() == 1 && node != st) break;
        if(!nodes[edges[adj[node][0]].first]){
            mpEdge[cnt-1] = adj[node][0];
         //   cout<<adj[node][0]<<endl;
            node = edges[adj[node][0]].first;
        }
        else if(!nodes[edges[adj[node][0]].second]){
            mpEdge[cnt-1] = adj[node][0];
       //     cout<<adj[node][0]<<endl;
            node = edges[adj[node][0]].second;
          //  cout<<adj[node][0]<<endl;
        }
        else if(!nodes[edges[adj[node][1]].first]){
            mpEdge[cnt-1] = adj[node][1];
           // cout<<adj[node][1]<<endl;
            node = edges[adj[node][1]].first;
           // cout<<adj[node][1]<<endl;
        }
        else if(!nodes[edges[adj[node][1]].second]){
            mpEdge[cnt-1] = adj[node][1];
           // cout<<adj[node][1]<<endl;
            node = edges[adj[node][0]].second;
           // cout<<adj[node][1]<<endl;
        }
        else break;
    }/*
    for(int i=1;i<=n;i++){
        cout<<i<<": "<<nodes[i]<<endl;
    }
    cout<<endl;
    for(int i=0;i<n-1;i++){
        cout<<i<<": "<<mpEdge[i]<<endl;
    }*/

    vector<int> partial(n+1);
    for(int i=0;i<m;i++){
        int sz;
        cin>>sz;
        int mn = 1e9;
        int mx = 0;
        for(int j=0;j<sz;j++){
            int x;cin>>x;
            mn = min(mn,nodes[x]);
            mx = max(mx,nodes[x]);
        }
        partial[mn] ++;
        partial[mx] --;
    }
    for(int i=1;i<=n;i++) partial[i] += partial[i-1];
    vector<int> ans;
    for(int i=1;i<=n;i++){
        if(partial[i] >= k){
            ans.push_back(mpEdge[i]+1);
        }
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<endl;
    for(auto i : ans) cout<<i<<' ';
    cout<<endl;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void solve()':
railway.cpp:19:9: warning: variable 'en' set but not used [-Wunused-but-set-variable]
   19 |     int en = 0;
      |         ^~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25