oj.uz

Submission #348536

# Submission time Handle Problem Language Result Execution time Memory
348536 2021-01-15T06:48:25 Z arnold518 Link (CEOI06_link) C++14
0 / 100
 1500 ms 33772 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 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;
	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

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

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 12140 KB Output isn't correct
2 Execution timed out 1572 ms 12140 KB Time limit exceeded
3 Incorrect 10 ms 12140 KB Output isn't correct
4 Execution timed out 1594 ms 12140 KB Time limit exceeded
5 Incorrect 14 ms 12268 KB Output isn't correct
6 Execution timed out 1581 ms 13420 KB Time limit exceeded
7 Execution timed out 1583 ms 14188 KB Time limit exceeded
8 Execution timed out 1585 ms 15104 KB Time limit exceeded
9 Incorrect 48 ms 16364 KB Output isn't correct
10 Incorrect 44 ms 16364 KB Output isn't correct
11 Execution timed out 1586 ms 18540 KB Time limit exceeded
12 Incorrect 110 ms 20716 KB Output isn't correct
13 Execution timed out 1581 ms 22892 KB Time limit exceeded
14 Incorrect 173 ms 25196 KB Output isn't correct
15 Execution timed out 1590 ms 27116 KB Time limit exceeded
16 Incorrect 236 ms 29412 KB Output isn't correct
17 Execution timed out 1592 ms 31468 KB Time limit exceeded
18 Incorrect 295 ms 33644 KB Output isn't correct
19 Incorrect 305 ms 33644 KB Output isn't correct
20 Incorrect 298 ms 33644 KB Output isn't correct
21 Incorrect 293 ms 33644 KB Output isn't correct
22 Incorrect 293 ms 33772 KB Output isn't correct
23 Execution timed out 1584 ms 33644 KB Time limit exceeded
24 Incorrect 300 ms 33644 KB Output isn't correct
25 Incorrect 298 ms 33772 KB Output isn't correct