Submission #270388

#	Time	Username	Problem	Language	Result	Execution time	Memory
270388		brcode	Railway (BOI17_railway)	C++14	23 / 100	1092 ms	51344 KiB

railway

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1e6+5;
int n,m,k;
int arr[MAXN];
int tmp[MAXN];
bool blocked[MAXN];
int sz[MAXN];
vector<int> res;
map<pair<int,int>,int> m2;
vector<int> v1[MAXN];
map<int,int> m1;
int side1;
int hold;
void dfs(int curr,int par){
    
    if(blocked[curr]){
        sz[curr] = 1;
        
    }
    
    for(int x:v1[curr]){
        if(x!=par){
            
            
            dfs(x,curr);
            if(sz[x]!=hold && sz[x]!=0){
                tmp[m2[make_pair(x,curr)]]++;
               // cout<<x<<" "<<curr<<" "<<sz[x]<<" "<<hold<<endl;
            }
            sz[curr]+=sz[x];
        }
    }
    
}
int main(){
    
    cin>>n>>m>>k;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        v1[x].push_back(y);
        v1[y].push_back(x);
        m2[make_pair(x,y)] = i;
        m2[make_pair(y,x)] = i;
    }
    
   
  
    for(int i=1;i<=m;i++){
        int val;
        cin>>val;
        for(int j=1;j<=n;j++){
            blocked[j] = false;
            sz[j] = 0;
        }
        
        for(int j=1;j<=val;j++){
            int x;
            cin>>x;
            blocked[x] = true;
        }
        side1 = val;
        hold = val;
        dfs(1,1);
        
    }
    for(int i=1;i<n;i++){
        if(tmp[i]>=k){
            res.push_back(i);
        }
    }
    cout<<res.size()<<endl;
    for(int x:res){
        cout<<x<<endl;
    }
}

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