Submission #213600

#	Time	Username	Problem	Language	Result	Execution time	Memory
213600		MKopchev	Railway (BOI17_railway)	C++14	100 / 100	189 ms	25332 KiB

railway

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;
int n,m,k;
pair<int,int> edges[nmax];

vector<int> adj[nmax];

int SZ,want[nmax];

int in[nmax],out[nmax],t=0;

int up[20][nmax],height[nmax];

int lca(int u,int v)
{
    if(height[u]<height[v])swap(u,v);
    for(int st=19;st>=0;st--)
        if(height[u]-(1<<st)>=height[v])u=up[st][u];
    if(u==v)return u;
    for(int st=19;st>=0;st--)
        if(up[st][u]!=up[st][v])u=up[st][u],v=up[st][v];
    return up[0][u];
}

void dfs(int node,int parent)
{
    up[0][node]=parent;
    t++;
    in[node]=t;

    height[node]=height[parent]+1;

    for(auto k:adj[node])
        if(k!=parent)
            dfs(k,node);

    out[node]=t;
}

int pref[nmax];

void dfs_collect(int node,int parent)
{
    for(auto k:adj[node])
        if(k!=parent)
        {
            dfs_collect(k,node);
            pref[node]+=pref[k];
        }
}
bool cmp(int u,int v)
{
    return in[u]<in[v];
}

stack<int> active;

void add()
{
    scanf("%i",&SZ);
    for(int i=1;i<=SZ;i++)scanf("%i",&want[i]);

    sort(want+1,want+SZ+1,cmp);

    set<int> noted={};
    for(int i=1;i<=SZ;i++)noted.insert(want[i]);
    for(int i=2;i<=SZ;i++)noted.insert(lca(want[i-1],want[i]));

    SZ=0;
    for(auto k:noted)
    {
        SZ++;
        want[SZ]=k;
    }

    sort(want+1,want+SZ+1,cmp);

    while(active.size())active.pop();
    active.push(want[1]);
    for(int i=2;i<=SZ;i++)
    {
        while(lca(active.top(),want[i])!=active.top())active.pop();

        pref[want[i]]++;
        pref[active.top()]--;

        active.push(want[i]);
    }
}
int main()
{
    scanf("%i%i%i",&n,&m,&k);

    for(int i=1;i<n;i++)
    {
        scanf("%i%i",&edges[i].first,&edges[i].second);

        adj[edges[i].first].push_back(edges[i].second);
        adj[edges[i].second].push_back(edges[i].first);
    }

    dfs(1,1);

    for(int st=1;st<20;st++)
        for(int i=1;i<=n;i++)
            up[st][i]=up[st-1][up[st-1][i]];

    for(int i=1;i<=m;i++)
        add();

    dfs_collect(1,1);

    for(int i=1;i<n;i++)
    {
        if(height[edges[i].first]<height[edges[i].second])swap(edges[i].first,edges[i].second);
        in[i]=pref[edges[i].first];
    }

    vector<int> output={};
    for(int i=1;i<n;i++)
        if(in[i]>=k)output.push_back(i);

    printf("%i\n",output.size());
    for(int i=0;i<output.size();i++)
    {
        printf("%i",output[i]);
        if(i==output.size()-1)printf("\n");
        else printf(" ");
    }
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:124:32: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%i\n",output.size());
                   ~~~~~~~~~~~~~^
railway.cpp:125:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<output.size();i++)
                 ~^~~~~~~~~~~~~~
railway.cpp:128:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i==output.size()-1)printf("\n");
            ~^~~~~~~~~~~~~~~~~
railway.cpp: In function 'void add()':
railway.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&SZ);
     ~~~~~^~~~~~~~~~
railway.cpp:62:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=SZ;i++)scanf("%i",&want[i]);
                           ~~~~~^~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i",&n,&m,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~
railway.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&edges[i].first,&edges[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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