Submission #272125

#	Time	Username	Problem	Language	Result	Execution time	Memory
272125		brcode	Railway (BOI17_railway)	C++14	100 / 100	796 ms	147596 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 h[MAXN];
vector<int> tosub[MAXN];
int dp[MAXN][32];
set<int> s1[MAXN];
int p[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){
    int edgenum = -1;
    if(curr!=par){
        edgenum = m2[make_pair(curr,par)];
    }
    int ind = curr;
    for(auto x:v1[curr]){
        if(x!=par){
            dfs(x,curr);
            if(s1[p[ind]].size()<s1[p[x]].size()){
                ind = p[x];
            }
        }
    }
    p[curr] = ind;
    for(int x:s1[curr]){
        s1[ind].insert(x);
    }
    for(auto x:v1[curr]){
        if(x==par||p[x] == ind){
            continue;
        }
        for(int j:s1[p[x]]){
            s1[ind].insert(j);
        }
    }
    for(int x:tosub[curr]){
        s1[ind].erase(x);
    }
    if(s1[ind].size()>=k && edgenum!=-1){
        res.push_back(edgenum);
    }
}
void precalcdfs(int curr,int par,int depth){
    if(curr!=par){
        dp[curr][0] = par;
        h[curr] = depth;
    }else{
        h[curr] = 1;
        dp[curr][0] = -1;
    }
    for(int j=1;j<=30;j++){
        if(dp[curr][j-1]!=-1){
            dp[curr][j] = dp[dp[curr][j-1]][j-1];
        }
    }
    for(int x:v1[curr]){
        if(x!=par){
            precalcdfs(x,curr,depth+1);
        }
    }
}
int lca(int x,int y){
    if(h[x]>h[y]){
        swap(x,y);
    }
    
    for(int i=20;i>=0;i--){
        if(h[y]-(1<<i) >=h[x]){
            y = dp[y][i];
        }
    }
    
    if(x == y){
        return x;
    }
    for(int i=20;i>=0;i--){
        if(dp[x][i]!=-1 && dp[x][i]!=dp[y][i]){
            x= dp[x][i];
            y = dp[y][i];
        }
    }
    return dp[x][0];
}
int main(){
    /*#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
    #endif*/
    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++){
        for(int j=0;j<=30;j++){
            dp[i][j] = -1;
        }
    }
    precalcdfs(1,1,1);
  
    for(int i=1;i<=m;i++){
        int len;
        cin>>len;
        int x;
        cin>>x;
        len--;
        s1[x].insert(i);
        int templ = x;
        for(int j=1;j<=len;j++){
            int x;
            cin>>x;
            s1[x].insert(i);
            templ = lca(templ,x);
        }
        tosub[templ].push_back(i);
        
    }
    dfs(1,1);
    sort(res.begin(),res.end());
    cout<<res.size()<<endl;
    for(int x:res){
        cout<<x<<endl;
    }
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:51:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |     if(s1[ind].size()>=k && edgenum!=-1){
      |        ~~~~~~~~~~~~~~^~~

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