#include "september.h"
#include <bits/stdc++.h>
using namespace std;
int solve(int n, int m, vector<int> par, vector<vector<int>> s) {
vector<int> p(n);
iota(p.begin(), p.end(), 0);
vector<int> from(n, n), to(n, 0);
function<int(int)> GetPar = [&](int x) {
return p[x] == x ? x : p[x] = GetPar(p[x]);
};
auto Merge = [&](int x, int y) {
x = GetPar(x);
y = GetPar(y);
if (x == y) {
return;
}
from[x] = min(from[x], from[y]);
to[x] = max(to[x], to[y]);
p[y] = x;
};
for (int i = 0; i < m; i++) {
for (int j = 0; j + 1 < n; j++) {
from[s[i][j]] = min(from[s[i][j]], j);
to[s[i][j]] = max(to[s[i][j]], j);
}
}
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
g[par[i]].push_back(i);
}
int T = 0;
vector<int> dfn(n);
vector<int> dfo(n);
function<void(int)> Dfs = [&](int v) {
dfn[v] = ++T;
for (int u : g[v]) {
Dfs(u);
}
dfo[v] = ++T;
};
Dfs(0);
auto IsAnc = [&](int x, int y) {
return dfn[x] <= dfn[y] && dfo[y] <= dfo[x];
};
for (int k = 0; k < m; k++) {
for (int i = 0; i + 1 < n; i++) {
for (int j = i + 1; j + 1 < n; j++) {
if (IsAnc(s[k][i], s[k][j])) {
Merge(s[k][i], s[k][j]);
}
}
}
}
vector<pair<int, int>> ev;
for (int i = 1; i < n; i++) {
if (GetPar(i) != i) {
continue;
}
ev.emplace_back(from[i], ~to[i]);
ev.emplace_back(to[i], to[i]);
}
sort(ev.begin(), ev.end());
multiset<int> st;
int res = 0;
for (auto& p : ev) {
if (st.empty()) {
res += 1;
}
int v = p.second;
if (v < 0) {
st.insert(~v);
} else {
st.erase(st.find(v));
}
}
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
604 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
2 ms |
344 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
348 KB |
Output is correct |
14 |
Correct |
2 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
348 KB |
Output is correct |
16 |
Correct |
3 ms |
348 KB |
Output is correct |
17 |
Correct |
2 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
604 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
5 ms |
600 KB |
Output is correct |
5 |
Correct |
5 ms |
676 KB |
Output is correct |
6 |
Correct |
5 ms |
608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
2 ms |
344 KB |
Output is correct |
19 |
Correct |
2 ms |
348 KB |
Output is correct |
20 |
Correct |
2 ms |
348 KB |
Output is correct |
21 |
Correct |
2 ms |
348 KB |
Output is correct |
22 |
Correct |
2 ms |
348 KB |
Output is correct |
23 |
Correct |
3 ms |
348 KB |
Output is correct |
24 |
Correct |
2 ms |
348 KB |
Output is correct |
25 |
Correct |
5 ms |
600 KB |
Output is correct |
26 |
Correct |
5 ms |
676 KB |
Output is correct |
27 |
Correct |
5 ms |
608 KB |
Output is correct |
28 |
Correct |
8 ms |
604 KB |
Output is correct |
29 |
Correct |
7 ms |
604 KB |
Output is correct |
30 |
Correct |
6 ms |
600 KB |
Output is correct |
31 |
Correct |
6 ms |
604 KB |
Output is correct |
32 |
Correct |
8 ms |
568 KB |
Output is correct |
33 |
Correct |
9 ms |
348 KB |
Output is correct |
34 |
Correct |
6 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
604 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Execution timed out |
1075 ms |
15960 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
2 ms |
344 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
348 KB |
Output is correct |
14 |
Correct |
2 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
348 KB |
Output is correct |
16 |
Correct |
3 ms |
348 KB |
Output is correct |
17 |
Correct |
2 ms |
348 KB |
Output is correct |
18 |
Execution timed out |
1075 ms |
15960 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
604 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
5 ms |
600 KB |
Output is correct |
5 |
Correct |
5 ms |
676 KB |
Output is correct |
6 |
Correct |
5 ms |
608 KB |
Output is correct |
7 |
Execution timed out |
1075 ms |
15960 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
2 ms |
344 KB |
Output is correct |
19 |
Correct |
2 ms |
348 KB |
Output is correct |
20 |
Correct |
2 ms |
348 KB |
Output is correct |
21 |
Correct |
2 ms |
348 KB |
Output is correct |
22 |
Correct |
2 ms |
348 KB |
Output is correct |
23 |
Correct |
3 ms |
348 KB |
Output is correct |
24 |
Correct |
2 ms |
348 KB |
Output is correct |
25 |
Correct |
5 ms |
600 KB |
Output is correct |
26 |
Correct |
5 ms |
676 KB |
Output is correct |
27 |
Correct |
5 ms |
608 KB |
Output is correct |
28 |
Correct |
8 ms |
604 KB |
Output is correct |
29 |
Correct |
7 ms |
604 KB |
Output is correct |
30 |
Correct |
6 ms |
600 KB |
Output is correct |
31 |
Correct |
6 ms |
604 KB |
Output is correct |
32 |
Correct |
8 ms |
568 KB |
Output is correct |
33 |
Correct |
9 ms |
348 KB |
Output is correct |
34 |
Correct |
6 ms |
600 KB |
Output is correct |
35 |
Execution timed out |
1075 ms |
15960 KB |
Time limit exceeded |
36 |
Halted |
0 ms |
0 KB |
- |