Submission #870424

#	Time	Username	Problem	Language	Result	Execution time	Memory
870424		BBart888	Railway (BOI17_railway)	C++14	23 / 100	617 ms	524288 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 = 2e5 + 11;
const ll P = 31;


int n, m, k;
vector<pair<int,int>> adj[MAXN];
set<int> curr[MAXN];
int ans[MAXN];
vector<int> to_del[MAXN];
int tin[MAXN];
int timer;
int tout[MAXN];
int up[MAXN][30];
int papa[MAXN];


void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= 29; ++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 = 29; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}




set<int> merge(set<int> a, set<int> b)
{
    if (a.size() > b.size())
        swap(a, b);
    for (auto x : a)
        b.insert(x);
    a.clear();
    return b;
}


void dfs2(int v, int p)
{

    for (auto u : adj[v])
    {
        if (u.first == p)
            continue;
        dfs2(u.first, v);
        curr[v] = merge(curr[v], curr[u.first]);
    }
    for(auto D : to_del[v])
    if (curr[v].find(D) != curr[v].end())
        curr[v].erase(D);
    
    //cout << " NOW NODE: " << v << '\n';
    //for (auto x : curr[v])
        //cout << x << " ";
    //cout << '\n';
    ans[papa[v]] = curr[v].size();
}



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 = 1; i <= m; i++)
    {
        int s;
        cin >> s;
        int lc;
        vector<int> arr;
        for (int j = 0; j < s; j++)
        {
            int v;
            cin >> v;
            arr.push_back(v);
            curr[v].insert(i);
        }

        lc = lca(arr[0], arr[1]);
        for (int i = 2; i < arr.size(); i++)
            lc = lca(lc, arr[i]);
        to_del[lc].push_back(i);
        //cout << "LCA " << lc << '\n';
    }

    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:157:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |         for (int i = 2; i < arr.size(); i++)
      |                         ~~^~~~~~~~~~~~

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