Submission #695260

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
695260	2023-02-04T20:42:43 Z	HossamHero7	Railway (BOI17_railway)	C++14	7 / 100	191 ms	17512 KB

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};
        // assert(adj[a].size()<=2 && adj[b].size()<=2);
    }
    int st = 0;
    int en = 0;
    for(int i=1;i<=n;i++){
        if(adj[i].size() == 1 && st == 0) st = i;
        if(adj[i].size() == 1) en = i;
    }
    //if(en == 0) en = st;
    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][1]].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

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

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	191 ms	17300 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	172 ms	17004 KB	Output is correct
4	Correct	150 ms	16432 KB	Output is correct
5	Correct	174 ms	17452 KB	Output is correct
6	Correct	161 ms	17512 KB	Output is correct