Submission #244668

#	Time	Username	Problem	Language	Result	Execution time	Memory
244668		kimbj0709	Railway (BOI17_railway)	C++14	23 / 100	381 ms	2432 KiB

railway

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 10050
vector<int> cnt(maxn,0);
vector<int> childcnt(maxn,0);
vector<int> curr(maxn,0);
vector<vector<pair<int,int> > > adj(maxn);
void dfs(int node,int parent){
    for(auto k:adj[node]){
        if(k.first!=parent){
            dfs(k.first,node);
            if(childcnt[k.first]>=1){
                cnt[k.second]++;
            }
            childcnt[node] += childcnt[k.first];
        }
    }
}
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int no_of_vertex,no_of_people,mini;
    int no_of_input;
    int input1,input2,input3,input;
    cin >> no_of_vertex >> no_of_people >> mini;
    for(int i=0;i<no_of_vertex-1;i++){
        cin >> input1 >> input2;
        adj[input1].push_back({input2,i});
        adj[input2].push_back({input1,i});
    }
    for(int i=0;i<no_of_people;i++){
        cin >> no_of_input;
        for(int j=0;j<no_of_input;j++){
            cin >> input;
            childcnt[input] = 1;
        }
        dfs(input,-1);
        for(int j=0;j<=no_of_vertex;j++){
            childcnt[j] = 0;
        }

        /*for(int j=0;j<=no_of_vertex;j++){
            cout << cnt[j] << " ";
        }
        cout << "\n";*/
    }
    vector<int> ans;
    for(int i=0;i<cnt.size();i++){
        if(cnt[i]>=mini){
            ans.push_back(i);
        }
    }
    cout << ans.size() << "\n";
    for(auto k:ans){
        cout << k+1 << " ";
    }

}

Compilation message (stderr)

railway.cpp: In function 'int32_t main()':
railway.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<cnt.size();i++){
                 ~^~~~~~~~~~~
railway.cpp:25:23: warning: unused variable 'input3' [-Wunused-variable]
     int input1,input2,input3,input;
                       ^~~~~~

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