Submission #347031

#	Time	Username	Problem	Language	Result	Execution time	Memory
347031		FatihSolak	Railway (BOI17_railway)	C++17	100 / 100	350 ms	71784 KiB

railway

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl "\n"
#define all(x) (x).begin(), (x).end()
using namespace std;
const int INF = (int) 1e9;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n,m,k;
vector<int> adj[MAXN];
int fake[MAXN];
int cnt = 1;
int arr[MAXN];
vector<int> nums[MAXN];
map<pii,int> mp;
map<pii,int> edge;
vector<pii> query;
vector<set<int>> sets(MAXN);
vector<int> ans;
int pare[MAXN];
void dfs(int v,int par){
    fake[v] = cnt++;
    for(auto u:adj[v]){
        if(u == par)continue;
        dfs(u,v);
        arr[fake[u]] = cnt-1;
        query.push_back({fake[u],cnt-1});
    }
}
struct BIT{
    vector<int> bit;
    int n;
    BIT(int l){
        this->n = l+1;
        bit.assign(l+1,0);
    }
    void upd(int pos,int val){
        for(;pos<n;pos+=pos&-pos){
            bit[pos]+=val;
        }
    }
    int get(int pos){
        int ret = 0;
        for(;pos>0;pos-=pos&-pos){
            ret+=bit[pos];
        }
        return ret;
    }
};
void dfs2(int v,int par){
    if(adj[v].size() == 1 && par!=-1){
        for(auto u:nums[v])sets[v].insert(u);
        if((sets[v].size()-mp[{fake[v],arr[fake[v]]}])>=k){
            ans.push_back(edge[{min(v,par),max(v,par)}]);
        }
        pare[v] = v;
        return;
    }
    int num = 0;
    for(auto u:adj[v]){
        if(u!=par){
            dfs2(u,v);
            if(num == 0 || sets[pare[u]].size() > sets[num].size()){
                num = pare[u];
            }
        }
    }
    for(auto u:adj[v]){
        if(u!=par && pare[u]!=num){
            for(auto c:sets[pare[u]]){
                sets[num].insert(c);
            }
        }
    }
    for(auto u:nums[v]){
        sets[num].insert(u);
    }
    if((sets[num].size()-mp[{fake[v],arr[fake[v]]}])>=k){
        ans.push_back(edge[{min(v,par),max(v,par)}]);
    }
    pare[v] = num;
}
void solve(){
    cin >> n >> m >> k;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin >> a >> b;
        edge[{min(a,b),max(a,b)}] = i+1;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1,-1);
    arr[1] = n;
    query.push_back({1,n});
    multiset<pii> ranges;
    BIT bt(n);
    for(int i=0;i<m;i++){
        int s;
        cin >> s;
        int mini =INF;
        int maxi = 0;
        for(int j=0;j<s;j++){
            int a;
            cin >> a;
            nums[a].push_back(i+1);
            mini = min(mini,fake[a]);
            maxi = max(maxi,fake[a]);
        }
        ranges.insert({mini,maxi});
        bt.upd(maxi,1);
    }
    sort(all(query));
    for(auto u:query){
        while(!ranges.empty() && ranges.begin()->ff < u.ff){
            bt.upd(ranges.begin()->ss,-1);
            ranges.erase(ranges.begin());
        }
        mp[u] = bt.get(u.ss);
    }
    dfs2(1,-1);
    cout << ans.size() << endl;
    sort(all(ans));
    for(auto u:ans){
        cout << u << " ";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message (stderr)

railway.cpp: In function 'void dfs2(int, int)':
railway.cpp:59:55: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |         if((sets[v].size()-mp[{fake[v],arr[fake[v]]}])>=k){
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
railway.cpp:84:53: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |     if((sets[num].size()-mp[{fake[v],arr[fake[v]]}])>=k){
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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