제출 #129596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
129596		davitmarg	Railway (BOI17_railway)	C++17	0 / 100	338 ms	54004 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],mns;
vector<int> g[200005],ans;
vector<pair<int,int>> t;
map<int,int> s[200005];


void dfs(int v,int p=0)
{
	int full=0;
    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]);
        for(auto it=s[to].begin();it!=s[to].end();++it)
		{
			if(s[v][it->first]+it->second==cnt[it->first])
				full++;
            s[v][it->first]+=it->second;
		}
	}
    if(s[v].size()-mns-full>=k)
		ans.PB(num[MP(v,p)]);
	mns+=full;
}

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);
			if(cnt[i]==1)
			{
                i--;
                m--;
				break;
			}
            s[v][i]++;
		}
	}
    dfs(1);
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)
        printf("%d ",ans[i]);
    cout<<endl;
	return 0;
}


/*


*/

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:35:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
railway.cpp:50:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(s[v].size()-mns-full>=k)
        ~~~~~~~~~~~~~~~~~~~~^~~
railway.cpp: In function 'int main()':
railway.cpp:86:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ans.size();i++)
                 ~^~~~~~~~~~~
railway.cpp:61: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:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&c);
   ~~~~~^~~~~~~~~
railway.cpp:74: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