Submission #1083033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083033		Seungni	September (APIO24_september)	C++17	45 / 100	183 ms	26696 KiB

september

#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);
    
    vector<int> p(N + 5);
    for (int i = 0; i < N - 1; i++) p[S[0][i]] = dist[0][i];
    
    for (int i = 0; i < S.size(); i++) {
        vector<int> now(N + 5);
        int m = 1e9;
        for (int j = N - 2; j >= 0; j--) now[j] = min(min(dist[i][j], p[S[i][j]]), m), m = min(m, now[j]);
        int v = 1;
        p[S[i][0]] = v;
        for (int j = 1; j < N - 1; j++) {
            if (now[j] != now[j - 1]) v++;
            p[S[i][j]] = v;
        }
    }
    
    int ret = 0;
    for (int i = 1; i < N; i++) ret = max(ret, p[i]);
    
    return ret;
}

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 = 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:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i = 0; i < S.size(); i++) {
      |                     ~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 0 / 5
• Subtask 6: 0 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16