Submission #1103258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103258		alexdd	Railway (BOI17_railway)	C++17	100 / 100	89 ms	24268 KiB

railway

#include <bits/stdc++.h>
using namespace std;
int n,m,k;
vector<pair<int,int>> con[100005];
pair<int,int> parent[100005];
int anc[100005][17];
int tin[100005],tout[100005],timer;
void dfs(int nod)
{
    tin[nod] = ++timer;
    for(auto [adj,id]:con[nod])
    {
        if(adj==anc[nod][0])
            continue;
        anc[adj][0] = nod;
        parent[adj] = {nod,id};
        dfs(adj);
    }
    tout[nod] = ++timer;
}
bool isanc(int x, int y)
{
    return (tin[x]<=tin[y] && tout[x]>=tout[y]);
}
int lca(int x, int y)
{
    if(isanc(x,y))
        return x;
    if(isanc(y,x))
        return y;
    for(int p=16;p>=0;p--)
        if(!isanc(anc[x][p],y))
            x = anc[x][p];
    return anc[x][0];
}
bool cmp(int x, int y)
{
    return tin[x] < tin[y];
}
int cnt[100005], auxcnt[100005];
void baga(int x, int y)
{
    assert(isanc(x,y));
    /*while(y!=x)
    {
        //cerr<<y<<" zzz\n";
        cnt[parent[y].second]++;
        y = parent[y].first;
    }*/
    auxcnt[y]++;
    auxcnt[x]--;
}
void dfs2(int nod)
{
    for(auto [adj,id]:con[nod])
    {
        if(adj==parent[nod].first)
            continue;
        dfs2(adj);
        cnt[id] = auxcnt[adj];
        auxcnt[nod] += auxcnt[adj];
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>k;
    int u,v;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        con[u].push_back({v,i});
        con[v].push_back({u,i});
    }
    anc[1][0]=1;
    dfs(1);
    for(int p=1;p<17;p++)
        for(int i=1;i<=n;i++)
            anc[i][p] = anc[anc[i][p-1]][p-1];
    while(m--)
    {
        int nr;
        cin>>nr;
        vector<int> v(nr);
        for(int i=0;i<nr;i++)
            cin>>v[i];
        sort(v.begin(),v.end(),cmp);
        map<int,int> ap;
        vector<int> newv;
        for(int i=0;i<nr;i++)
        {
            if(!ap[v[i]])
            {
                newv.push_back(v[i]);
                ap[v[i]]=1;
            }
        }
        for(int i=0;i+1<nr;i++)
        {
            int x = lca(v[i],v[i+1]);
            //cerr<<v[i]<<" "<<v[i+1]<<"  lca "<<x<<"\n";
            if(!ap[x])
            {
                newv.push_back(x);
                ap[x]=1;
            }
        }
        sort(newv.begin(),newv.end(),cmp);
        vector<int> aux;
        aux.push_back(newv[0]);
        for(int i=1;i<newv.size();i++)
        {
            int x = newv[i];
            while(!aux.empty() && !isanc(aux.back(),x))
            {
                aux.pop_back();
            }
            baga(aux.back(),x);
            aux.push_back(x);
        }
    }
    dfs2(1);
    vector<int> sol;
    for(int i=1;i<n;i++)
        if(cnt[i]>=k)
            sol.push_back(i);
    cout<<(int)sol.size()<<"\n";
    for(int x:sol)
        cout<<x<<" ";
    return 0;
}

Compilation message (stderr)

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