Submission #519534

#	Time	Username	Problem	Language	Result	Execution time	Memory
519534		Yazan_Alattar	Railway (BOI17_railway)	C++14	100 / 100	120 ms	28860 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};

vector <int> ans;
vector < pair <int,int> > adj[M];
int n, m, k, anc[M][20], dep[M], in[M], out[M], pref[M], timer, edge[M], c[M];

bool cmp(int a, int b)  { return in[a] < in[b]; }

void calc(int node, int p)
{
    in[node] = ++timer;
    for(auto i : adj[node]) if(i.F != p){
        edge[i.F] = i.S;
        dep[i.F] = dep[node] + 1;
        anc[i.F][0] = node;
        calc(i.F, node);
    }
    out[node] = ++timer;
    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 get(int node, int p)
{
    for(auto i : adj[node]) if(i.F != p){
        get(i.F, node);
        pref[node] += pref[i.F];
        if(pref[i.F] >= 2 * k) ans.pb(i.S);
    }
    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) cin >> c[j];
        sort(c + 1, c + s + 1, cmp);
        c[s + 1] = c[1];
        for(int i = 1; i <= s; ++i){
            ++pref[c[i]];
            ++pref[c[i + 1]];
            pref[lca(c[i], c[i + 1])] -= 2;
        }
    }
    get(1, 0);
    sort(all(ans));
    cout << ans.size() << endl;
    for(auto i : ans) cout << i << " ";
    cout << endl;
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:82:16: warning: unused variable 'res' [-Wunused-variable]
   82 |         int s, res = 0;
      |                ^~~

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