oj.uz

답안 #51732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51732 2018-06-20T13:52:03 Z Costin Andrei Oncescu(#1294) 우주 해적 (JOI14_space_pirate) C++11
0 / 100
 2000 ms 1528 KB 
#include<bits/stdc++.h>

using namespace std;

int nr, N, repCyc[3009], lin[3009], col[3009], p[3009], ans[3009];
long long K;
vector < int > cyc[3009];

int aft[3009][3009], d[3009][3009];
bool can[3009][3009];
void init ()
{
    for (int i=1; i<=N; i++)
    {
        int j = p[i], oldJ = i;
        can[i][i] = 1, d[i][i] = 0, aft[i][0] = i;
        while (can[i][j] == 0)
            can[i][j] = 1, d[i][j] = d[i][oldJ] + 1,
            aft[i][d[i][j]] = j, oldJ = p[oldJ], j = p[j];
        repCyc[i] = j;
        if (lin[j] == 0)
        {
            lin[j] = ++nr, col[j] = 0;
            cyc[nr].push_back (j);
            int k = p[j];
            while (k != j)
                col[k] = cyc[nr].size (), lin[k] = nr,
                cyc[nr].push_back (k), k = p[k];
        }
    }
}

int standardJump (int i, long long K)
{
    if (lin[i] > 0)
    {
        int sz = cyc[lin[i]].size (), pos = ((col[i] + K) % sz);
        return cyc[lin[i]][pos];
    }
    int j = repCyc[i], sz = cyc[lin[j]].size (), pos = col[j];
    if (K <= d[i][j]) return aft[i][K];
    K -= d[i][j], K %= sz, pos = (pos + K) % sz;
    return cyc[lin[j]][pos];
}

int brute (int a, int b)
{
    int oldP = p[a], curr = 1;
    p[a] = b;
    long long steps = K;
    while (steps --)
        curr = p[curr];
    p[a] = oldP;
    return curr;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %lld", &N, &K);
for (int i=1; i<=N; i++)
    scanf ("%d", &p[i]);
init ();
int standardEnd = standardJump (1, K);
for (int a=1; a<=N; a++)
    for (int b=1; b<=N; b++)
    {
        int curr = -1;
        if (!can[1][a]) curr = standardEnd;
        else
        if (!can[1][b])
        {
            if (can[b][1])
            {
                int sz = d[b][1] + 1 + d[1][a], k = (K % sz);
                if (k <= d[1][a]) curr = aft[1][k];
                else curr = aft[b][k - 1 - d[1][a]];
            }
            else
            curr = standardJump (b, K - d[1][a] - 1);
        }
        else
        if (d[1][a] >= d[1][b])
        {
            int sz = d[1][a] - d[1][b] + 1, k = ((K - d[1][b]) % sz);
            curr = standardJump (b, k);
        }
        else
        if (lin[a] == 0)
            curr = standardJump (b, K - d[1][a] - 1);
        else
        {
            assert (lin[b] == lin[a]);
            if (lin[1] == 0)
            {
                int j = repCyc[1], sz = ((int) cyc[lin[a]].size ()) - (d[1][b] - d[1][a] - 1), k = (K - d[1][j]) % sz;
                if (k <= d[j][a]) curr = standardJump (j, k);
                else curr = standardJump (b, k - d[j][a] - 1);
            }
            else
            {
                int sz = ((int) cyc[lin[a]].size ()) - (d[1][b] - d[1][a] - 1), k = (K % sz);
                if (k <= d[1][a]) curr = standardJump (1, k);
                else curr = standardJump (b, k - d[1][a] - 1);
            }
        }
        curr = brute (a, b);
/*        printf ("%d%c", curr, " \n"[b == N]);
        if (curr != brute (a, b))
        {
            printf ("WA (%d %d) %d instead of %d\n", a, b, curr, brute (a, b));
            return 0;
        }*/
        ans[curr] ++;
    }
for (int i=1; i<=N; i++)
    printf ("%d\n", ans[i]);
return 0;
}

Compilation message

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2078 ms 1528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2078 ms 1528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5 ms 1528 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2078 ms 1528 KB Time limit exceeded
2 Halted 0 ms 0 KB -