Submission #980588

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
980588	2024-05-12T09:04:44 Z	vjudge1	Rainforest Jumps (APIO21_jumps)	C++17	Compilation error	0 ms	0 KB

jumps

#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100, INF = 1e9;
vector<int> v[N];
int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
queue<int> q;

void bfs() {
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto to : v[cur]) {
            if (dist[to] != INF)
                continue;
            dist[to] = dist[cur] + 1;
            q.push(to);
        }
    }
}

void dfs(int x) {
    visited[x] = 1;
    tin[x] = ++tt;
    for (auto to : v[x]) {
        if (visited[to])
            continue;
        r[to] = r[x] + 1;
        dfs(to);
    }
    tout[x] = tt;
}

void init(int N, vector<int> H) {
    vector<pair<int, int>> ord(N);
    set<int> s;
    for (int i = 0; i < N; i++) {
        ord[i].first = H[i];
        ord[i].second = i;
    }
    n = N;
    sort(ord.begin(), ord.end());
    reverse(ord.begin(), ord.end());
    vector<int> todo;
    for (int i = 0; i < N; i++) {
        todo.clear();
        while (true) {
            todo.push_back(ord[i].second);
            auto l = s.lower_bound(ord[i].second);
            if (l != s.end()) {
              v[ord[i].second].push_back(*l);
              // cout << ord[i].second << " " << *l << "\n";
            }
            if (l != s.begin()) {
              --l;
              v[ord[i].second].push_back(*l);
              // cout << ord[i].second << " " << *l << "\n";
            }
            if (i + 1 < N && ord[i].first == ord[i + 1].first) {
              i++;
              continue;
            }
            break;
        }
        for (auto it : todo)
            s.insert(it);
    }
    reverse(ord.begin(), ord.end());
    for (auto i : ord) {
        if (!visited[i.second]) {
            dfs(i.second);
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    if (A == B && C == D) {
        if (tin[A] <= tin[C] && tout[A] >= tout[C])
            return r[C] - r[A];
        return -1;
    }
    int res = INF;
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
    }
    for (int i = A; i <= B; i++) {
        dist[i] = 0;
        q.push(i);
    }
    bfs();
    for (int i = C; i <= D; i++) {
        res = min(res, dist[i]);
    }
    return (res == INF ? -1 : res);
}
#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100, INF = 1e9;
vector<int> v[N];
int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
queue<int> q;

void bfs() {
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto to : v[cur]) {
            if (dist[to] != INF)
                continue;
            dist[to] = dist[cur] + 1;
            q.push(to);
        }
    }
}

void dfs(int x) {
    visited[x] = 1;
    tin[x] = ++tt;
    for (auto to : v[x]) {
        if (visited[to])
            continue;
        r[to] = r[x] + 1;
        dfs(to);
    }
    tout[x] = tt;
}

