Submission #998125

#	Time	Username	Problem	Language	Result	Execution time	Memory
998125		Trisanu_Das	September (APIO24_september)	C++17	84 / 100	425 ms	47756 KiB

september

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int M = 15;
int sz[N][M], p[N][M];
vector<int> g[N];

void make_set(int v, int t) {
    p[v][t] = v;
    sz[v][t] = 1;
}

int find_set(int v, int t) {
    if (p[v][t] == v) return v;
    return p[v][t] = find_set(p[v][t], t);
}

void merge(int a, int b, int t) {
    a = find_set(a, t);
    b = find_set(b, t);
    if (a == b) return;
    if (sz[a][t] < sz[b][t]) swap(a, b);
    sz[a][t] += sz[b][t];
    p[b][t] = a;
}

void add_edges(int v, int t) {
    for (auto u : g[v]) {
        if (p[u][t] >= 0) {
            merge(u, v, t);
        }
    }
}

int solve(int n, int m, vector<int> F, vector<vector<int>> S) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            p[i][j] = -1;
        }
        g[i].clear();
    }

    for (int i = 1; i < n; i++) {
        g[i].push_back(F[i]);
        g[F[i]].push_back(i);
    }
    int ans = 0;
    for (int i = 0; i < m; i++) {
        make_set(0, i);
    }
    set<int> myset[M];
    for (int i = n - 2; i >= 0; i--) {
        bool check = true;
        for (int j = 0; j < m; j++) {
            int x = S[j][i];
            myset[j].insert(x);
            make_set(x, j);
            add_edges(x, j);
            if (sz[find_set(x, j)][j] != n - i) {
                check = false;
            }
        }
        if (n <= 1000) {
            for (int j = 1; j < m; j++) {
                if (myset[j] != myset[j - 1]) {
                    check = false;
                }
            }
        }

        if (check) {
            ans++;
        }
    }

    return ans;
}

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