Submission #1108196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108196		InvMOD	Railway (BOI17_railway)	C++14	100 / 100	78 ms	28944 KiB

railway

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 1e5+5;
const int lg = 21;


int n, m, k, timerDFS, h[N];

int tin[N], tout[N], par[lg][N], val[N];

pair<int,int> E[N];
vector<int> g[N], answer;


void pre_dfs(int x, int p){
    tin[x] = ++timerDFS;

    for(int id : g[x]){
        int v = E[id].first ^ E[id].second ^ x;
        if(v != p){
            h[v] = h[x] + 1;
            par[0][v] = x;
            for(int i = 1; i < lg; i++) par[i][v] = par[i-1][par[i-1][v]];
            pre_dfs(v, x);
        }
    }

    tout[x] = timerDFS;
    return;
}

bool inSub(int u, int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

bool cmpDFS(int u, int v){
    return tin[u] < tin[v];
}

int get_LCA(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    int k = h[u] - h[v];
    for(int i = lg-1; i >= 0; i--) if(k>>i&1) u = par[i][u];
    if(u == v) return v;
    for(int i = lg-1; i >= 0; i--) if(par[i][u] != par[i][v]) u = par[i][u], v = par[i][v];
    return par[0][v];
}

void solve_Query(vector<int>& vec){
    sort(all(vec), cmpDFS);

    int k = sz(vec);
    for(int i = 1; i < k; i++) vec.pb(get_LCA(vec[i], vec[i-1]));

    sort(all(vec), cmpDFS), compact(vec);
    stack<int> st; st.push(vec[0]);

    for(int i = 1; i < sz(vec); i++){
        int v = vec[i];
        while(!inSub(st.top(), v)) st.pop();

        val[v]++, val[st.top()]--;
        st.push(v);
    }
    return;
}

void proc_val(int x, int p){
    for(int id : g[x]){
        int v = E[id].first ^ E[id].second ^ x;
        if(v != p){
            proc_val(v, x);
            val[x] += val[v];
            if(val[v] >= k) answer.push_back(id);
        }
    }
    return;
}

void solve()
{
    cin >> n >> m >> k;
    for(int i = 1; i < n; i++){
        int u,v; cin >> u >> v;
        E[i] = make_pair(u, v);
        g[u].pb(i), g[v].pb(i);
    }

    pre_dfs(1, -1);

    for(int i = 1; i <= m; i++){
        int k; cin >> k;
        vector<int> vec;
        for(int j = 1; j <= k; j++){
            int v; cin >> v;
            vec.push_back(v);
        }

        solve_Query(vec);
    }

    proc_val(1, -1);

    cout << sz(answer) <<"\n";

    sort(all(answer));
    for(int id : answer) cout << id <<" "; cout <<"\n";
}

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

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void solve()':
railway.cpp:127:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  127 |     for(int id : answer) cout << id <<" "; cout <<"\n";
      |     ^~~
railway.cpp:127:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  127 |     for(int id : answer) cout << id <<" "; cout <<"\n";
      |                                            ^~~~
railway.cpp: In function 'int main()':
railway.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         freopen(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