oj.uz

Submission #422708

# Submission time Handle Problem Language Result Execution time Memory
422708 2021-06-10T10:59:05 Z ACmachine Space Pirate (JOI14_space_pirate) C++17
10 / 100
 2000 ms 524292 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
const int INF = (int)1e9;
typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n; ll k;
    cin >> n >> k;
    const int mx = 62;
    vector<vector<int>> nxt(mx, vector<int>(n, -1));
    REP(i, n){
        cin >> nxt[0][i];
        nxt[0][i]--;
    }
    FOR(i, 1, mx, 1){
        REP(j, n){
            nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
        }
    }
    vector<vector<int>> dist(n, vector<int>(n, -1));
    function<void(int, int, int)> dfs = [&](int v, int d, int s){
        dist[s][v] = d;
        if(dist[s][nxt[0][v]] == -1){
            dfs(nxt[0][v], d + 1, s);
        }
    };
    REP(i, n){
        dfs(i, 0, i);
    } 
    auto go = [&](int v, ll k){
        REPD(i, mx - 1){
            if((1ll << i) <= k){
                v = nxt[i][v];
                k -= (1ll << i);
            }
        }
        return v;
    };
    vector<int> ans(n, 0);
    int def = go(0, k);
    REP(a, n){
        REP(b, n){
            if(dist[0][a] == -1){ // neviem sa dostat do zaciatku novej hrany
                ans[def]++;
            }
            else if(dist[b][a] == -1){ // nevytvorim cyklus
                ans[go(b, k - dist[0][a] - 1)]++;
            }
            else if(a == b){ // rovnake
                ans[a]++;
            } 
            else{ // vytvorim cyklus; pojdem do a
                ll kk = k - dist[0][a];
                ll cycle_size = 1 + dist[b][a];
                kk %= cycle_size;
                if(kk == 0)
                    ans[a]++;
                else
                    ans[go(b, kk - 1)]++; 
            } 
        }
    }
    REP(i, n){
        cout << ans[i] << "\n";
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 2 ms 312 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 96 ms 36312 KB Output is correct
16 Correct 45 ms 36416 KB Output is correct
17 Correct 124 ms 36300 KB Output is correct
18 Correct 1849 ms 36524 KB Output is correct
19 Correct 1229 ms 36460 KB Output is correct
20 Correct 934 ms 36548 KB Output is correct
21 Execution timed out 2080 ms 36428 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 270 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 2 ms 312 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 96 ms 36312 KB Output is correct
16 Correct 45 ms 36416 KB Output is correct
17 Correct 124 ms 36300 KB Output is correct
18 Correct 1849 ms 36524 KB Output is correct
19 Correct 1229 ms 36460 KB Output is correct
20 Correct 934 ms 36548 KB Output is correct
21 Execution timed out 2080 ms 36428 KB Time limit exceeded
22 Halted 0 ms 0 KB -