Submission #213590

#	Time	Username	Problem	Language	Result	Execution time	Memory
213590		MKopchev	Railway (BOI17_railway)	C++14	23 / 100	1100 ms	15096 KiB

railway

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

vector<int> adj[nmax];

int SZ,want[nmax];

int in[nmax];

int current[nmax];

void dfs(int node,int parent)
{
    for(auto k:adj[node])
        if(k!=parent)
        {
            dfs(k,node);
            current[node]+=current[k];
        }
}

bool proper(int SZ_a,int SZ_b)
{
    if(SZ_a==SZ&&SZ_b==SZ)return 0;
    if(SZ_a==0||SZ_b==0)return 0;
    return 1;
}
void add()
{
    scanf("%i",&SZ);
    for(int i=1;i<=SZ;i++)scanf("%i",&want[i]);

    if(SZ<BIG)
    {
        return;
    }

    for(int i=1;i<=SZ;i++)current[want[i]]=1;

    dfs(1,0);

    //for(int i=1;i<=n;i++)cout<<current[i]<<" ";cout<<endl;

    for(int i=1;i<n;i++)
        if(proper(current[edges[i].first],current[edges[i].second]))
        {
            //cout<<"add "<<edges[i].first<<" "<<edges[i].second<<endl;
            in[i]++;
        }

    for(int i=1;i<=n;i++)current[i]=0;
}
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);
    }
    for(int i=1;i<=m;i++)
        add();

    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:74: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:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<output.size();i++)
                 ~^~~~~~~~~~~~~~
railway.cpp:78: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:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&SZ);
     ~~~~~^~~~~~~~~~
railway.cpp:34: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:58: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:62: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: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25