Submission #129603

#	Time	Username	Problem	Language	Result	Execution time	Memory
129603		davitmarg	Railway (BOI17_railway)	C++17	100 / 100	449 ms	56176 KiB

railway

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

map<pair<int,int>,int> num;
int n,k,m,cnt[50004],f[200005],mns;
vector<int> g[200005],ans;
vector<pair<int,int>> t;
map<int,int> s[200005];


void dfs(int v,int p=0)
{
    for(auto it=s[v].begin();it!=s[v].end();++it)
        f[v]+=(it->second==cnt[it->first]);
    for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
        if(to==p)
			continue;
		dfs(to,v);
        if(s[v].size()<s[to].size())
		{
            swap(s[v],s[to]);
            swap(f[v],f[to]);
		}
        for(auto it=s[to].begin();it!=s[to].end();++it)
		{
            s[v][it->first]+=it->second;
			if(s[v][it->first]==cnt[it->first])
				f[v]++;
		}
	}
    if(s[v].size()-f[v]>=k)
		ans.PB(num[MP(v,p)]);
}

int main()
{
    cin >> n >> m >> k;
    for(int i=1;i<=n-1;i++)
	{
        int a,b;
        scanf("%d%d",&a,&b);
        g[a].PB(b);
        g[b].PB(a);
        num[MP(a,b)]=num[MP(b,a)]=i;
	}

    for(int i=1;i<=m;i++)
	{
		int c,v;
		scanf("%d",&c);
        cnt[i]=c;
        while(c--)
		{
			scanf("%d",&v);
            s[v][i]++;
		}
	}
    dfs(1);
    cout<<ans.size()<<endl;
    sort(all(ans));
    for(int i=0;i<ans.size();i++)
        printf("%d ",ans[i]);
    cout<<endl;
	return 0;
}


/*

2 2 2
1 2
2 1 2
2 2 1


*/

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
railway.cpp:54:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(s[v].size()-f[v]>=k)
        ~~~~~~~~~~~~~~~~^~~
railway.cpp: In function 'int main()':
railway.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ans.size();i++)
                 ~^~~~~~~~~~~
railway.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~
railway.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&c);
   ~~~~~^~~~~~~~~
railway.cpp:77:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&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