Submission #269966

#	Time	Username	Problem	Language	Result	Execution time	Memory
269966		brcode	Railway (BOI17_railway)	C++14	7 / 100	363 ms	48164 KiB

railway

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

using namespace std;
const int MAXN = 1e6+5;
int arr[MAXN];
int pref[MAXN];
vector<int> res;
map<pair<int,int>,int> m2;
vector<int> v1[MAXN];
map<int,int> m1;
int main(){
    int n,m,k;
    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<=n;i++){
        if(v1[i].size() == 1){
            arr[1] = i;
            break;
        }
        
    }
    for(int i=1;i<n;i++){
        for(int x:v1[i]){
            if(x!=arr[i-1]){
                arr[i+1] = x;
                break;
            }
        }
    }
    for(int i=1;i<=n;i++){
        m1[arr[i]] = i;
    }
    
    
    for(int i=1;i<=m;i++){
        int num;
        cin>>num;
        int mn = 1e9;
        int mx = 0;
        for(int i=1;i<=num;i++){
            int x;
            cin>>x;
            mn = min(mn,x);
            mx = max(mx,x);
        }
        pref[mn]++;
        pref[mx+1]--;
    }
    for(int i=1;i<=n;i++){
        pref[i]+=pref[i-1];
    }
    
    for(int i=2;i<=n;i++){
        if(pref[i]>=k && pref[i-1]>=k){
            
            res.push_back(m2[make_pair(arr[i],arr[i-1])]);
        }
    }
    cout<<res.size()<<endl;
    for(auto x:res){
        cout<<x<<" ";
    }
}

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