#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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5212 KB |
Output is correct |
2 |
Correct |
1 ms |
5212 KB |
Output is correct |
3 |
Correct |
1 ms |
5212 KB |
Output is correct |
4 |
Correct |
1 ms |
5212 KB |
Output is correct |
5 |
Correct |
1 ms |
5212 KB |
Output is correct |
6 |
Correct |
1 ms |
5212 KB |
Output is correct |
7 |
Correct |
1 ms |
5212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5212 KB |
Output is correct |
2 |
Correct |
1 ms |
5212 KB |
Output is correct |
3 |
Correct |
1 ms |
5212 KB |
Output is correct |
4 |
Correct |
1 ms |
5212 KB |
Output is correct |
5 |
Correct |
1 ms |
5212 KB |
Output is correct |
6 |
Correct |
1 ms |
5212 KB |
Output is correct |
7 |
Correct |
1 ms |
5212 KB |
Output is correct |
8 |
Correct |
1 ms |
7512 KB |
Output is correct |
9 |
Correct |
1 ms |
7260 KB |
Output is correct |
10 |
Correct |
1 ms |
7260 KB |
Output is correct |
11 |
Correct |
1 ms |
7260 KB |
Output is correct |
12 |
Correct |
1 ms |
7260 KB |
Output is correct |
13 |
Correct |
1 ms |
7260 KB |
Output is correct |
14 |
Correct |
1 ms |
7260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5208 KB |
Output is correct |
2 |
Correct |
1 ms |
5208 KB |
Output is correct |
3 |
Correct |
1 ms |
5212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5212 KB |
Output is correct |
2 |
Correct |
1 ms |
5212 KB |
Output is correct |
3 |
Correct |
1 ms |
5212 KB |
Output is correct |
4 |
Correct |
1 ms |
5212 KB |
Output is correct |
5 |
Correct |
1 ms |
5212 KB |
Output is correct |
6 |
Correct |
1 ms |
5212 KB |
Output is correct |
7 |
Correct |
1 ms |
5212 KB |
Output is correct |
8 |
Correct |
1 ms |
5208 KB |
Output is correct |
9 |
Correct |
1 ms |
5208 KB |
Output is correct |
10 |
Correct |
1 ms |
5212 KB |
Output is correct |
11 |
Correct |
1 ms |
5208 KB |
Output is correct |
12 |
Correct |
1 ms |
5212 KB |
Output is correct |
13 |
Correct |
1 ms |
5212 KB |
Output is correct |
14 |
Correct |
1 ms |
5212 KB |
Output is correct |
15 |
Correct |
1 ms |
5212 KB |
Output is correct |
16 |
Correct |
1 ms |
5208 KB |
Output is correct |
17 |
Correct |
1 ms |
5212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5208 KB |
Output is correct |
2 |
Correct |
1 ms |
5208 KB |
Output is correct |
3 |
Correct |
1 ms |
5212 KB |
Output is correct |
4 |
Correct |
2 ms |
7260 KB |
Output is correct |
5 |
Correct |
3 ms |
7260 KB |
Output is correct |
6 |
Correct |
4 ms |
7260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5212 KB |
Output is correct |
2 |
Correct |
1 ms |
5212 KB |
Output is correct |
3 |
Correct |
1 ms |
5212 KB |
Output is correct |
4 |
Correct |
1 ms |
5212 KB |
Output is correct |
5 |
Correct |
1 ms |
5212 KB |
Output is correct |
6 |
Correct |
1 ms |
5212 KB |
Output is correct |
7 |
Correct |
1 ms |
5212 KB |
Output is correct |
8 |
Correct |
1 ms |
7512 KB |
Output is correct |
9 |
Correct |
1 ms |
7260 KB |
Output is correct |
10 |
Correct |
1 ms |
7260 KB |
Output is correct |
11 |
Correct |
1 ms |
7260 KB |
Output is correct |
12 |
Correct |
1 ms |
7260 KB |
Output is correct |
13 |
Correct |
1 ms |
7260 KB |
Output is correct |
14 |
Correct |
1 ms |
7260 KB |
Output is correct |
15 |
Correct |
1 ms |
5208 KB |
Output is correct |
16 |
Correct |
1 ms |
5208 KB |
Output is correct |
17 |
Correct |
1 ms |
5212 KB |
Output is correct |
18 |
Correct |
1 ms |
5208 KB |
Output is correct |
19 |
Correct |
1 ms |
5212 KB |
Output is correct |
20 |
Correct |
1 ms |
5212 KB |
Output is correct |
21 |
Correct |
1 ms |
5212 KB |
Output is correct |
22 |
Correct |
1 ms |
5212 KB |
Output is correct |
23 |
Correct |
1 ms |
5208 KB |
Output is correct |
24 |
Correct |
1 ms |
5212 KB |
Output is correct |
25 |
Correct |
2 ms |
7260 KB |
Output is correct |
26 |
Correct |
3 ms |
7260 KB |
Output is correct |
27 |
Correct |
4 ms |
7260 KB |
Output is correct |
28 |
Correct |
2 ms |
7260 KB |
Output is correct |
29 |
Correct |
2 ms |
7260 KB |
Output is correct |
30 |
Correct |
2 ms |
7260 KB |
Output is correct |
31 |
Correct |
2 ms |
7260 KB |
Output is correct |
32 |
Correct |
2 ms |
7260 KB |
Output is correct |
33 |
Correct |
2 ms |
7260 KB |
Output is correct |
34 |
Correct |
2 ms |
7260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5208 KB |
Output is correct |
2 |
Correct |
1 ms |
5208 KB |
Output is correct |
3 |
Correct |
1 ms |
5212 KB |
Output is correct |
4 |
Correct |
88 ms |
10068 KB |
Output is correct |
5 |
Correct |
90 ms |
10124 KB |
Output is correct |
6 |
Correct |
105 ms |
10104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5212 KB |
Output is correct |
2 |
Correct |
1 ms |
5212 KB |
Output is correct |
3 |
Correct |
1 ms |
5212 KB |
Output is correct |
4 |
Correct |
1 ms |
5212 KB |
Output is correct |
5 |
Correct |
1 ms |
5212 KB |
Output is correct |
6 |
Correct |
1 ms |
5212 KB |
Output is correct |
7 |
Correct |
1 ms |
5212 KB |
Output is correct |
8 |
Correct |
1 ms |
5208 KB |
Output is correct |
9 |
Correct |
1 ms |
5208 KB |
Output is correct |
10 |
Correct |
1 ms |
5212 KB |
Output is correct |
11 |
Correct |
1 ms |
5208 KB |
Output is correct |
12 |
Correct |
1 ms |
5212 KB |
Output is correct |
13 |
Correct |
1 ms |
5212 KB |
Output is correct |
14 |
Correct |
1 ms |
5212 KB |
Output is correct |
15 |
Correct |
1 ms |
5212 KB |
Output is correct |
16 |
Correct |
1 ms |
5208 KB |
Output is correct |
17 |
Correct |
1 ms |
5212 KB |
Output is correct |
18 |
Correct |
88 ms |
10068 KB |
Output is correct |
19 |
Correct |
90 ms |
10124 KB |
Output is correct |
20 |
Correct |
105 ms |
10104 KB |
Output is correct |
21 |
Correct |
103 ms |
10660 KB |
Output is correct |
22 |
Correct |
103 ms |
10692 KB |
Output is correct |
23 |
Correct |
100 ms |
10412 KB |
Output is correct |
24 |
Correct |
96 ms |
10412 KB |
Output is correct |
25 |
Correct |
104 ms |
10664 KB |
Output is correct |
26 |
Correct |
101 ms |
10760 KB |
Output is correct |
27 |
Correct |
99 ms |
10256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5208 KB |
Output is correct |
2 |
Correct |
1 ms |
5208 KB |
Output is correct |
3 |
Correct |
1 ms |
5212 KB |
Output is correct |
4 |
Correct |
2 ms |
7260 KB |
Output is correct |
5 |
Correct |
3 ms |
7260 KB |
Output is correct |
6 |
Correct |
4 ms |
7260 KB |
Output is correct |
7 |
Correct |
88 ms |
10068 KB |
Output is correct |
8 |
Correct |
90 ms |
10124 KB |
Output is correct |
9 |
Correct |
105 ms |
10104 KB |
Output is correct |
10 |
Correct |
55 ms |
15308 KB |
Output is correct |
11 |
Correct |
58 ms |
15212 KB |
Output is correct |
12 |
Correct |
56 ms |
15312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5212 KB |
Output is correct |
2 |
Correct |
1 ms |
5212 KB |
Output is correct |
3 |
Correct |
1 ms |
5212 KB |
Output is correct |
4 |
Correct |
1 ms |
5212 KB |
Output is correct |
5 |
Correct |
1 ms |
5212 KB |
Output is correct |
6 |
Correct |
1 ms |
5212 KB |
Output is correct |
7 |
Correct |
1 ms |
5212 KB |
Output is correct |
8 |
Correct |
1 ms |
7512 KB |
Output is correct |
9 |
Correct |
1 ms |
7260 KB |
Output is correct |
10 |
Correct |
1 ms |
7260 KB |
Output is correct |
11 |
Correct |
1 ms |
7260 KB |
Output is correct |
12 |
Correct |
1 ms |
7260 KB |
Output is correct |
13 |
Correct |
1 ms |
7260 KB |
Output is correct |
14 |
Correct |
1 ms |
7260 KB |
Output is correct |
15 |
Correct |
1 ms |
5208 KB |
Output is correct |
16 |
Correct |
1 ms |
5208 KB |
Output is correct |
17 |
Correct |
1 ms |
5212 KB |
Output is correct |
18 |
Correct |
1 ms |
5208 KB |
Output is correct |
19 |
Correct |
1 ms |
5212 KB |
Output is correct |
20 |
Correct |
1 ms |
5212 KB |
Output is correct |
21 |
Correct |
1 ms |
5212 KB |
Output is correct |
22 |
Correct |
1 ms |
5212 KB |
Output is correct |
23 |
Correct |
1 ms |
5208 KB |
Output is correct |
24 |
Correct |
1 ms |
5212 KB |
Output is correct |
25 |
Correct |
2 ms |
7260 KB |
Output is correct |
26 |
Correct |
3 ms |
7260 KB |
Output is correct |
27 |
Correct |
4 ms |
7260 KB |
Output is correct |
28 |
Correct |
2 ms |
7260 KB |
Output is correct |
29 |
Correct |
2 ms |
7260 KB |
Output is correct |
30 |
Correct |
2 ms |
7260 KB |
Output is correct |
31 |
Correct |
2 ms |
7260 KB |
Output is correct |
32 |
Correct |
2 ms |
7260 KB |
Output is correct |
33 |
Correct |
2 ms |
7260 KB |
Output is correct |
34 |
Correct |
2 ms |
7260 KB |
Output is correct |
35 |
Correct |
88 ms |
10068 KB |
Output is correct |
36 |
Correct |
90 ms |
10124 KB |
Output is correct |
37 |
Correct |
105 ms |
10104 KB |
Output is correct |
38 |
Correct |
103 ms |
10660 KB |
Output is correct |
39 |
Correct |
103 ms |
10692 KB |
Output is correct |
40 |
Correct |
100 ms |
10412 KB |
Output is correct |
41 |
Correct |
96 ms |
10412 KB |
Output is correct |
42 |
Correct |
104 ms |
10664 KB |
Output is correct |
43 |
Correct |
101 ms |
10760 KB |
Output is correct |
44 |
Correct |
99 ms |
10256 KB |
Output is correct |
45 |
Correct |
55 ms |
15308 KB |
Output is correct |
46 |
Correct |
58 ms |
15212 KB |
Output is correct |
47 |
Correct |
56 ms |
15312 KB |
Output is correct |
48 |
Correct |
69 ms |
17152 KB |
Output is correct |
49 |
Correct |
72 ms |
16892 KB |
Output is correct |
50 |
Correct |
65 ms |
18120 KB |
Output is correct |
51 |
Correct |
66 ms |
16956 KB |
Output is correct |
52 |
Correct |
70 ms |
17152 KB |
Output is correct |
53 |
Correct |
65 ms |
16896 KB |
Output is correct |
54 |
Correct |
76 ms |
16840 KB |
Output is correct |