Submission #519128

#	Time	Username	Problem	Language	Result	Execution time	Memory
519128		Yazan_Alattar	Railway (BOI17_railway)	C++14	23 / 100	1073 ms	432948 KiB

railway

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
#include <assert.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 200007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

set <int> v[M];
vector <int> ans, add[M], rem[M];
vector < pair <int,int> > adj[M];
int n, m, k, anc[M][20], dep[M], sz[M], len[M];

void calc(int node, int p)
{
    for(auto i : adj[node]) if(i.F != p){
        dep[i.F] = dep[node] + 1;
        anc[i.F][0] = node;
        calc(i.F, node);
    }
    return;
}

int lca(int x, int y)
{
    if(x == y) return x;
    if(dep[x] > dep[y]) swap(x, y);
    for(int i = 19; i >= 0; --i) if(anc[y][i] && dep[anc[y][i]] >= dep[x]) y = anc[y][i];
    if(x == y) return x;
    for(int i = 19; i >= 0; --i) if(anc[x][i] && anc[x][i] != anc[y][i]){
        x = anc[x][i];
        y = anc[y][i];
    }
    return anc[x][0];
}

void calcsz(int node, int p)
{
    sz[node] = add[node].size();
    for(auto i : adj[node]) if(i.F != p){
        calcsz(i.F, node);
        sz[node] += sz[i.F];
    }
    return;
}

void dfs(int node, int p)
{
    int big = 0;
    for(auto i : adj[node]) if(i.F != p && sz[i.F] > sz[big]) big = i.F;
    for(auto i : adj[node]) if(i.F != p && i.F != big) dfs(i.F, node);
    if(big){
        dfs(big, node);
        swap(v[big], v[node]);
    }
    for(auto i : add[node]) v[node].insert(i);
    for(auto i : adj[node]) if(i.F != p && i.F != big) for(auto j : v[i.F]) v[node].insert(j);
    for(auto i : rem[node]) v[node].erase(i);
    len[node] = v[node].size();
    return;
}

void get(int node, int p)
{
    for(auto i : adj[node]) if(i.F != p){
        if(len[i.F] >= k) ans.pb(i.S);
        get(i.F, node);
    }
    return;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i < n; ++i){
        int a, b;
        cin >> a >> b;
        adj[a].pb({b, i});
        adj[b].pb({a, i});
    }
    calc(1, 0);
    for(int j = 1; j < 20; ++j) for(int i = 1; i <= n; ++i) anc[i][j] = anc[anc[i][j - 1]][j - 1];
    for(int i = 1; i <= m; ++i){
        int s, res = 0;
        cin >> s;
        for(int j = 1; j <= s; ++j){
            int x; cin >> x;
            if(res == 0) res = x;
            else res = lca(res, x);
            add[x].pb(i);
        }
        rem[res].pb(i);
    }
    dfs(1, 0);
    get(1, 0);
    sort(all(ans));
    cout << ans.size() << endl;
    for(auto i : ans) cout << i << " ";
    cout << endl;
    return 0;
}

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