oj.uz

Submission #348534

# Submission time Handle Problem Language Result Execution time Memory
348534 2021-01-15T06:39:10 Z arnold518 Link (CEOI06_link) C++14
0 / 100
 405 ms 39256 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12140 KB Output isn't correct
2 Incorrect 8 ms 12140 KB Output isn't correct
3 Incorrect 9 ms 12140 KB Output isn't correct
4 Incorrect 9 ms 12268 KB Output isn't correct
5 Incorrect 10 ms 12396 KB Output isn't correct
6 Incorrect 21 ms 13676 KB Output isn't correct
7 Incorrect 30 ms 14828 KB Output isn't correct
8 Incorrect 39 ms 15852 KB Output isn't correct
9 Incorrect 54 ms 17376 KB Output isn't correct
10 Incorrect 54 ms 17424 KB Output isn't correct
11 Incorrect 97 ms 20248 KB Output isn't correct
12 Incorrect 122 ms 22764 KB Output isn't correct
13 Incorrect 164 ms 25308 KB Output isn't correct
14 Incorrect 209 ms 28324 KB Output isn't correct
15 Incorrect 253 ms 30460 KB Output isn't correct
16 Incorrect 293 ms 33628 KB Output isn't correct
17 Incorrect 344 ms 35764 KB Output isn't correct
18 Incorrect 390 ms 38992 KB Output isn't correct
19 Incorrect 388 ms 38880 KB Output isn't correct
20 Incorrect 399 ms 38476 KB Output isn't correct
21 Incorrect 405 ms 38668 KB Output isn't correct
22 Incorrect 402 ms 38676 KB Output isn't correct
23 Incorrect 389 ms 39256 KB Output isn't correct
24 Incorrect 390 ms 38640 KB Output isn't correct
25 Incorrect 391 ms 38608 KB Output isn't correct