Submission #1096348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096348		tachvoi	Railway (BOI17_railway)	C++14	100 / 100	170 ms	42956 KiB

railway

#include <bits/stdc++.h>  

using namespace std;
#define N 200005
#define LOG 18

int tin[N], depth[N], timer, par[N][LOG], dp[N], n, q, k;
vector <int> adj[N], ans;
map <pair <int, int>, int> lab;

void dfs1(int u)
{
    tin[u] = ++timer;
    for (int v : adj[u])
        if (v != par[u][0]) par[v][0] = u, depth[v] = depth[u] + 1, dfs1(v);
}

int getlca(int u, int v)
{
    if (depth[u] < depth[v]) swap(u, v);
    for (int k = LOG - 1; k >= 0; k--)
        if (par[u][k] && depth[par[u][k]] >= depth[v]) u = par[u][k];

    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--)
        if (par[u][k] != par[v][k])
        {
            u = par[u][k];
            v = par[v][k];
        }

    return par[u][0];
}

void dfs2(int u)
{
    for (int v : adj[u])
        if (v != par[u][0]) dfs2(v), dp[u] += dp[v];

    if (dp[u] >= 2 * k) ans.push_back(lab[{u, par[u][0]}]);
}

bool cmp(int x, int y)
{
    return tin[x] < tin[y];
}

signed main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
  
    cin >> n >> q >> k; 
    for (int i = 1; i < n; i++)
    {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        lab[{u, v}] = lab[{v, u}] = i;
    }

    dfs1(1);
    for (int k = 1; k < LOG; k++)
        for (int u = 1; u <= n; u++)
            par[u][k] = par[par[u][k - 1]][k - 1];

    while (q--)
    {
        int m; cin >> m; vector <int> vec;
        for (int i = 1; i <= m; i++)
        {
            int x; cin >> x;
            vec.push_back(x);
        }

        sort(vec.begin(), vec.end(), cmp); vec.push_back(vec[0]);
        for (int i = 1; i < vec.size(); i++)
        {
            int u = vec[i - 1], v = vec[i];
            int lca = getlca(u, v);
            dp[u]++; dp[v]++; dp[lca] -= 2;
        }
    }

    dfs2(1); sort(ans.begin(), ans.end()); 
    cout << ans.size() << '\n';
    for (int x : ans) cout << x << ' ';
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for (int i = 1; i < vec.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