Submission #311554

#	Time	Username	Problem	Language	Result	Execution time	Memory
311554		hoangtung_pro	Railway (BOI17_railway)	C++14	100 / 100	278 ms	48400 KiB

railway

#include<bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define bit(s, i) (s & (1<<i))

using namespace std;

const int maxn = 1e5 + 5;
const int mod = 1e9+7;

typedef long long ll;
typedef pair < int, int > ii;

int n, m, k;

vector < ii > adj[maxn];
vector < int > child[maxn];
bool vis[maxn];

int h[maxn];
int id[maxn];
int p[maxn][20];

void ht(int v)
{
    vis[v] = true;
    for(ii u : adj[v])
    if(!vis[u.fi])
    {
        p[u.fi][0] = v;
        h[u.fi] = h[v] + 1;
        id[u.fi] = u.se;
        child[v].pb(u.fi);
        ht(u.fi);
    }
}

int LCA(int u, int v)
{
    if(h[u] > h[v]) swap(u, v);

    for(int i=18;i>=0;--i) if( h[p[v][i]] >= h[u] ) v = p[v][i];

    if(u == v) return u;

    for(int i=18;i>=0;--i)
    {
        if( p[u][i] != p[v][i] )
        {
            u = p[u][i];
            v = p[v][i];
        }
    }
    return p[u][0];
}

set < int > query[maxn];
vector < int > requery[maxn], res;

void cal(int v)
{
    for(int u : child[v])
    {
        cal(u);
        if(query[u].size() > query[v].size()) swap(query[u], query[v]);
        for(int x : query[u]) query[v].insert(x);
    }
//    cout << v << endl;
//    for(int x : query[v]) cout << x <<' ';
//    cout << endl;
    for(int x : requery[v]) query[v].erase(x);
    if(query[v].size() >= k) res.pb(id[v]);
//    for(int x : query[v]) cout << x <<' ';
//    cout << endl;
//    cout << endl;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen(".inp","r",stdin);
    //freopen(".out","w",stdout);

    cin >> n >> m >> k;
    for(int i=1;i<n;++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].pb( ii(v, i) );
        adj[v].pb( ii(u, i) );
    }

    h[0] = -1;
    ht(1);

    for(int j=1;j<=18;++j)
    for(int i=1;i<=n;++i)  if((1<<j) <= h[i]) p[i][j] = p[p[i][j-1]][j-1];

    for(int i=1, s;i<=m;++i)
    {
        cin >> s;
        int ro;
        for(int j=1, x;j<=s;++j)
        {
            cin >> x;
            query[x].insert(i);
            if(j == 1) ro = x;
            else ro = LCA(ro, x);
        }
        requery[ro].pb(i);
    }

    cal(1);
    sort(res.begin(), res.end());

    cout << res.size() << endl;
    for(int x : res) cout << x << ' ';
}

Compilation message (stderr)

railway.cpp: In function 'void cal(int)':
railway.cpp:75:24: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |     if(query[v].size() >= k) res.pb(id[v]);
      |        ~~~~~~~~~~~~~~~~^~~~

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