Submission #1195322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195322		og_matveychick1	Space Pirate (JOI14_space_pirate)	C++20	33 / 100	49 ms	57456 KiB

space_pirate

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define ret return
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define be(x) x.begin()
#define en(x) x.end()
#define sz(x) ll(x.size())
#define for0(i, n) for (ll   i = 0; i < (n); ++i)
#define for1(i, n) for (ll   i = 1; i < (n); ++i)
#define rfor0(i, n) for (ll   i = (n) - 1; i >= 0; --i)
#define rfor1(i, n) for (ll   i = (n) - 1; i >= 1; --i)
#define rep(i, a, n) for (ll   i = a; i < ll(n); ++i)
#define fastIO() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define con continue
#define pb push_back
#define pob pop_back
#define rs resize
#define ba(a) a.back()
#define rsun(a) a.resize(unique(a.begin(), a.end())-a.begin())
#define endl '\n'
#ifdef OG_Matveychick1
bool local = true;
#else
bool local = false;
#endif

typedef long long ll;
typedef vector<ll> vll;

template<typename T1, typename T2>
inline void amin(T1 &a, T2 b) {
    a = min(a, b);
}

template<typename T1, typename T2>
inline void amax(T1 &a, T2 b) {
    a = max(a, b);
}


mt19937_64 rn(chrono::steady_clock::now().time_since_epoch().count());
//mt19937_64 rn(4);

ll rnd(ll l, ll r) {
    ll a = rn() % (r - l + 1) + l;
    return a;
}

void solve();

ll T = 1;

