Submission #885215

#	Time	Username	Problem	Language	Result	Execution time	Memory
885215		Arshi	Railway (BOI17_railway)	C++17	100 / 100	77 ms	34504 KiB

railway

/**********************GOD**********************/

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <iterator>
#include <map>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll , ll> pll;

#define len                 length()
#define MP                  make_pair
#define fs                  first
#define sc                  second
#define pb                  push_back
#define all(x)              x.begin() , x.end()
#define kill(x)             cout << x , exit(0)


const int MXN = 2e5 + 4;
const int LOG = 23;

int n, m, k;
int tim;

vector<pair<int, int>> E;
vector<int> adj[MXN];
int dp[MXN], h[MXN], st[MXN];
int par[MXN][LOG];


void Build(int v = 1, int p = 0)
{
    st[v] = ++ tim;
    par[v][0] = p;
    for(int i = 1; i < LOG; i ++)
        par[v][i] = par[par[v][i - 1]][i - 1];
    for(int u : adj[v]) {
        if(u == p)
            continue;
        h[u] = h[v] + 1;
        Build(u, v);
    }
}

int Get(int v, int k)
{
    for(int i = 0; i < LOG; i ++)
        if(k >> i & 1)
            v = par[v][i];
    return v;
}

int LCA(int v, int u)
{
    if(h[v] < h[u]) swap(v, u);
    v = Get(v, h[v] - h[u]);
    if(v == u)
        return v;
    for(int i = LOG - 1; i >= 0; i --) {
        if(par[v][i] != par[u][i]) {
            v = par[v][i];
            u = par[u][i];
        }
    }
    return par[v][0];
}

void DFS(int v, int p = 0)
{
    for(int u : adj[v]) {
        if(u == p)
            continue;
        DFS(u, v);
        dp[v] += dp[u];
    }
}

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 v, u; cin >> v >> u;
        adj[v].pb(u);
        adj[u].pb(v);
        E.pb({v, u});
    }

    Build();

    while(m --) {
        vector<int> vc; int s; cin >> s;
        for(int i = 0; i < s; i ++) {
            int v; cin >> v;
            vc.pb(v);
        }
        sort(all(vc), [&](int i, int j) {
            return st[i] < st[j];
        });
        for(int i = 0; i < s; i ++) {
            int v = vc[i], u = vc[(i + 1) % s];
            int w = LCA(v, u);
            dp[v] ++; dp[u] ++;
            dp[w] -= 2;
        }
    }

    DFS(1);

    vector<int> ans;
    for(int i = 0; i < E.size(); i ++) {
        int v, u; tie(v, u) = E[i];
        if(h[v] < h[u])
            swap(v, u);
        if(dp[v] >= 2 * k)
            ans.pb(i + 1);
    }

    cout << ans.size() << '\n';
    for(int i : ans)
        cout << i << ' ';

    return 0;
}

/*!
ahkh
*/

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:124: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]
  124 |     for(int i = 0; i < E.size(); i ++) {
      |                    ~~^~~~~~~~~~

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