oj.uz

Submission #348533

# Submission time Handle Problem Language Result Execution time Memory
348533 2021-01-15T06:37:23 Z arnold518 Link (CEOI06_link) C++14
0 / 100
 419 ms 45912 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++)
		{
			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++) 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 9 ms 12160 KB Output isn't correct
3 Incorrect 9 ms 12172 KB Output isn't correct
4 Incorrect 10 ms 12268 KB Output isn't correct
5 Incorrect 10 ms 12396 KB Output isn't correct
6 Incorrect 21 ms 14060 KB Output isn't correct
7 Incorrect 30 ms 15340 KB Output isn't correct
8 Incorrect 39 ms 16620 KB Output isn't correct
9 Incorrect 56 ms 18656 KB Output isn't correct
10 Incorrect 56 ms 18576 KB Output isn't correct
11 Incorrect 100 ms 22680 KB Output isn't correct
12 Incorrect 124 ms 25324 KB Output isn't correct
13 Incorrect 170 ms 28684 KB Output isn't correct
14 Incorrect 216 ms 32184 KB Output isn't correct
15 Incorrect 245 ms 35068 KB Output isn't correct
16 Incorrect 295 ms 38896 KB Output isn't correct
17 Incorrect 364 ms 41780 KB Output isn't correct
18 Incorrect 393 ms 45708 KB Output isn't correct
19 Incorrect 396 ms 45536 KB Output isn't correct
20 Incorrect 395 ms 45292 KB Output isn't correct
21 Incorrect 397 ms 45228 KB Output isn't correct
22 Incorrect 419 ms 45232 KB Output isn't correct
23 Incorrect 401 ms 45912 KB Output isn't correct
24 Incorrect 409 ms 45168 KB Output isn't correct
25 Incorrect 395 ms 45208 KB Output isn't correct