signed main(int argc, char **argv) {
//    setlocale(LC_ALL, "RUS");
    fastIO()
    cout.precision(12);
    cout << fixed;
    if (local && argc == 1) {
        freopen("input.txt", "r", stdin);
//        freopen("output.txt", "w", stdout);
    }
//    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}


struct node {
    vll a, b;
    vll ps;
    ll mn;

    node() {}
};

const ll N = 1e5 + 5, K = 60;

ll n, m, a[N], k, ans[N], up[K][N], used[N], dg[N], m1, ad[N], psb[N], cmp[N], gc[N], inc[N];
vector<node> nd;

ll go(ll v, ll s) {
    for0(i, K) if ((s >> i) & 1) v = up[i][v];
    ret v;
}

void prec() {
    for0(i, n) {
        if (used[i] || dg[i]) con;
        nd.pb(node());
        vll st;
        ll v = i;
        st.pb(v);
        used[v] = 1;
        while (!used[a[v]]) {
            v = a[v];
            st.pb(v);
            used[v] = 1;
        }
        bool fl = 0;
        for (auto x: st) {
            fl |= x == a[v];
            if (fl) {
                psb[x] = sz(ba(nd).b);
                ba(nd).b.pb(x);
                inc[x] = 1;
            } else {
                ba(nd).a.pb(x);
            }
        }
    }
    for0(i, n) {
        if (used[i]) con;
        nd.pb(node());
        vll st;
        ll v = i;
        st.pb(v);
        used[v] = 1;
        while (!used[a[v]]) {
            v = a[v];
            st.pb(v);
            used[v] = 1;
        }
        bool fl = 0;
        for (auto x: st) {
            fl |= x == a[v];
            if (fl) {
                psb[x] = sz(ba(nd).b);
                ba(nd).b.pb(x);
                inc[x] = 1;
            } else {
                ba(nd).a.pb(x);
            }
        }
    }
    for (auto &x: nd) x.ps.rs(2 * sz(x.b) + 1);
    for (auto &x: nd) {
        ll mn = 1e18;
        if (sz(x.a)) amin(mn, *min_element(all(x.a)));
        if (sz(x.b)) amin(mn, *min_element(all(x.b)));
        x.mn = mn;
    }
    sort(all(nd), [&](node &a, node &b) {
        ret a.mn < b.mn;
    });
    ll pv = 0;
    for (auto x: nd) {
        for (auto c: x.b) cmp[c] = pv;
        for (auto c: x.a) cmp[c] = pv;
        pv++;
    }
}

void solve1(vll c, ll k, ll m) {
    for (ll d = 1; d <= m; d++) {
        ll dc = m - d + 1;
        ll k1 = k;
        k1 %= dc;
        ll v;
        if (k1 == 0) {
            v = c[0];
            ans[v] += m - d;
        } else {
            v = d + k1 - 1;
            ans[c[v]] += v - d + 1;
            ans[c[k1]] += (m - d) - (v - d + 1);
        }

        dc = d + 1;
        k1 = k % dc;
        v = k1;
        ll pl = m - d;
        ll l = 0;
        while (pl > 0) {
            ll mn = min(pl, v - l + 1);
            ans[c[v]] += mn;
            pl -= mn;
            v += d + 1;
            l = v - d;
        }
    }
}

void solve2(vll c, ll p1, ll p2, ll k, ll m) {
    for (ll d = 1; d <= m; d++) {
        ll dc = d + 1;
        ll k1 = k % dc;
        ll v = k1;
        ll pl = m - d - max(0ll, (m - p2) - d);
        ll l = 0;
        while (pl > 0) {
            ll mn = min(pl, v - l + 1);
            ans[c[v]] += mn;
            pl -= mn;
            v += d + 1;
            l = v - d;
        }
    }
    for (ll d = 1; d <= m; d++) {
        ll dc = d + 1;
        ll k1 = k % dc;
        ll v = k1;
        ll pl = max(0ll, p1 - d);
        ll l = 0;
        while (pl > 0) {
            ll mn = min(pl, v - l + 1);
            ans[c[v]] -= mn;
            pl -= mn;
            v += d + 1;
            l = v - d;
        }
    }
}

void solve3(vll c, ll p1, ll fp, ll k, ll m, ll j) {
    for (ll d = 1; d <= m; d++) {
        ll dc = d + 1;
        ll k1 = k % dc;
        ll v = k1;
        ll pl = m - d - max(0ll, (m - p1) - d);
        ll l = 0;
        while (pl > 0) {
            ll mn = min(pl, v - l + 1);
            ll vp = (v < sz(c) ? c[v] : nd[j].b[(v - sz(c) + fp) % sz(nd[j].b)]);
            ans[vp] += mn;
            pl -= mn;
            v += d + 1;
            l = v - d;
        }
    }
    for (ll d = 1; d <= m; d++) {
        ll dc = d + 1;
        ll k1 = k % dc;
        ll v = k1;
        ll pl = max(0ll, p1 - d);
        ll l = 0;
        while (pl > 0) {
            ll mn = min(pl, v - l + 1);
            ll vp = (v < sz(c) ? c[v] : nd[j].b[(v - sz(c) + fp) % sz(nd[j].b)]);
            ans[vp] -= mn;
            pl -= mn;
            v += d + 1;
            l = v - d;
        }
    }
}

ll f(ll v) {
    if (gc[v] != -1) ret gc[v];
    ret gc[v] = (inc[v] ? v : f(go(ba(nd[cmp[v]].a), 1)));
}

void solve() {
    cin >> n >> k;
    for0(i, n) cin >> a[i], a[i]--, up[0][i] = a[i], dg[a[i]]++, gc[i] = -1;
    for1(i, K) for0(j, n) up[i][j] = up[i - 1][up[i - 1][j]];
    prec();
    for0(i, n) gc[i] = f(i);
    m = sz(nd[0].a);
    if (sz(nd[0].b)) m += sz(nd[0].b);
    else m += sz(nd[cmp[gc[0]]].b);
    ans[go(0, k)] += (n - m) * n; // из других компонент в нашу
    for (auto x: nd[0].a) { // из нашего хвоста куда-то
        if (x == 0) break;
        ans[go(0, k)] += n;
    }
    {   // петли в нашей компоненте после хвоста
        bool fl = 0;
        for (auto x: nd[0].a) {
            fl |= x == 0;
            ans[x] += fl;
            m1 += fl;
        }
        if (sz(nd[0].b)) for (auto x: nd[0].b) ans[x]++;
        else for (auto x: nd[cmp[gc[0]]].b) ans[x]++;
    }
    for1(i, sz(nd)) { // из нашей компоненты после хвоста в другие компоненты
        ll c = (sz(nd[i].a) ? cmp[gc[ba(nd[i].a)]] : cmp[nd[i].b[0]]);
        if (c) for (auto x: nd[c].b) ans[x] += m1 + (c == 0 ? 0 : sz(nd[0].b));
        for (auto x: nd[i].a) {
            ad[c] += (m1 + (c == 0 ? 0 : sz(nd[0].b))) / sz(nd[c].b);
            ll ost = (m1 + (c == 0 ? 0 : sz(nd[0].b))) % sz(nd[c].b);
            ll r = psb[go(x, k - 1)], l = r - ost + 1;
            r += sz(nd[c].b);
            l += sz(nd[c].b);
            nd[c].ps[l]++;
            nd[c].ps[r + 1]--;
        }
    }

    { // из нашего цикла в наш цикл
        ll k1;
        if (find(all(nd[0].a), 0) == en(nd[0].a)) k1 = k + psb[0];
        else k1 = k - (en(nd[0].a) - find(all(nd[0].a), 0));
        solve1(nd[0].b, k1, sz(nd[0].b));
    }

    { // из нашей компоненты после хвоста в наш цикл
        ll m2;
        if (find(all(nd[0].a), 0) == en(nd[0].a)) m2 = 0;
        else m2 = en(nd[0].a) - find(all(nd[0].a), 0);
        for (auto x: nd[0].b) ans[x] += m2;
    }

    if (find(all(nd[0].a), 0) != en(nd[0].a)) {
        { // из нашего хвоста в хвост ->
            ll D = en(nd[0].a) - find(all(nd[0].a), 0) - 1;
            for (ll d = 1; d <= D; d++) ans[go(0, k - (d - 1))] += D - d + 1;
        }
        { // + цикл в нашем хвосте
            ll k1 = k + (find(all(nd[0].a), 0) - be(nd[0].a));
            ll p = find(all(nd[0].a), 0) - be(nd[0].a);
            vll c;
            for (auto x: nd[0].a) c.pb(x);
            solve2(c, p, sz(nd[0].a), k1, sz(c));
        }
    }

    { // из нашего цикла в какой-то хвост
        ll j = (find(all(nd[0].b), 0) != en(nd[0].b) ? 0 : cmp[gc[ba(nd[0].a)]]);
        ll f = (find(all(nd[0].b), 0) != en(nd[0].b) ? 0 : cmp[gc[ba(nd[0].a)]]);
        ll dc = sz(nd[j].b);
        ll k2 = k - (find(all(nd[0].a), 0) == en(nd[0].a) ? 0 : en(nd[0].a) - find(all(nd[0].a), 0));
        for0(i, sz(nd)) {
            if (!sz(nd[i].a) || cmp[gc[ba(nd[i].a)]] != j) con;
            ll p1 = psb[gc[ba(nd[i].a)]];
            ll k1;
            k1 = k2 + (psb[f] - p1 + dc) % dc + sz(nd[i].a);
            solve3(nd[i].a, sz(nd[i].a), p1, k1, sz(nd[i].a) + sz(nd[j].b), j);
        }
    }

    for0(i, sz(nd)) {
        partial_sum(all(nd[i].ps), be(nd[i].ps));
        for0(j, sz(nd[i].b)) ans[nd[i].b[j]] += nd[i].ps[j] + nd[i].ps[j + sz(nd[i].b)];
        for (auto x: nd[i].b) ans[x] += ad[i];
    }
    for0(i, n) cout << ans[i] << endl;
}

Compilation message (stderr)

space_pirate.cpp: In function 'int main(int, char**)':
space_pirate.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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