Submission #1084672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084672		LTTrungCHL	Railway (BOI17_railway)	C++17	100 / 100	78 ms	25772 KiB

railway

///***LTT***///
/// ->NHAT QUOC GIA<- ///
#include<bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
//#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
using namespace std;
vector <int> lg2;
void MAKE_LOG_ARR(int n){
    lg2.resize(n + 3);
    for (int i = 1;i <= n;++i){
        lg2[i] = __lg(i);
    }
}
const long long oo = 1e9+7;
const int N = 1e5 + 10;
int n, m, k;
int sum[N];
int L[N], R[N], h[N], elt;
int ST[20][N];
int ans[N];
vector <int>  vec, vans;
vector <pair <int ,int>> adj[N],edge;
stack <int> st;
int lca(int u, int v){
    if (h[u] < h[v]) swap(u, v);
    int lg = lg2[h[u]];
    for (int i = lg;i >= 0;--i){
        if (h[ST[i][u]] >= h[v]){
            u = ST[i][u];
        }
    }
    if (u == v) return u;
    for (int i = lg;i >= 0;--i){
        if (ST[i][u] != ST[i][v]){
            u = ST[i][u];
            v = ST[i][v];
        }
    }
    return ST[0][u];
}
void pre(int u, int p){
    L[u] = ++elt;
    h[u] = h[p] + 1;
    for (int i = 0;i < adj[u].size();++i){
        int v = adj[u][i].F;
        if (v == p) continue;
        pre(v, u);
        ST[0][v] = u;
    }
    R[u] = elt;
    return;
}
void dfs(int u, int p){
    for (int i = 0;i < adj[u].size();++i){
        int v = adj[u][i].F;
        if (v == p) continue;
        int id = adj[u][i].S;
        dfs(v, u);
        sum[u] += sum[v];
        ans[id] = sum[v];
    }
    return;
}
bool cmp(int a, int b){
    return L[a] < L[b];
}
bool isp(int u, int v){
    return L[u] <= L[v] and R[u] >= L[v];
}
void build_vitural_tree(){
    int sz = vec.size();
    sort(vec.begin(), vec.end(), cmp);
    for (int i = 0;i < sz - 1;++i){
        int lc = lca(vec[i], vec[i + 1]);
        vec.pb(lc);
    }
    sort(vec.begin(), vec.end(), cmp);
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    while (!st.empty()) st.pop();
    st.push(vec[0]);
    for (int i = 1;i < vec.size();++i){
        while (!isp(st.top() ,vec[i])){
            st.pop();
        }
        int u = st.top();
        int v = vec[i];
        st.push(v);
        edge.pb({u,v});
        ///u - > v;
    }
    return;
}
void solve(){
    cin >> n >> m >> k;
    MAKE_LOG_ARR(n);
    for (int i = 1;i < n;++i){
        int u, v;
        cin >> u >> v;
        adj[u].pb({v,i});
        adj[v].pb({u,i});
    }
    pre(1,0);
    for (int i = 1;i <= lg2[n];++i){
        for (int j = 1;j <= n;++j){
            ST[i][j] = ST[i-1][ST[i-1][j]];
        }
    }
    while(m--){
        int x;
        cin >> x;
        edge.clear();
        vec.clear();
        for (int i = 1;i <= x;++i){
            int u;
            cin >> u;
            vec.pb(u);
        }
        build_vitural_tree();
        for (int i = 0;i < edge.size();++i){
            int u = edge[i].F;
            int v = edge[i].S;
            ++sum[v];
            --sum[u];
        }
    }
    dfs(1,0);
    for (int i = 1;i < n;++i){
        if (ans[i] >= k){
            vans.pb(i);
        }
    }
    sort(vans.begin(), vans.end());
    cout << vans.size() <<"\n";
    for (int i : vans){
        cout << i <<" ";
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    if (fopen("ltt.inp", "r")){
        freopen("ltt.inp", "r", stdin);
        freopen("ltt.out", "w", stdout);
    }
//    int t;
//    cin >> t;
//    while(t--){
    solve();
//    }
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void pre(int, int)':
railway.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0;i < adj[u].size();++i){
      |                    ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'void dfs(int, int)':
railway.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0;i < adj[u].size();++i){
      |                    ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'void build_vitural_tree()':
railway.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int i = 1;i < vec.size();++i){
      |                    ~~^~~~~~~~~~~~
railway.cpp: In function 'void solve()':
railway.cpp:125:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for (int i = 0;i < edge.size();++i){
      |                        ~~^~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:150:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         freopen("ltt.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen("ltt.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