Submission #1000743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000743		Boycl07	September (APIO24_september)	C++17	100 / 100	105 ms	18120 KiB

september

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

typedef long long ll;

#define rep(i, n) for(int i = 1; (i) <= (n); ++i)
#define forn(i, l, r) for(int i = (l); i <= (r); ++i)
#define ford(i, r, l) for(int i = (r); i >= (l); --i)
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define FORD(i, n) for(int i = ((n) - 1); i >= 0; --i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task "note"
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}

const int MaxN = 1e5 + 3;
const int MaxM = 6;
const int p = 311;

vector<int> g[MaxN];

struct volunteers
{
    int num_cc;
    int del[MaxN];
    int n;
    int P[MaxN], cur_hash;
    void init(int N)
    {
        n = N;
        num_cc = 1;
        FOR(i, N) del[i] = 0;
        P[0] = 1;
        rep(i, N) P[i] = P[i - 1] * p;
        cur_hash = 0;
    }

    bool check() {return num_cc == 1;}

    void add(int x)
    {
        del[x] = 1;
        --num_cc;
        for(int v : g[x])
            num_cc += !del[v];
        cur_hash += P[x];
    }
} f[MaxM];

bool check(int M)
{
    FOR(i, M) if(!f[i].check() || f[i].cur_hash != f[0].cur_hash) return 0;
    return 1;
}

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S)
{
    FOR(i, N) g[i].clear();
    rep(i, N - 1) g[F[i]].pb(i), g[i].pb(F[i]);

    FOR(i, M) f[i].init(N);

    int res = 0;
    FOR(i, N - 1)
    {
        FOR(j, M) f[j].add(S[j][i]);
        if(check(M)) ++res;
    }
    return res;
}

• 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: 16 / 16