Submission #1183025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183025		anmattroi	September (APIO24_september)	C++17	0 / 100	1 ms	2880 KiB

september

#include "september.h"
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;

int64_t Rand(int64_t l, int64_t h) {
    return uniform_int_distribution<int64_t>(l, h)(rng);
}

int64_t H[maxn];
int64_t P[5][maxn];
int64_t G[5];
int doable[maxn], sz[maxn];

vector<int> adj[maxn];


int head[maxn], heavy[maxn], pos[maxn], id = 0;

void pfs(int u) {
    sz[u] = 1; int mxsz = -1;
    for (int v : adj[u]) {
        pfs(v);
        sz[u] += sz[v];
        if (mxsz < sz[v]) {
            mxsz = sz[v];
            heavy[u] = v;
        }
    }
}

void dcp(int u, int p) {
    head[u] = p; pos[u] = ++id;
    if (heavy[u]) dcp(heavy[u], p);
    for (int v : adj[u])
        if (v != heavy[u]) dcp(v, v);
}

int st[4*maxn], lz[4*maxn];

void down(int r) {
    if (lz[r]) {
        st[r<<1] += lz[r];
        st[r<<1|1] += lz[r];
        lz[r<<1] += lz[r];
        lz[r<<1|1] += lz[r];
        lz[r] = 0;
    }
}

void update(int u, int v, int d, int r = 1, int lo = 1, int hi = n) {
    if (u <= lo && hi <= v) {
        st[r] += d;
        lz[r] += d;
        return;
    }
    down(r);
    int mid = (lo + hi) >> 1;
    if (u <= mid) update(u, v, d, r<<1, lo, mid);
    if (v > mid) update(u, v, d, r<<1|1, mid+1, hi);
    st[r] = min(st[r<<1], st[r<<1|1]);
}


int solve(int N, int M, vector<int> F, vector<vector<int> > S) {
    n = N;
    for (int i = 0; i < N; i++) ++F[i];
    for (int i = 0; i < M; i++) {
        S[i].insert(S[i].begin(), 0);
        for (int j = 1; j <= N; j++) ++S[i][j];
    }
    id = 0;

    for (int i = 1; i <= N; i++) H[i] = Rand(0, LLONG_MAX);
    for (int i = 0; i < M; i++)
        for (int j = 1; j <= N; j++) P[i][j] = (P[i][j-1] ^ H[S[i][j]]);
    int ans = 0, last = 1;

    for (int i = 1; i <= N; i++) heavy[i] = 0;

    for (int i = 1; i < N; i++) adj[F[i]].emplace_back(i+1);
    pfs(1);
    dcp(1, 1);

    for (int i = 1; i <= N; i++) --sz[i];
    for (int i = 1; i <= N; i++) doable[i] = 0;


    for (int i = 1; i < N; i++) {
        int u = S[0][i];
//        cerr << u << ' ';
        update(pos[u], pos[u], -sz[u]);
        u = F[u];
        if (u) {
            while (head[u] != head[1]) {
                update(pos[head[u]], pos[u], 1);
                u = F[head[u]];
            }
            update(pos[head[u]], pos[u], 1);
        }
//        cerr << st[1] << "\n";
        doable[i] = (st[1] >= 0);
    }
    while (last < N) {
        for (int o = last; o < N; o++) {
            if (!doable[o]) continue;
            for (int i = 0; i < M; i++) G[i] = (P[i][o]^P[i][last-1]);
            if (1) {
                int c = 1;
                for (int i = 1; i < M; i++) if (G[i] != G[i-1]) {c = 0; break;}
                if (c == 0) continue;
            }
            last = o+1;
            break;
        }
        ++ans;
    }
    for (int i = 1; i <= N; i++) adj[i].clear();
	return ans;
}
/*
1
5 2
0 0 1 1
1 2 3 4
4 1 2 3
*/

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 5
• Subtask 4: 0 / 9
• Subtask 5: 0 / 5
• Subtask 6: 0 / 11
• Subtask 7: 0 / 9
• Subtask 8: 0 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16