Submission #348537

#	Time	Username	Problem	Language	Result	Execution time	Memory
348537		arnold518	Link (CEOI06_link)	C++14	0 / 100	300 ms	64136 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 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]++;
	}

	int ans=987654321;
	assert(N<=20);
	for(int i=0; i<(1<<N); i++)
	{
		for(int j=1; j<=N; j++) col[j]=0;
		int now=1;
		for(int p=1; p<=K+1; p++)
		{
			col[now]=1;
			now=A[now];
		}

		for(int j=0; j<N; j++)
		{
			if(i&(1<<j))
			{
				now=j+1;
				for(int p=1; p<=K; p++)
				{
					col[now]=1;
					now=A[now];
				}
			}
		}
		bool flag=true;
		for(int j=1; j<=N; j++) if(!col[j]) flag=false;
		if(flag) ans=min(ans, __builtin_popcount(i));
	}

	printf("%d\n", ans);
}

Compilation message (stderr)

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

• Subtask 1: 0 / 100