Submission #745943

#	Time	Username	Problem	Language	Result	Execution time	Memory
745943		nguyentunglam	Railway Trip 2 (JOI22_ho_t4)	C++17	0 / 100	109 ms	155616 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 5010;
int trace[N], d[N], f[N][N];
bool adj[N][N];
int n, m, k;
void bfs(int s) {
    for(int i = 1; i <= n; i++) trace[i] = d[i] = 0;
    queue<int> q;
    q.push(s); trace[s] = -1; d[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for(int v = 1; v <= n; v++) if (adj[u][v] && !trace[v]) {
            d[v] = d[u] + 1;
            trace[v] = u;
            q.push(v);
        }
    }
    for(int j = s + 2; j <= n; j++) if (d[j] < d[j - 1]) assert(0);
    for(int j = s - 2; j >= 1; j--) if (d[j] < d[j + 1]) assert(0);
    for(int j = 1; j <= n; j++) f[s][j] = d[j] - 1;
}
int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    cin >> n >> k >> m;
    for(int i = 1; i <= m; i++) {
        int a, b; cin >> a >> b;
        if (a < b) for(int j = a; j <= min(a + k - 1, b - 1); j++) for(int k = j + 1; k <= b; k++) adj[j][k] = 1;
        else for(int j = a; j >= max(a - k + 1, b + 1); j--) for(int k = j - 1; k >= b; k--) adj[j][k] = 1;
    }
    for(int i = 1; i <= n; i++) bfs(i);
    int q; cin >> q;
    while (q--) {
        int s, t; cin >> s >> t;
        cout << f[s][t] << endl;
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:31:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:32:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:35:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:36:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13