Submission #129482

#	Time	Username	Problem	Language	Result	Execution time	Memory
129482		davitmarg	Railway (BOI17_railway)	C++17	0 / 100	1038 ms	294108 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,p[200005],cnt[50004];
vector<int> g[200005],ans,s[200005],v[200005];
vector<pair<int,int>> t;

void dfs(int v,int p=0)
{
    for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
        if(to==p)
			continue;
        dfs(to,v);
	}
    if(p)
		t.PB(MP(v,p));
}

void dsu(int a,int b)
{
	int id=num[MP(a,b)];
	a=p[a];
	b=p[b];
    if(s[a].size()<s[b].size())
		swap(a,b);
    map<int,int> c;
    while(!s[b].empty())
	{
        c[s[b].back()]++;
        s[a].PB(s[b].back());
        s[b].pop_back();
	}
    while(!v[b].empty())
	{
        v[a].PB(v[b].back());
        p[v[b].back()]=a;
        v[b].pop_back();
	}
	int x=0;
    for(auto it=c.begin();it!=c.end();++it)
	{
        if(cnt[it->first]>it->second)
            x++;
	}
    if(x>=k)
        ans.PB(id);
}

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<=n;i++)
	{
		p[i]=i;
        v[i].PB(i);
	}

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


/*

2 2 0
1 2
1 1
1 2

*/

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:103:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<t.size();i++)
                 ~^~~~~~~~~
railway.cpp:106:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ans.size();i++)
                 ~^~~~~~~~~~~
railway.cpp:79: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:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&c);
   ~~~~~^~~~~~~~~
railway.cpp:98:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&v);
    ~~~~~^~~~~~~~~

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