Submission #472902

#	Time	Username	Problem	Language	Result	Execution time	Memory
472902		soba	Railway (BOI17_railway)	C++14	100 / 100	400 ms	64032 KiB

railway

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, l, m , k;
vector<int> adj[100005];
int nodes[100005];
int parent[100005] , level[100005] , sz[100005], sol[100005];
int timer;
vector<int> tin, tout;
vector<vector<int>> up;
set<int>st[100005], en[100005];
void dfs(int v, int p, int lvl)
{
    sz[v]++;
    level[v]=lvl;
    parent[v]=p;
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for (int u : adj[v]) {
        if (u != p)
        {
            dfs(u, v , lvl+1);
            sz[v]+=sz[u];
        }
    }
    tout[v] = ++timer;
    return;
}

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 = l; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}

void preprocess(int root) {
    tin.resize(n+1);
    tout.resize(n+1);
    timer = 0;
    l = ceil(log2(n+1));
    up.assign(n+1, vector<int>(l + 1));
    dfs(root, root , 0);
}
set<int> smalltolarge(int node , int p )
{
    set<int>cst;
    for(int u : st[node])
        cst.insert(u);
    for(int u : adj[node])
    {
        if(u==p)
            continue;
        set<int>nst=smalltolarge(u,node);
        if(nst.size()>cst.size())
        {
            swap(cst , nst);
        }
        for(int uu : nst)
            cst.insert(uu);
    }
    set<int>::iterator it;
    for(int u : en[node])
    {
        it=cst.lower_bound(u);
        cst.erase(it);
    }
//    cout << node << ":- \n";
//    for(int u : cst)
//    {
//        cout << u << " ";
//    }
//    cout << "\n";
    sol[node]=(int)cst.size();
    return cst;
}
int main()
{
    cin >> n >>m >> k;
    int x , y , one , nd , lcc;
    vector<pair<int,int> > edgs;
    for(int i  = 0 ;  i < n-1 ; i++)
    {
        cin >>x>>y ;
        edgs.push_back({min(x,y),max(x,y)});
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    preprocess(1);
    for(int i = 0 ; i < m ; i++)
    {
        cin >> y;
        lcc=-1;
        for(int j = 0 ; j < y ; j++)
        {
            cin >> x ;
            st[x].insert(i+1);
            if(lcc==-1)lcc=x;
            else lcc=lca(lcc , x);
        }
        en[lcc].insert(i+1);
    }
    smalltolarge(1 , 1);
    vector<int> finlans;
    int idx=1;
    for( auto p : edgs)
    {
        x = (level[p.first] > level[p.second]) ? p.first : p.second ;
        if(sol[x] >= k )finlans.push_back(idx);
        idx++;
    }
    cout << finlans.size() << "\n";
    for(int u : finlans)
    {
        cout << u << " ";
    }
    cout << "\n";
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:95:17: warning: unused variable 'one' [-Wunused-variable]
   95 |     int x , y , one , nd , lcc;
      |                 ^~~
railway.cpp:95:23: warning: unused variable 'nd' [-Wunused-variable]
   95 |     int x , y , one , nd , lcc;
      |                       ^~

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