Submission #348539

#	Time	Username	Problem	Language	Result	Execution time	Memory
348539		arnold518	Link (CEOI06_link)	C++14	0 / 100	564 ms	45400 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;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());


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 dep[MAXN+10];

void dfs(int now, int bef, int d)
{
	dep[now]=d;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(cyc[nxt]) continue;
		dfs(nxt, now, d+1);
	}
}

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++) if(cyc[i])
	{
		dfs(i, i, 1);
	}
	//for(int i=1; i<=N; i++) printf("%d ", dep[i]); printf("\n");

	priority_queue<pii> PQ;
	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]) PQ.push({dep[i], i});

	int ans=0;
	while(!PQ.empty())
	{
		int now=PQ.top().second; PQ.pop();
		if(deg[now]!=0) continue;
		if(col[now]) continue;
		if(cyc[now]) continue;
		ans++;
		//printf("%d\n", now);

		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 && !col[A[u]]) PQ.push({dep[A[u]], 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 && !col[A[u]]) 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:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
link.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100