void init(int N, vector<int> H) {
    vector<pair<int, int>> ord(N);
    set<int> s;
    for (int i = 0; i < N; i++) {
        ord[i].first = H[i];
        ord[i].second = i;
    }
    n = N;
    sort(ord.begin(), ord.end());
    reverse(ord.begin(), ord.end());
    vector<int> todo;
    for (int i = 0; i < N; i++) {
        todo.clear();
        while (true) {
            todo.push_back(ord[i].second);
            auto l = s.lower_bound(ord[i].second);
            if (l != s.end()) {
              v[ord[i].second].push_back(*l);
              // cout << ord[i].second << " " << *l << "\n";
            }
            if (l != s.begin()) {
              --l;
              v[ord[i].second].push_back(*l);
              // cout << ord[i].second << " " << *l << "\n";
            }
            if (i + 1 < N && ord[i].first == ord[i + 1].first) {
              i++;
              continue;
            }
            break;
        }
        for (auto it : todo)
            s.insert(it);
    }
    reverse(ord.begin(), ord.end());
    for (auto i : ord) {
        if (!visited[i.second]) {
            dfs(i.second);
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    if (A == B && C == D) {
        if (tin[A] <= tin[C] && tout[A] >= tout[C])
            return r[C] - r[A];
        return -1;
    }
    int res = INF;
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
    }
    for (int i = A; i <= B; i++) {
        dist[i] = 0;
        q.push(i);
    }
    bfs();
    for (int i = C; i <= D; i++) {
        res = min(res, dist[i]);
    }
    return (res == INF ? -1 : res);
}

Compilation message

jumps.cpp:101:11: error: redefinition of 'const int N'
  101 | const int N = 2e5 + 100, INF = 1e9;
      |           ^
jumps.cpp:5:11: note: 'const int N' previously defined here
    5 | const int N = 2e5 + 100, INF = 1e9;
      |           ^
jumps.cpp:101:26: error: redefinition of 'const int INF'
  101 | const int N = 2e5 + 100, INF = 1e9;
      |                          ^~~
jumps.cpp:5:26: note: 'const int INF' previously defined here
    5 | const int N = 2e5 + 100, INF = 1e9;
      |                          ^~~
jumps.cpp:102:13: error: redefinition of 'std::vector<int> v [200100]'
  102 | vector<int> v[N];
      |             ^
jumps.cpp:6:13: note: 'std::vector<int> v [200100]' previously declared here
    6 | vector<int> v[N];
      |             ^
jumps.cpp:103:5: error: redefinition of 'int dist [200100]'
  103 | int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
      |     ^~~~
jumps.cpp:7:5: note: 'int dist [200100]' previously declared here
    7 | int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
      |     ^~~~
jumps.cpp:103:14: error: redefinition of 'int n'
  103 | int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
      |              ^
jumps.cpp:7:14: note: 'int n' previously declared here
    7 | int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
      |              ^
jumps.cpp:103:17: error: redefinition of 'int tin [200100]'
  103 | int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
      |                 ^~~
jumps.cpp:7:17: note: 'int tin [200100]' previously declared here
    7 | int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
      |                 ^~~
jumps.cpp:103:25: error: redefinition of 'int tout [200100]'
  103 | int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
      |                         ^~~~
jumps.cpp:7:25: note: 'int tout [200100]' previously declared here
    7 | int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
      |                         ^~~~
jumps.cpp:103:34: error: redefinition of 'int tt'
  103 | int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
      |                                  ^~
jumps.cpp:7:34: note: 'int tt' previously declared here
    7 | int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
      |                                  ^~
jumps.cpp:103:38: error: redefinition of 'int r [200100]'
  103 | int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
      |                                      ^
jumps.cpp:7:38: note: 'int r [200100]' previously declared here
    7 | int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
      |                                      ^
jumps.cpp:103:44: error: redefinition of 'int visited [200100]'
  103 | int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
      |                                            ^~~~~~~
jumps.cpp:7:44: note: 'int visited [200100]' previously declared here
    7 | int dist[N], n, tin[N], tout[N], tt, r[N], visited[N];
      |                                            ^~~~~~~
jumps.cpp:104:12: error: redefinition of 'std::queue<int> q'
  104 | queue<int> q;
      |            ^
jumps.cpp:8:12: note: 'std::queue<int> q' previously declared here
    8 | queue<int> q;
      |            ^
jumps.cpp:106:6: error: redefinition of 'void bfs()'
  106 | void bfs() {
      |      ^~~
jumps.cpp:10:6: note: 'void bfs()' previously defined here
   10 | void bfs() {
      |      ^~~
jumps.cpp:119:6: error: redefinition of 'void dfs(int)'
  119 | void dfs(int x) {
      |      ^~~
jumps.cpp:23:6: note: 'void dfs(int)' previously defined here
   23 | void dfs(int x) {
      |      ^~~
jumps.cpp:131:6: error: redefinition of 'void init(int, std::vector<int>)'
  131 | void init(int N, vector<int> H) {
      |      ^~~~
jumps.cpp:35:6: note: 'void init(int, std::vector<int>)' previously defined here
   35 | void init(int N, vector<int> H) {
      |      ^~~~
jumps.cpp:173:5: error: redefinition of 'int minimum_jumps(int, int, int, int)'
  173 | int minimum_jumps(int A, int B, int C, int D) {
      |     ^~~~~~~~~~~~~
jumps.cpp:77:5: note: 'int minimum_jumps(int, int, int, int)' previously defined here
   77 | int minimum_jumps(int A, int B, int C, int D) {
      |     ^~~~~~~~~~~~~