This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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[v] < now) 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 = 0; i < F.size(); i++) tree[F[i]].push_back(i + 1);
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 0;
}
Compilation message (stderr)
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 = 0; i < F.size(); i++) tree[F[i]].push_back(i + 1);
| ~~^~~~~~~~~~
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |