Submission #348534

#	Time	Username	Problem	Language	Result	Execution time	Memory
348534		arnold518	Link (CEOI06_link)	C++14	0 / 100	405 ms	39256 KiB

link

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;

int N, K;
int A[MAXN+10];
vector<int> adj[MAXN+10];
int deg[MAXN+10];
int col[MAXN+10];

int vis[MAXN+10], cyc[MAXN+10];

int main()
{
	scanf("%d%d", &N, &K);
	for(int i=1; i<=N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		A[u]=v;
		adj[v].push_back(u);
		deg[v]++;
	}

	for(int i=1; i<=N; i++)
	{
		if(vis[i]) continue;

		int now=i;	
		vector<int> S;
		while(1)
		{
			vis[now]=i;
			S.push_back(now);
			if(vis[A[now]])
			{	
				if(vis[A[now]]!=i) break;
				while(!S.empty() && S.back()!=A[now])
				{
					cyc[S.back()]=i;
					S.pop_back();
				}
				cyc[A[now]]=i;
				break;
			}
			now=A[now];
		}
	}
	//for(int i=1; i<=N; i++) printf("%d ", cyc[i]); printf("\n");

	queue<int> Q;

	int now=1;
	for(int i=1; i<=K+1; i++)
	{
		if(col[now]==0)
		{
			deg[A[now]]--;
		}
		col[now]=1;
		now=A[now];
	}

	for(int i=1; i<=N; i++) if(deg[i]==0 && col[i]==0 && !cyc[i]) Q.push(i);

	int ans=0;
	while(!Q.empty())
	{
		int now=Q.front(); Q.pop();
		if(deg[now]!=0) continue;
		if(col[now]) continue;
		if(cyc[now]) continue;
		ans++;

		int u=now;
		for(int i=1; i<=K; i++)
		{
			if(col[u]==0)
			{
				deg[A[u]]--;
				if(!cyc[A[u]] && deg[A[u]]==0) Q.push(A[u]);
			}
			col[u]=1;
			u=A[u];
		}
	}
	//for(int i=1; i<=N; i++) printf("%d ", col[i]); printf(" : %d\n", ans);

	for(int i=1; i<=N; i++) if(deg[i]==0 && col[i]==0) Q.push(i);
	while(!Q.empty())
	{
		int now=Q.front(); Q.pop();
		if(deg[now]!=0) continue;
		if(col[now]) continue;
		ans++;

		int u=now;
		for(int i=1; i<=K; i++)
		{
			if(col[u]==0)
			{
				deg[A[u]]--;
				if(deg[A[u]]==0) Q.push(A[u]);
			}
			col[u]=1;
			u=A[u];
		}
	}
	//for(int i=1; i<=N; i++) printf("%d ", col[i]); printf(" : %d\n", ans);

	for(int i=1; i<=N; i++) if(col[i]==0) Q.push(i);
	while(!Q.empty())
	{
		int now=Q.front(); Q.pop();
		if(col[now]) continue;
		ans++;

		int u=now;
		for(int i=1; i<=K; i++)
		{
			col[u]=1;
			u=A[u];
		}
	}
	//for(int i=1; i<=N; i++) printf("%d ", col[i]); printf(" : %d\n", ans);

	for(int i=1; i<=N; i++) assert(col[i]);
	printf("%d\n", ans);
}

Compilation message (stderr)

link.cpp: In function 'int main()':
link.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
link.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100