Submission #1101740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101740		qrn	Railway (BOI17_railway)	C++14	100 / 100	140 ms	52284 KiB

railway

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

template<class ISqr, class T>
ISqr& operator>>(ISqr& is, vector<T>& v) { for (auto& x : v) is >> x; return is; }

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define print(v) \
    for(auto& u : v) cout << u << " "; \
    cout << endl;

#define pb push_back
#define ins insert

#define fi first
#define er erase
#define se second
 
#define vi vector<int>
#define gi greater<int>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
 
#define endl "\n"
#define yes cout << "yes" << endl
#define no cout << "no" << endl
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define impos cout << -1 << endl;   
#define int long long

#define _ << " " << 

const int mod = 998244353;
const int inf = 1e18;
const int p = 47;
const int LOG = 11;

const int sz = 2e5 + 5;

vector<vi>graph(sz), up;
int timer, n, L;
vi giris(sz), cixis(sz), depth(sz), sub(sz), deg(sz);

void dfs(int node, int parent) {
    giris[node] = timer++;
    if(node != parent) {
        depth[node] = depth[parent] + 1;
    }

    up[node][0] = parent;
    for(int i=1;i <= L;i++){
        up[node][i] = up[up[node][i-1]][i-1];
    }

    for(auto u : graph[node]) {
        if(u != parent) {
            dfs(u, node);
        }
    }
    cixis[node] = timer++;
}

bool check_ancestor(int a, int b) {
    if(giris[a] <= giris[b] && cixis[a] >= cixis[b]) return true;
    return false; 
}

int lca(int a, int b) {
    if(check_ancestor(a,b)) return a;
    if(check_ancestor(b,a)) return b;
    for(int i = L; i >= 0; i--) {
        if(!check_ancestor(up[a][i], b)) a = up[a][i];
    }
    return up[a][0];
}
int tt;
void dfs2(int node, int parent = -1) {
    tt++;
    for(auto u : graph[node]) {
        if(u != parent) {
            // cout << "DFS: " << u << " " << node << " " << tt << endl;
            dfs2(u, node);
            // cout << "DFSS: " << u << " " << node << " "<< tt << endl;
            sub[node] += sub[u];
        }
    }
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    graph.resize(n+1);
    giris.assign(n+1, 0);
    cixis.assign(n+1, 0);
    L = ceil(log2(n));
    up.assign(n+1, vi(L+1));
    sub.resize(n+1);
    timer = 0;
    // cout << "ISLEYIREM" << endl;
    vi recs; vpii edges;
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].pb(b);
        graph[b].pb(a);
        ++deg[a]; ++deg[b];
        edges.pb({a,b});
    }
    // cout << "IISLEYIREM" << endl;
    int root = 0;
    for(int i = 1; i <= n; i++) {
        if(deg[i] == 1) {
            root = i;
            break;
        }
    }
    // cout << "Root: " << root << endl;
    // cout << "IIISLEYIREM" << endl;
    dfs(root, root);
    // cout << "IIIISLEYIREM" << endl;
    for(int i = 0; i < m; i++) {
        int s;
        cin >> s;
        vi cock(s);
        cin >> cock;
        sort(ALL(cock),[&](int a, int b){
            return giris[a] < giris[b];
        });
        cock.pb(cock[0]);
        for(int j = 0; j < s; j++) {
            sub[cock[j]]++;
            sub[cock[j+1]]++;
            sub[lca(cock[j],cock[j+1])] -= 2;
        }
    }
    // for(int i = 1; i <= n; i++) {
    //     cout << "Init: " << i <<  " " << sub[i] << endl;
    // }
    // cout << "IIIISLEYIREM" << endl;
    dfs2(root);
    // cout << "IIIIISLEYIREM" << endl;
    // for(int i = 1; i <= n; i++) {
    //     cout << i << " " << sub[i] << endl;
    // }
    // cout << endl;

    set<pii>cockset;
    for(int i = 1; i <= n; i++) {
        if(sub[i] >= 2 * k) {
            cockset.ins({min(i, up[i][0]), max(i, up[i][0])});
        }
    }
    int ind = 0;
    for(auto u : edges) {
        bool checker = cockset.count({min(u.fi,u.se),max(u.fi,u.se)});
        if(checker) recs.pb(ind+1);
        ind++;
    }
    cout << sz(recs) << endl;
    for(int i : recs) cout << i << " ";
    cout << endl;
}
 
signed main() {
    SPEED;
    int tst = 1;
    // cin >> tst;
    for (int cs = 1; cs <= tst; cs++) {
        solve();
    }
    // cerr << "Time Elapsed: " << (long double)clock() << eel;
}

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