Submission #246978

#	Time	Username	Problem	Language	Result	Execution time	Memory
246978		receed	Space Pirate (JOI14_space_pirate)	C++14	0 / 100	2057 ms	10480 KiB

space_pirate

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 100001;
vector<int> g[N], cl, l1;
ll a[N], pos[N], used[N], cyc[N], cnt[N], ps[N], st[N], vis[N], cu[N];
ll ans[N];

// void dfs(int v) {
//     used[v] = 1;
//     for (int u : g[v])
//         if (!used[u])
//             dfs(u);
// }

// void dfs2(int v, int pos) {
//     used[v] = 1;
//     cnt[pos]++;
//     pos--;
//     if (pos < 0)
//         pos = cl.size() - 1;
//     for (int u : g[v])
//         if (!cyc[u])
//             dfs2(u, pos);
// }

void dfs3(int v, int h, int fv, ll ck) {
    vis[v] = 1;
    st[h - 1] = v;
    ans[st[(h - ck % h) % h]]++;
    for (int u : g[v]) {
        if (u == fv)
            continue;
        dfs3(u, h + 1, fv, ck);
    }
}

void dfs4(int v, ll pos, int fv) {
    vis[v] = 1;
    ans[cl[pos]]++;
    for (int u : g[v])
        if (u != fv && cu[u] != 2)
            dfs4(u, (pos - 1 + (ll) cl.size()) % cl.size(), fv);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n, k;
    cin >> n >> k;
    rep(i, n) {
        cin >> a[i];
        a[i]--;
        g[a[i]].push_back(i);
        pos[i] = -1;
    }
    ll c = 0, v = 0, bl, u, dv, bd;
    while (pos[v] == -1) {
        l1.push_back(v);
        pos[v] = c++;
        v = a[v];
    }
    bl = c - pos[v];
    bd = pos[v];
    ll dvp = (k - bd) % bl;
    dv = l1[bd + dvp];
    // dfs(v);
    ans[dv] += (n - c) * n;
    // rep(i, bl) {
    //     ll of = (i - dvp + bl) % bl;
    //     rep(i, bd)
    //         ans[l1[bd + i]] += (c - 2 - i - of + bl - 1) / bl;
    // }
    /*rep(i, bd)
        rep(j, c - 1 - i)
            ans[l1[((k - bd - j) % bl + bl) % bl + bd]]++;
    rep(i, bl)
        dfs3(

    rep(i, n) {
        if (used[i])
            continue;
        u = i;
        cl.clear();
        while (pos[u] == -1) {
            pos[u] = -2;
            u = a[u];
        }
        while (!cyc[u]) {
            cnt[cl.size()] = 0;
            cl.push_back(u);
            cyc[u] = 1;
            u = a[u];
        }
        int cls = cl.size();
        rep(i, cls)
            dfs2(cl[i], i);
        rep(i, cls)
            ps[i + 1] = ps[i] + cnt[i];
        rep(i, cls) {
            cout << cl[i] << ' ' << cnt[i] << '\n';
            int rp = (i + k) % cls + 1, lp = (i + k - c % cls + 1) % cls;
            cout << ' ' << lp << ' ' << rp << '\n';
            if (lp < 0) {
                lp += cls;
                ans[cl[i]] += ps[cls];
            }
            ans[cl[i]] += c / cls * ps[cls] + ps[rp] - ps[lp];
        }
    }*/
    rep(i, c) {
        rep(j, n)
            vis[j] = cu[j] = 0;
        cl.clear();
        dfs3(l1[i], 1, l1[i], k - i);
        rep(j, n) {
            if (vis[j])
                continue;
            u = j;
            while (!cu[u]) {
                cu[u] = 1;
                u = a[u];
            }
            while (cu[u] == 1) {
                cl.push_back(u);
                cu[u] = 2;
                u = a[u];
            }
            rep(l, cl.size())
                dfs4(cl[l], (l + k - i - 1) % cl.size(), l1[i]);
        }
    }
    rep(i, n)
        cout << ans[i] << '\n';
}

Compilation message (stderr)

space_pirate.cpp: In function 'int main()':
space_pirate.cpp:19:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i = 0; i < (n); i++)
                                     ^
space_pirate.cpp:152:13: note: in expansion of macro 'rep'
             rep(l, cl.size())
             ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 37
• Subtask 3: 0 / 33
• Subtask 4: 0 / 20