oj.uz

Submission #125749

# Submission time Handle Problem Language Result Execution time Memory
125749 2019-07-06T10:03:23 Z AngusRitossa Space Pirate (JOI14_space_pirate) C++14
47 / 100
 1654 ms 91392 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
	#define D(x...) printf(x)
#else
	#define D(x...)
#endif
typedef long long ll;
int n, a[3010], ans[3010];
int canreach[3010][3010], at[3010][3010];
int from[3010][3030], fromsz[3010];
void dfs(int i, int j, int dis = 1)
{
	if (canreach[i][j]) return;
	canreach[i][j] = dis;
	from[i][fromsz[i]++] = j;
	dfs(i, a[j], dis+1);
}
ll k;
int main()
{
	scanf("%d%lld", &n, &k);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) dfs(i, i);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (canreach[1][i])
			{
				if (i == j) ans[i]++;
				else if (canreach[j][i])
				{
					ll dis = k-canreach[1][i]+1;
					dis %= canreach[j][i];
					int endpoint = i;
					if (dis > 0) endpoint = from[j][dis-1];
					ans[endpoint]++;
				}
				else at[j][canreach[1][i]]++;
			}
			else at[1][0]++;
		}
	}
	
	for (int i = 1; i <= n; i++)
	{
		int cyclestart = a[from[i][fromsz[i]-1]];
		int loc = -1;
		for (int j = 0; j < fromsz[i]; j++)
		{
			if (from[i][j] == cyclestart) { loc = j; break; }
		}
		assert(loc != -1);
		int sz = fromsz[i]-loc;
		ll dis2 = k-loc;
		int dis = dis2%sz;
		for (int j = 0; j <= n; j++)
		{
			if (!at[i][j]) continue;
			int d = dis-(ll)j;
			d += n*sz;
			d %= sz;
			ans[from[i][d+loc]] += at[i][j];
		}
	}

	for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
}

Compilation message

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~
space_pirate.cpp:23:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
                               ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1528 KB Output is correct
5 Correct 3 ms 1656 KB Output is correct
6 Correct 3 ms 1528 KB Output is correct
7 Correct 4 ms 1656 KB Output is correct
8 Correct 3 ms 1656 KB Output is correct
9 Correct 3 ms 1656 KB Output is correct
10 Correct 3 ms 1528 KB Output is correct
11 Correct 3 ms 1528 KB Output is correct
12 Correct 3 ms 1144 KB Output is correct
13 Correct 3 ms 1656 KB Output is correct
14 Correct 3 ms 1528 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1528 KB Output is correct
5 Correct 3 ms 1656 KB Output is correct
6 Correct 3 ms 1528 KB Output is correct
7 Correct 4 ms 1656 KB Output is correct
8 Correct 3 ms 1656 KB Output is correct
9 Correct 3 ms 1656 KB Output is correct
10 Correct 3 ms 1528 KB Output is correct
11 Correct 3 ms 1528 KB Output is correct
12 Correct 3 ms 1144 KB Output is correct
13 Correct 3 ms 1656 KB Output is correct
14 Correct 3 ms 1528 KB Output is correct
15 Correct 132 ms 60792 KB Output is correct
16 Correct 108 ms 55160 KB Output is correct
17 Correct 168 ms 61304 KB Output is correct
18 Correct 1654 ms 85500 KB Output is correct
19 Correct 801 ms 85100 KB Output is correct
20 Correct 927 ms 79224 KB Output is correct
21 Correct 1228 ms 91392 KB Output is correct
22 Correct 519 ms 80760 KB Output is correct
23 Correct 1192 ms 90488 KB Output is correct
24 Correct 472 ms 81316 KB Output is correct
25 Correct 101 ms 54776 KB Output is correct
26 Correct 1638 ms 71332 KB Output is correct
27 Correct 499 ms 74552 KB Output is correct
28 Correct 644 ms 75180 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 376 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1528 KB Output is correct
5 Correct 3 ms 1656 KB Output is correct
6 Correct 3 ms 1528 KB Output is correct
7 Correct 4 ms 1656 KB Output is correct
8 Correct 3 ms 1656 KB Output is correct
9 Correct 3 ms 1656 KB Output is correct
10 Correct 3 ms 1528 KB Output is correct
11 Correct 3 ms 1528 KB Output is correct
12 Correct 3 ms 1144 KB Output is correct
13 Correct 3 ms 1656 KB Output is correct
14 Correct 3 ms 1528 KB Output is correct
15 Correct 132 ms 60792 KB Output is correct
16 Correct 108 ms 55160 KB Output is correct
17 Correct 168 ms 61304 KB Output is correct
18 Correct 1654 ms 85500 KB Output is correct
19 Correct 801 ms 85100 KB Output is correct
20 Correct 927 ms 79224 KB Output is correct
21 Correct 1228 ms 91392 KB Output is correct
22 Correct 519 ms 80760 KB Output is correct
23 Correct 1192 ms 90488 KB Output is correct
24 Correct 472 ms 81316 KB Output is correct
25 Correct 101 ms 54776 KB Output is correct
26 Correct 1638 ms 71332 KB Output is correct
27 Correct 499 ms 74552 KB Output is correct
28 Correct 644 ms 75180 KB Output is correct
29 Execution timed out 3 ms 376 KB Time limit exceeded (wall clock)
30 Halted 0 ms 0 KB -