oj.uz

Submission #52307

# Submission time Handle Problem Language Result Execution time Memory
52307 2018-06-25T09:02:01 Z 강태규(#1345) Space Pirate (JOI14_space_pirate) C++11
10 / 100
 27 ms 828 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n;
llong k;
int nxt[100001];
int dist[100001];
int sz[100001];
llong ans[100001];
int main() {
	scanf("%d%lld", &n, &k);
	for (int i = 1; i <= n; ++i) {
        scanf("%d", nxt + i);
	}
	
	if (n > 100) return 0;
	for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= n; ++k) {
                dist[k] = -1;
            }
            int tp = nxt[i];
            nxt[i] = j;
            
            int cyc, s;
            for (int k = 1, m = 0; ; k = nxt[k], ++m) {
                if (dist[k] != -1) {
                   cyc = m - dist[k];
                   s = k;
                   break;
                }
                dist[k] = m;
            }
            int x = s;
            for (int d = (k - dist[s]) % cyc; d--; ) {
                x = nxt[x];
            }
            
            ++ans[x];
            nxt[i] = tp;
        }
	}
	
	for (int i = 1; i <= n; ++i) {
        printf("%lld\n", ans[i]);
	}
	return 0;
}

Compilation message

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:28: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:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", nxt + i);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 4 ms 356 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 508 KB Output is correct
6 Correct 4 ms 524 KB Output is correct
7 Correct 5 ms 648 KB Output is correct
8 Correct 4 ms 648 KB Output is correct
9 Correct 5 ms 648 KB Output is correct
10 Correct 4 ms 648 KB Output is correct
11 Correct 3 ms 648 KB Output is correct
12 Correct 5 ms 648 KB Output is correct
13 Correct 5 ms 648 KB Output is correct
14 Correct 4 ms 648 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 4 ms 356 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 508 KB Output is correct
6 Correct 4 ms 524 KB Output is correct
7 Correct 5 ms 648 KB Output is correct
8 Correct 4 ms 648 KB Output is correct
9 Correct 5 ms 648 KB Output is correct
10 Correct 4 ms 648 KB Output is correct
11 Correct 3 ms 648 KB Output is correct
12 Correct 5 ms 648 KB Output is correct
13 Correct 5 ms 648 KB Output is correct
14 Correct 4 ms 648 KB Output is correct
15 Incorrect 2 ms 648 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 4 ms 356 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 508 KB Output is correct
6 Correct 4 ms 524 KB Output is correct
7 Correct 5 ms 648 KB Output is correct
8 Correct 4 ms 648 KB Output is correct
9 Correct 5 ms 648 KB Output is correct
10 Correct 4 ms 648 KB Output is correct
11 Correct 3 ms 648 KB Output is correct
12 Correct 5 ms 648 KB Output is correct
13 Correct 5 ms 648 KB Output is correct
14 Correct 4 ms 648 KB Output is correct
15 Incorrect 2 ms 648 KB Output isn't correct
16 Halted 0 ms 0 KB -