Submission #732881

#	Time	Username	Problem	Language	Result	Execution time	Memory
732881		Trunkty	Railway (BOI17_railway)	C++14	100 / 100	285 ms	74444 KiB

railway

#include <bits/extc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n,m,k;
vector<vector<int>> roads[100005];
int jump[100005][21],dep[100005];
vector<int> toadd[100005],torem[100005];
set<int> s[100005];
int roadid[100005];
vector<int> ans;

void dfs(int x, int p){
    for(vector<int> i:roads[x]){
        if(i[0]!=p){
            dep[i[0]] = dep[x]+1;
            jump[i[0]][0] = x;
            roadid[i[0]] = i[1];
            dfs(i[0],x);
        }
    }
}

int lca(int a, int b){
    if(dep[a]>dep[b]){
        swap(a,b);
    }
    for(int j=20;j>=0;j--){
        if(dep[b]-(1<<j)>=dep[a]){
            b = jump[b][j];
        }
    }
    if(a==b){
        return a;
    }
    for(int j=20;j>=0;j--){
        if(jump[a][j]!=jump[b][j]){
            a = jump[a][j];
            b = jump[b][j];
        }
    }
    return jump[a][0];
}

void dfs2(int x, int p){
    for(int i:toadd[x]){
        s[x].insert(i);
    }
    for(vector<int> i:roads[x]){
        if(i[0]!=p){
            dfs2(i[0],x);
            if(s[i[0]].size()>s[x].size()){
                swap(s[x],s[i[0]]);
            }
            for(int j:s[i[0]]){
                s[x].insert(j);
            }
        }
    }
    for(int i:torem[x]){
        s[x].erase(i);
    }
    if(x==1){
        return;
    }
    if(s[x].size()>=k){
        ans.push_back(roadid[x]);
    }
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n >> m >> k;
    for(int i=1;i<=n-1;i++){
        int a,b;
        cin >> a >> b;
        roads[a].push_back({b,i});
        roads[b].push_back({a,i});
    }
    dfs(1,-1);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            jump[i][j] = jump[jump[i][j-1]][j-1];
        }
    }
    for(int i=1;i<=m;i++){
        int a;
        cin >> a;
        vector<int> v;
        for(int j=1;j<=a;j++){
            int b;
            cin >> b;
            v.push_back(b);
            toadd[b].push_back(i);
        }
        while(v.size()>=2){
            int b = v.back();
            v.pop_back();
            int c = v.back();
            v.pop_back();
            v.push_back(lca(b,c));
        }
        torem[v[0]].push_back(i);
    }
    dfs2(1,-1);
    sort(ans.begin(),ans.end());
    cout << ans.size() << "\n";
    for(int i:ans){
        cout << i << " ";
    }
	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs2(ll, ll)':
railway.cpp:67:19: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   67 |     if(s[x].size()>=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