Submission #930959

#	Time	Username	Problem	Language	Result	Execution time	Memory
930959		idiotcomputer	Railway (BOI17_railway)	C++11	100 / 100	653 ms	28104 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second 


const int mxN = 1e5;
int n,k;

vector<pii> adj[mxN];
int bj[mxN][20];
int first[mxN];
int pidx[mxN];
int ssize[mxN];
int res[mxN];

int cnt = 0;
void dfs(int node, int p){
    bj[node][0] = p;
    for (int i = 1; i < 20; i++){
        if (bj[node][i-1] == -1){
            break;
        }
        bj[node][i] = bj[bj[node][i-1]][i-1];
    }
    first[node] = cnt;
    cnt++;
    ssize[node] = 1;
   // cout << node << " -" << p << '\n';
    for (pii next : adj[node]){
        if (next.f != p){
            dfs(next.f,node);
            ssize[node] += ssize[next.f];
        } else {
            pidx[node] = next.s;
        }
    }
}

bool contain(int a, int b){
    if (first[a] <= first[b] && ssize[a] + first[a] > first[b]){
        return true;
    }
    return false;
}

int glca(int a, int b){
    if (a == -1){
        return b;
    }
    while (!contain(a,b)){
        for (int i = 1; i < 20; i++){
            if (bj[a][i] == -1 || contain(bj[a][i],b)){
                a = bj[a][i-1];
                break;
            }
        }
    }    
    return a;
}

bool segtree[4*mxN+1];

void upd(int t, bool v, int l = 0, int r = n-1, int idx = 0){
    if (l > t || r < t){
        return;
    }
    if (l == r){
        segtree[idx] = v;
        return;
    }
    int m = (l+r)/2;
    upd(t,v,l,m,2*idx+1);
    upd(t,v,m+1,r,2*idx+2);
    segtree[idx] = (segtree[2*idx+1] || segtree[2*idx+2]);
}

bool query(int tl, int tr, int l = 0, int r = n-1, int idx = 0){
    if (l > tr || r < tl){
        return false;
    }
    if (l >= tl & r <= tr){
        return segtree[idx];
    }
    int m = (l+r)/2;
    return query(tl,tr,l,m,2*idx+1) || query(tl,tr,m+1,r,2*idx+2);
}

void addon(int a){
    int next;
  //  cout << a << " : ";
    while (!query(first[a],first[a]+ssize[a]-1)){
        for (int i = 1; i < 20; i++){
            next = bj[a][i];
            if (next == -1 || query(first[next],first[next]+ssize[next]-1)){
                a = bj[a][i-1];
                break;
            }
        }
       // cout << a << " ";
    }    
   // cout << a << '\n';
    res[a] -= 1;
}

vector<int> tot;
void solve(int node, int p){
    for (pii next : adj[node]){
        if (next.f != p){
            solve(next.f,node);
            res[node] += res[next.f];
        }
    }
    if (res[node] >= k){
        tot.pb(pidx[node]+1);
    }
   // cout << res[node] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int m;
    cin >> n >> m >> k;
    
    
    int a,b;
    for (int i =0; i < n-1; i++){
        cin >> a >> b;
        a -= 1;
        b -= 1;
        adj[a].pb({b,i});
        adj[b].pb({a,i});
    }
    
    memset(res,0,sizeof(res));
    memset(segtree,0,sizeof(segtree));
    for (int i =0; i < mxN; i++) for (int j =0; j <20; j++) bj[i][j]=-1;
    dfs(0,-1);
    pidx[0] = -1;    
    int si,lca;
  /*  for (int i =0; i < n; i++) cout << first[i] << " ";
    cout << '\n';
    for (int i =0; i < n; i++) cout << ssize[i] << " ";
    cout << '\n';*/
    vector<int> all;
    for (int i = 0; i < m; i++){
        cin >> si;
        lca = -1;
        all.clear();
        for (int j = 0; j < si; j++){
            cin >> a;
            a -= 1;
            all.pb(a);
            lca = glca(lca,a);
        }
      //  cout << all[0] << '\n';
        upd(first[all[0]],true);
        res[all[0]]++;
        res[lca]--;
        for (int j = 1; j < all.size(); j++){
            addon(all[j]);
            res[all[j]]++;
            upd(first[all[j]],true);
        }
        for (int j = 0; j < all.size(); j++){
            upd(first[all[j]],false);
        }
      /*  for (int j =0; j < n; j++){
        cout << res[j] << " ";
    }
    cout << '\n';*/
    }
    
    solve(0,-1);
    sort(tot.begin(),tot.end());
    cout << (int) tot.size() << "\n";
    for (int i : tot){
        cout << i << " ";
    }
    cout << '\n';
    
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'bool query(int, int, int, int, int)':
railway.cpp:84:11: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   84 |     if (l >= tl & r <= tr){
      |         ~~^~~~~
railway.cpp: In function 'int main()':
railway.cpp:165:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         for (int j = 1; j < all.size(); j++){
      |                         ~~^~~~~~~~~~~~
railway.cpp:170:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |         for (int j = 0; j < all.size(); j++){
      |                         ~~^~~~~~~~~~~~

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