Submission #942057

#	Time	Username	Problem	Language	Result	Execution time	Memory
942057		dshfjka	Railway (BOI17_railway)	C++14	100 / 100	240 ms	62884 KiB

railway

#include <bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
const LL N=1e5;
LL arr[N+5],res;
vector<LL>dep[N+5],akhir;
LL n,m,k;
vector<pair<LL,LL>>adj[N+5];
bool visited[N+5];
struct disjoint_set{
	LL parent[N+5],sz[N+5],ans[N+5];
	bool vis[N+5];
	map<LL,LL>mp[N+5];
	disjoint_set(){
		for(LL a=1;a<=N;a++)parent[a]=a;
		for(LL a=1;a<=N;a++)sz[a]=1;
	}
	LL root(LL x)
	{
	//	printf("x=%lld\n");
		if(parent[x]==x)return x;
		return parent[x]=root(parent[x]);
	}
	void merge(LL x, LL y)
	{
	//	printf("MERGE(%lld, %lld)\n",x,y);
		LL px=root(x),py=root(y);
	//	printf("%lld %lld\n",px,py);
		if(px==py)return;
	//	printf("HEE\n");
		if(sz[px]<sz[py])swap(px,py);
		sz[px]+=sz[py];
		parent[py]=px;
	//	printf("DOR\n");
		for(pair<LL,LL> a:mp[py])
		{
		//	printf("%lld %lld %lld\n",py,a.fi,a.se);
		//	printf("dep[%lld][%lld]=%lld\n",px,a.fi,mp[px][a.fi]);
			if(!mp[px][a.fi])
			{
				ans[px]++;
			}
			mp[px][a.fi]+=a.se;
			if(mp[px][a.fi]==arr[a.fi])ans[px]--;
		}
	}
	
}dsu;
void dfs(LL x, LL num)
{
//	printf("%lld %lld\n",x,num);
	visited[x]=1;
	for(LL a:dep[x]){
		dsu.mp[x][a]++;
		if(arr[x]!=1)dsu.ans[x]++;
	}
	for(pair<LL,LL> a:adj[x])
	{
		if(visited[a.fi])continue;
		dfs(a.fi,a.se);
		dsu.merge(a.fi,x);
	}
//	printf("%lld %lld , dsu.ans[%lld]=%lld\n",x,num, dsu.root(x),dsu.ans[dsu.root(x)]);
//	printf("%lld : %lld\n",num,dsu.ans[dsu.root(x)]);
	if(dsu.ans[dsu.root(x)]>=k){
		akhir.push_back(num);
	}
}
int main()
{
	
	scanf("%lld %lld %lld",&n,&m,&k);
	for(LL a=1;a<n;a++)
	{
		LL x,y;
		scanf("%lld %lld",&x,&y);
		adj[x].push_back(mp(y,a));
		adj[y].push_back(mp(x,a));
	}
	for(LL a=1;a<=m;a++)
	{
		scanf("%lld",&arr[a]);
		for(LL b=1;b<=arr[a];b++)
		{
			LL x;
			scanf("%lld",&x);
			dep[x].push_back(a);
		}
	}
	dfs(1,0);
//	printf("SINI\n");
	printf("%lld\n",akhir.size());
	sort(akhir.begin(),akhir.end());
	for(LL x:akhir){
		printf("%lld ",x);
	}
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:95:13: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   95 |  printf("%lld\n",akhir.size());
      |          ~~~^    ~~~~~~~~~~~~
      |             |              |
      |             long long int  std::vector<long long int>::size_type {aka long unsigned int}
      |          %ld
railway.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%lld %lld %lld",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%lld %lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
railway.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%lld",&arr[a]);
      |   ~~~~~^~~~~~~~~~~~~~~~
railway.cpp:89:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |    scanf("%lld",&x);
      |    ~~~~~^~~~~~~~~~~

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