Submission #247007

#	Time	Username	Problem	Language	Result	Execution time	Memory
247007		receed	Space Pirate (JOI14_space_pirate)	C++14	80 / 100	226 ms	13680 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) {
    assert(vis[v] != 2);
    vis[v] = 2;
    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, 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];
        }
    }*/
    if (n <= 3000) {
        rep(i, c) {
            rep(j, n)
                vis[j] = cu[j] = 0;
            dfs3(l1[i], 1, l1[i], k - i);
            rep(j, n) {
                if (vis[j])
                    continue;
                cl.clear();
                u = j;
                while (!cu[u]) {
                    cu[u] = 1;
                    assert(!vis[u]);
                    u = a[u];
                }
                while (cu[u] == 1) {
                    cl.push_back(u);
                    cu[u] = 2;
                    assert(!vis[u]);
                    u = a[u];
                }
                rep(l, cl.size())
                    dfs4(cl[l], (l + k - i - 1) % cl.size(), l1[i]);
            }
        }
    }
    else {
        rep(i, n) 
            if (!used[i])
                ans[i] += c;
        ans[dv] += c;
        for (int i = 1; i < c; i++) {
            int pos = c - i + (k - 1) % i + 1;
            ans[l1[pos % c]] += (c - pos == 0 ? i : pos - c + i);
            int cc = c - (c - pos == 0 ? i : pos - c + i);
            // cout << pos << '\n';
            while (cc > 0) {
                pos = (pos + i) % c;
                ans[l1[pos]] += min(cc, i);
                cc -= min(cc, i);
            }
            // rep(j, c)
            //     cout << ans[l1[j]] << ' ';
            // cout << '\n';
        }
    }
    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:154:17: note: in expansion of macro 'rep'
                 rep(l, cl.size())
                 ^~~

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