Submission #1115854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115854		vjudge1	Railway (BOI17_railway)	C++17	100 / 100	211 ms	39484 KiB

railway

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn = 1e5+5, inf=1e18;

struct FenwickTree{
    int n;
    vector<long long> bit;
    FenwickTree(){}
    FenwickTree(int n): n(n), bit(n+1, 0LL){}
    void update(int idx, long long v){
        if(idx <= 0) return;
        for(;idx<=n;idx+=(idx&-idx)) bit[idx]+=v;
    }
    long long getSum(int idx){
        if(idx <= 0) return 0;
        long long res = 0;
        for(;idx;idx-=idx&-idx) res += bit[idx];
        return res;
    }
};

int n,m,k,id[maxn];
vector<int> G[maxn], all, st, ans;
FenwickTree bit;
map<pair<int,int>, int> mp;

int sp[maxn], ep[maxn], timer = 1;
void tour(int u, int p){
    sp[u] = timer++;
    for(int c: G[u]){
        if(c != p) tour(c, u);
    }
    ep[u] = timer - 1;
}

int par[17][maxn], depth[maxn];
void binlift(int u, int p){
    par[0][u] = p;
    f1(i, 16) par[i][u] = par[i-1][par[i-1][u]];
    for(int c: G[u]){
        if(c != p) {
            id[c] = mp[{c, u}];
            depth[c] = depth[u] + 1;
            binlift(c, u);
        }
    }
}

int jump(int u, int l){
    for(int i=0;i<17;i++){
        if(l & (1 << i)) u = par[i][u];
    }
    return u;
}

int LCA(int u, int v){
    if(depth[u] > depth[v]) swap(u, v);
    v = jump(v, depth[v] - depth[u]);
    if(u == v) return u;
    for(int i=16;i>=0;i--){
        if(par[i][u] != par[i][v]){
            u = par[i][u];
            v = par[i][v];
        }
    }
    return par[0][u];
}

bool cmp(int u, int v){
    return sp[u] < sp[v];
}

bool isParent(int u, int v){
    return sp[u] <= sp[v] && ep[v] <= ep[u];
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n >> m >> k;
    f1(i,n-1){
        ll u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
        mp[{u, v}] = i;
        mp[{v, u}] = i;
    }
    bit = FenwickTree(n);
    tour(1, 0);
    binlift(1, 0);
    while(m--){
        int s; cin >> s;
        all.clear();
        f1(i, s){
            int u; cin >> u;
            all.push_back(u);
        }
        sort(all.begin(), all.end(), cmp);
        for(int i=1;i<s;i++){
            all.push_back(LCA(all[i], all[i-1]));
        }
        sort(all.begin(), all.end(), cmp);
        all.resize(unique(all.begin(), all.end()) - all.begin());
        st.clear();
        st.push_back(all.front());
        for(int i=1;i<all.size();i++){
            while(!isParent(st.back(), all[i])){
                st.pop_back();
            }
            bit.update(sp[st.back()], -1);
            bit.update(sp[all[i]], 1);
            st.push_back(all[i]);
        }
    }
    f1(i,n){
        if(bit.getSum(ep[i]) - bit.getSum(sp[i] - 1) >= k){
            ans.push_back(id[i]);
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size();el;
    for(int item: ans) cout << item << ' ';
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for(int i=1;i<all.size();i++){
      |                     ~^~~~~~~~~~~
railway.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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