#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#include "september.h"
#include <vector>
int n;
vector<int> tree[100005];
vector<pii> graph[100005];
int dp[100005];
void init() {
for (int i = 0; i < n; i++) tree[i].clear(), graph[i].clear();
return;
}
void DFS(int node) {
for (int next: tree[node]) {
DFS(next);
dp[node] = max(dp[node], dp[next]);
}
}
void make_graph(vector<int> &arr) {
for (int i = 0; i < n - 1; i++) graph[i].clear();
for (int i = 0; i < n - 2; i++) graph[i].push_back({i + 1, 1});
for (int i = 1; i < n - 1; i++) graph[i].push_back({i - 1, 0});
vector<int> pos(n + 1);
for (int i = 0; i < arr.size(); i++) pos[arr[i]] = i;
for (int i = 1; i < n; i++) dp[i] = pos[i];
DFS(0);
for (int i = 1; i < n; i++) {
graph[pos[i]].push_back({dp[i], 0});
}
}
void Dijkstra(int start, vector<int> &dist) {
fill(dist.begin(), dist.end(), 1e9);
dist[start] = 1;
priority_queue<pii, vector<pii>, greater<>> pq;
pq.push({1, start});
while (pq.size()) {
pii t = pq.top();
pq.pop();
int now = t.second, v = t.first;
if (dist[now] < v) continue;
for (auto &[next, cost]: graph[now]) {
if (dist[next] > v + cost) {
dist[next] = v + cost;
pq.push({v + cost, next});
}
}
}
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
n = N;
init();
for (int i = 1; i < F.size(); i++) tree[F[i]].push_back(i);
vector<int> dist[5];
for (int i = 0; i < S.size(); i++) {
dist[i].resize(N + 5);
make_graph(S[i]);
Dijkstra(0, dist[i]);
}
vector<int> ans(N + 5, 1e9);
for (int i = 0; i < S.size(); i++) {
vector<int> now(N + 5);
for (int j = 0; j < N - 1; j++) now[S[i][j]] = dist[i][j];
for (int j = 1; j < N; j++) ans[j] = min(ans[j], now[j]);
}
int ret = 0;
for (int i = 1; i < N; i++) ret = max(ret, ans[i]);
return ret;
}
Compilation message
september.cpp: In function 'void make_graph(std::vector<int>&)':
september.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int i = 0; i < arr.size(); i++) pos[arr[i]] = i;
| ~~^~~~~~~~~~~~
september.cpp: In function 'int solve(int, int, std::vector<int>, std::vector<std::vector<int> >)':
september.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 1; i < F.size(); i++) tree[F[i]].push_back(i);
| ~~^~~~~~~~~~
september.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int i = 0; i < S.size(); i++) {
| ~~^~~~~~~~~~
september.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i = 0; i < S.size(); i++) {
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 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 |
5380 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 |
2 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 |
5380 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 |
Incorrect |
2 ms |
5208 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5468 KB |
Output is correct |
2 |
Correct |
2 ms |
5468 KB |
Output is correct |
3 |
Correct |
2 ms |
5468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 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 |
5380 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 |
2 ms |
5468 KB |
Output is correct |
9 |
Correct |
2 ms |
5468 KB |
Output is correct |
10 |
Correct |
2 ms |
5468 KB |
Output is correct |
11 |
Correct |
2 ms |
5468 KB |
Output is correct |
12 |
Correct |
2 ms |
5468 KB |
Output is correct |
13 |
Correct |
2 ms |
5392 KB |
Output is correct |
14 |
Correct |
2 ms |
5468 KB |
Output is correct |
15 |
Correct |
1 ms |
5392 KB |
Output is correct |
16 |
Correct |
1 ms |
5468 KB |
Output is correct |
17 |
Correct |
2 ms |
5468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5468 KB |
Output is correct |
2 |
Correct |
2 ms |
5468 KB |
Output is correct |
3 |
Correct |
2 ms |
5468 KB |
Output is correct |
4 |
Incorrect |
2 ms |
5468 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 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 |
5380 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 |
Incorrect |
2 ms |
5208 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5468 KB |
Output is correct |
2 |
Correct |
2 ms |
5468 KB |
Output is correct |
3 |
Correct |
2 ms |
5468 KB |
Output is correct |
4 |
Correct |
148 ms |
28032 KB |
Output is correct |
5 |
Correct |
144 ms |
28096 KB |
Output is correct |
6 |
Correct |
140 ms |
28028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 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 |
5380 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 |
2 ms |
5468 KB |
Output is correct |
9 |
Correct |
2 ms |
5468 KB |
Output is correct |
10 |
Correct |
2 ms |
5468 KB |
Output is correct |
11 |
Correct |
2 ms |
5468 KB |
Output is correct |
12 |
Correct |
2 ms |
5468 KB |
Output is correct |
13 |
Correct |
2 ms |
5392 KB |
Output is correct |
14 |
Correct |
2 ms |
5468 KB |
Output is correct |
15 |
Correct |
1 ms |
5392 KB |
Output is correct |
16 |
Correct |
1 ms |
5468 KB |
Output is correct |
17 |
Correct |
2 ms |
5468 KB |
Output is correct |
18 |
Correct |
148 ms |
28032 KB |
Output is correct |
19 |
Correct |
144 ms |
28096 KB |
Output is correct |
20 |
Correct |
140 ms |
28028 KB |
Output is correct |
21 |
Correct |
169 ms |
23204 KB |
Output is correct |
22 |
Correct |
171 ms |
23156 KB |
Output is correct |
23 |
Correct |
178 ms |
24172 KB |
Output is correct |
24 |
Correct |
162 ms |
24276 KB |
Output is correct |
25 |
Correct |
171 ms |
23100 KB |
Output is correct |
26 |
Correct |
159 ms |
23156 KB |
Output is correct |
27 |
Correct |
161 ms |
24264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5468 KB |
Output is correct |
2 |
Correct |
2 ms |
5468 KB |
Output is correct |
3 |
Correct |
2 ms |
5468 KB |
Output is correct |
4 |
Incorrect |
2 ms |
5468 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 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 |
5380 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 |
Incorrect |
2 ms |
5208 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |