oj.uz

Submission #348538

# Submission time Handle Problem Language Result Execution time Memory
348538 2021-01-15T06:50:35 Z arnold518 Link (CEOI06_link) C++14
0 / 100
 301 ms 64108 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;
	assert(N<=30);
	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 Runtime error 24 ms 24300 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Runtime error 23 ms 24300 KB Execution killed with signal 6 (could be triggered by violating memory limits)
3 Runtime error 23 ms 24428 KB Execution killed with signal 6 (could be triggered by violating memory limits)
4 Runtime error 24 ms 24556 KB Execution killed with signal 6 (could be triggered by violating memory limits)
5 Runtime error 26 ms 24684 KB Execution killed with signal 6 (could be triggered by violating memory limits)
6 Runtime error 35 ms 26732 KB Execution killed with signal 6 (could be triggered by violating memory limits)
7 Runtime error 41 ms 28268 KB Execution killed with signal 6 (could be triggered by violating memory limits)
8 Runtime error 50 ms 29804 KB Execution killed with signal 6 (could be triggered by violating memory limits)
9 Runtime error 65 ms 32236 KB Execution killed with signal 6 (could be triggered by violating memory limits)
10 Runtime error 62 ms 32236 KB Execution killed with signal 6 (could be triggered by violating memory limits)
11 Runtime error 88 ms 36204 KB Execution killed with signal 6 (could be triggered by violating memory limits)
12 Runtime error 116 ms 40172 KB Execution killed with signal 6 (could be triggered by violating memory limits)
13 Runtime error 144 ms 44228 KB Execution killed with signal 6 (could be triggered by violating memory limits)
14 Runtime error 173 ms 48108 KB Execution killed with signal 6 (could be triggered by violating memory limits)
15 Runtime error 210 ms 52076 KB Execution killed with signal 6 (could be triggered by violating memory limits)
16 Runtime error 233 ms 55916 KB Execution killed with signal 6 (could be triggered by violating memory limits)
17 Runtime error 273 ms 60140 KB Execution killed with signal 6 (could be triggered by violating memory limits)
18 Runtime error 293 ms 63852 KB Execution killed with signal 6 (could be triggered by violating memory limits)
19 Runtime error 301 ms 63852 KB Execution killed with signal 6 (could be triggered by violating memory limits)
20 Runtime error 295 ms 63852 KB Execution killed with signal 6 (could be triggered by violating memory limits)
21 Runtime error 300 ms 63852 KB Execution killed with signal 6 (could be triggered by violating memory limits)
22 Runtime error 294 ms 63852 KB Execution killed with signal 6 (could be triggered by violating memory limits)
23 Runtime error 300 ms 63852 KB Execution killed with signal 6 (could be triggered by violating memory limits)
24 Runtime error 287 ms 64108 KB Execution killed with signal 6 (could be triggered by violating memory limits)
25 Runtime error 288 ms 63980 KB Execution killed with signal 6 (could be triggered by violating memory limits)