oj.uz

Submission #348539

# Submission time Handle Problem Language Result Execution time Memory
348539 2021-01-15T07:09:10 Z arnold518 Link (CEOI06_link) C++14
0 / 100
 564 ms 45400 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;

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

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

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12140 KB Output isn't correct
2 Incorrect 8 ms 12268 KB Output isn't correct
3 Incorrect 8 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 22 ms 13932 KB Output isn't correct
7 Incorrect 35 ms 15340 KB Output isn't correct
8 Incorrect 51 ms 16892 KB Output isn't correct
9 Incorrect 70 ms 20068 KB Output isn't correct
10 Incorrect 75 ms 18320 KB Output isn't correct
11 Incorrect 107 ms 22168 KB Output isn't correct
12 Incorrect 176 ms 24292 KB Output isn't correct
13 Incorrect 222 ms 29552 KB Output isn't correct
14 Incorrect 308 ms 30756 KB Output isn't correct
15 Incorrect 308 ms 34296 KB Output isn't correct
16 Incorrect 440 ms 36188 KB Output isn't correct
17 Incorrect 440 ms 40244 KB Output isn't correct
18 Incorrect 564 ms 43848 KB Output isn't correct
19 Incorrect 546 ms 42332 KB Output isn't correct
20 Incorrect 498 ms 42960 KB Output isn't correct
21 Incorrect 504 ms 45168 KB Output isn't correct
22 Incorrect 524 ms 43824 KB Output isn't correct
23 Incorrect 559 ms 45400 KB Output isn't correct
24 Incorrect 507 ms 43380 KB Output isn't correct
25 Incorrect 512 ms 42964 KB Output isn't correct