Submission #870429

#	Time	Username	Problem	Language	Result	Execution time	Memory
870429		BBart888	Railway (BOI17_railway)	C++14	36 / 100	71 ms	26960 KiB

railway

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <stack>
#include <stdio.h>      
#include <stdlib.h>     
#include <time.h> 
#include <string>
#include <fstream>
#include <unordered_map>



using namespace std;
using ll = long long;
using ld = long double;



using Mat = array<array<ll, 2>, 2>;
const ll mod1 = 1e9 + 7;
const ll mod2 = 1e9 + 123;
const int MAXN = 1e5 + 11;
const ll P = 31;


struct Node {
    int time_in, time_out, v;
};

int n, m, k;
vector<pair<int,int>> adj[MAXN];
int ans[MAXN];
int tin[MAXN];
int timer;
int tout[MAXN];
int up[MAXN][21];
int papa[MAXN];
int dp[MAXN];

vector<Node> vec;

bool cmp(Node a, Node b)
{
    if (a.time_in != b.time_in)
        return a.time_in > b.time_in;
    return a.time_out < b.time_out;
}


void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= 20; ++i)
        up[v][i] = up[up[v][i - 1]][i - 1];

    for (auto u : adj[v]) {
        if (u.first != p)
        {
            dfs(u.first, v);
            papa[u.first] = u.second;
        }
        
     }

    tout[v] = ++timer;
}

bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = 20; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}



void dfs2(int v, int p)
{


    for (auto u : adj[v])
    {
        if (u.first == p)
            continue;
        dfs2(u.first, v);
        dp[v] += dp[u.first];
    }
    ans[papa[v]] = dp[v];
}




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);



    //freopen("runaway.in", "r", stdin);
    //freopen("runaway.out", "w", stdout);

    cin >> n >> m >> k;

    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back({ b ,i});
        adj[b].push_back({ a ,i});
    }

    dfs(1, 1);

    for (int i = 0; i < m; i++)
    {
        int s;
        cin >> s;
        vec.clear();
        for (int j = 0; j < s; j++)
        {
            int v;
            cin >> v;
            vec.push_back({ tin[v],tout[v],v });
        }

        sort(vec.begin(), vec.end(), cmp);

        int curr_lca = lca(vec[0].v,vec[1].v);
        dp[vec[0].v]++;
        if (curr_lca == vec[1].v)
        {
            dp[vec[1].v]--;
        }
        else
        {
            dp[vec[1].v]++;
            dp[curr_lca]-=2;
        }

        for (int i = 2; i < vec.size(); i++)
        {
            dp[curr_lca]++;
            curr_lca = lca(curr_lca, vec[i].v);
            if (curr_lca == vec[i].v)
            {
                dp[vec[i].v]--;
            }
            else
            {
                dp[vec[i].v]++;
                dp[curr_lca]-=2;
            }
        }
        
    }

    dfs2(1, 1);

    vector<int> fin;
    for (int i = 1; i < n; i++)
        if (ans[i] >= k)
            fin.push_back(i);

    cout << fin.size() << '\n';
    for (auto x : fin)
        cout << x << " ";




    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:161:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |         for (int i = 2; i < vec.size(); i++)
      |                         ~~^~~~~~~~~~~~

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