oj.uz

Submission #1083019

# Submission time Handle Problem Language Result Execution time Memory
1083019 2024-09-02T09:54:29 Z Seungni September (APIO24_september) C++17
0 / 100
 3 ms 5460 KB 
#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

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++) {
      |                     ~~^~~~~~~~~~

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -