oj.uz

Submission #132295

# Submission time Handle Problem Language Result Execution time Memory
132295 2019-07-18T16:39:59 Z egorlifar Space Pirate (JOI14_space_pirate) C++17
10 / 100
 2000 ms 135672 KB 
/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>

using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left224
#define right right224
#define next next224
#define rank rank224
#define prev prev224
#define y1 y1224
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
const string FILENAME = "input";
const int MAXN = 3028;

int n;
long long k;
int a[MAXN];
int cnt[MAXN];
int uk = 1;
int used[MAXN];
int pos[MAXN];
int jump[MAXN][65];
bool can[MAXN][MAXN];
int dist[MAXN][MAXN];

int go(int i, long long f) {
    for (int s = 62; s >= 0; s--) {
        if (f >= (1LL << s)) {
            f -= 1LL << s;
            i = jump[i][s];
        }
    }
    return i;
}


vector<int> fk[MAXN];
vector<int> sk[MAXN];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME);
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        //cout << i + 1 << ' '  << a[i] + 1 << endl;
        jump[i][0] = a[i];
    }
    int it = 0;
    pos[0] = 0;
    vector<int> g;
    int cur = 0;
    while (used[cur] != uk && it < k) {
        used[cur] = uk;
        pos[cur] = it;
        g.pb(cur);
        it++;
        cur = a[cur];
    }
    assert(sz(g) <= n);
    if (it != k) {
        int f = it - pos[cur];
        for (int jj = 0; jj < (k - it) % f; jj++) {
            cur = a[cur];
        }
    }
    for (int i = 0; i < n; i++) {
        if (used[i] != uk) {
            cnt[cur] += n;
        }
    }
    for (int k = 1; k <= 63; k++) {
        for (int i = 0; i < n; i++) {
            jump[i][k] = jump[jump[i][k - 1]][k - 1];
        }
    }
    for (int i = 0; i < n; i++) {
        int f = i;
        for (int j = 0; j < n; j++) {
            if (can[i][f]) break;
            can[i][f] = true;
            dist[i][f] = j;
            fk[i].pb(f);
            f = a[f];
        }
    }
    //cout << jump[2][0] + 1 << endl;
    for (int i = 0; i < n; i++) {
        int t = go(i, k - sz(g));
        for (int f = 0; f < sz(g); f++) {
            sk[i].pb(t);
            t = a[t];
        }
    }
    long long ks = k;
    for (int i = 0; i < sz(g); i++) {
        for (int j = 0; j < n; j++) {
            if (j == a[g[i]]) {
                cnt[cur]++;
            } else {
                if (can[j][g[i]]) {
                  //  cout << j << ' ' << g[i] << endl;
                    int fs = dist[j][g[i]] + 1;
                   // cout << dist[0][0] << endl;
                    long long kk = k;
                    if (kk == 0) {
                        cnt[g[i]]++;
                        continue;
                    }
                    kk--;
                    kk %= fs;
                    if (kk == 0) {
                        //cout << g[i] << endl;

                        cnt[j]++;
                    } else {

                        cnt[fk[j][kk]]++;
                    }
                } else {
                    if (k == 0) {
                        cnt[g[i]]++;
                        continue;
                    }
                    cnt[sk[j][k - 1 - (ks - sz(g))]]++;
                }
            }
        }
        k--;
    }
    for (int i = 0; i < n; i++) {
        cout << cnt[i] << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1400 KB Output is correct
4 Correct 4 ms 1400 KB Output is correct
5 Correct 3 ms 1292 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 3 ms 1400 KB Output is correct
8 Correct 3 ms 1400 KB Output is correct
9 Correct 4 ms 1400 KB Output is correct
10 Correct 3 ms 1272 KB Output is correct
11 Correct 3 ms 1272 KB Output is correct
12 Correct 4 ms 1400 KB Output is correct
13 Correct 3 ms 1272 KB Output is correct
14 Correct 3 ms 1272 KB Output is correct
15 Correct 79 ms 48740 KB Output is correct
16 Correct 41 ms 41208 KB Output is correct
17 Correct 96 ms 48908 KB Output is correct
18 Execution timed out 2043 ms 135672 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1400 KB Output is correct
4 Correct 4 ms 1400 KB Output is correct
5 Correct 3 ms 1292 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 3 ms 1400 KB Output is correct
8 Correct 3 ms 1400 KB Output is correct
9 Correct 4 ms 1400 KB Output is correct
10 Correct 3 ms 1272 KB Output is correct
11 Correct 3 ms 1272 KB Output is correct
12 Correct 4 ms 1400 KB Output is correct
13 Correct 3 ms 1272 KB Output is correct
14 Correct 3 ms 1272 KB Output is correct
15 Correct 79 ms 48740 KB Output is correct
16 Correct 41 ms 41208 KB Output is correct
17 Correct 96 ms 48908 KB Output is correct
18 Execution timed out 2043 ms 135672 KB Time limit exceeded
19 Halted 0 ms 0 KB -