제출 #617608

#제출 시각아이디문제언어결과실행 시간메모리
617608qwerasdfzxclEscape Route (JOI21_escape_route)C++17
컴파일 에러
0 ms0 KiB
#include "escape_route.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 4e18; pair<ll, ll> adj[101][101]; int n, m, q, idx[101][9090]; ll MOD, dist0[101][101], dist[101][101][9090], sz[101], sz2[101][101]; pair<ll, int> ran[101][9090], DB[101][101][9090]; bool visited[101]; vector<ll> ans; void dijkstra(int s, ll t, ll dist[], bool is0){ fill(dist+1, dist+n+1, INF); fill(visited+1, visited+n+1, 0); dist[s] = t; for (int i=1;i<=n;i++){ ll mn = INF, v = -1; for (int j=1;j<=n;j++) if (!visited[j] && mn > dist[j]) mn = dist[j], v = j; if (v==-1) break; visited[v] = 1; //printf(" %d %lld\n", v, mn); for (int nxt=1;nxt<=n;nxt++) if (!visited[nxt] && adj[v][nxt].first){ auto &[l, c] = adj[v][nxt]; ll nt = mn + l; if (!is0){ if (mn>c-l) continue; } else if (mn%MOD > c-l){ nt = (mn/MOD*MOD + MOD) + l; } if (nt < dist[nxt]){ dist[nxt] = nt; } } } } void dijkINV(int s, ll t, ll dist[]){ fill(dist+1, dist+n+1, -INF); fill(visited+1, visited+n+1, 0); dist[s] = t; for (int i=1;i<=n;i++){ ll mx = -INF, v = -1; for (int j=1;j<=n;j++) if (!visited[j] && mx < dist[j]) mx = dist[j], v = j; if (v==-1) break; visited[v] = 1; for (int nxt=1;nxt<=n;nxt++) if (!visited[nxt] && adj[v][nxt].first){ auto &[l, c] = adj[v][nxt]; ll nt = mx - l; if (nt > c-l) continue; if (nt > dist[nxt]){ dist[nxt] = nt; } } } } ll distx[101], disty[101]; int Enum; void calc(int x, int y){ if (!adj[x][y].first) return; auto [l, c] = adj[x][y]; dijkINV(x, c-l, distx); dijkstra(y, c, disty, 0); ++Enum; //printf("\n %d %d (Enum = %d)\n", x, y, Enum); for (int i=1;i<=n;i++) if (distx[i] > -INF){ ran[i][sz[i]++] = {distx[i]+1, Enum}; for (int j=1;j<=n;j++) if (distx[i] > -INF && disty[j] < INF){ //printf(" %d -> %d: %lld -> %lld\n", i, j, distx[i], disty[j]); DB[i][j][sz2[i][j]++] = {disty[j] - distx[i], Enum}; } } } void init(int s){ sort(ran[s], ran[s]+sz[s]); for (int i=1;i<sz[s];i++) idx[s][ran[s][i].second] = i; for (int v=1;v<=n;v++){ //printf("\n%d %d\n", s, v); fill(dist[s][v], dist[s][v]+sz[s]+1, INF); for (int i=0;i<sz2[s][v];i++){ auto &[d, e] = DB[s][v][i]; //printf(" %lld %d(->%d)\n", d, e, idx[s][e]); dist[s][v][idx[s][e]-1] = d; } for (int i=sz[s]-1;i>=0;i--){ dist[s][v][i] = min(dist[s][v][i], dist[s][v][i+1]); //printf("%lld ", dist[s][v][i]); } //printf("\n"); } fill(dist[s][s], dist[s][s]+sz[s], 0); } std::vector<long long> calculate_necessary_time( int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B, std::vector<long long> L, std::vector<long long> C, std::vector<int> U, std::vector<int> V, std::vector<long long> T) { n = N, m = M, MOD = S, q = Q; for (int i=0;i<m;i++){ ++A[i], ++B[i]; adj[A[i]][B[i]] = make_pair(L[i], C[i]); adj[B[i]][A[i]] = make_pair(L[i], C[i]); } for (int i=1;i<=n;i++) dijkstra(i, 0, dist0[i], 1); fill(sz+1, sz+n+1, 1); for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++) calc(i, j); } for (int i=1;i<=n;i++) init(i); for (int i=0;i<q;i++){ ++U[i], ++V[i]; int pt = upper_bound(ran[U[i]], ran[U[i]]+sz[U[i]], make_pair(T[i], (int)1e9)) - ran[U[i]] - 1; //printf(" %d %d %lld -> %d\n", U[i], V[i], T[i], pt); ll ret = dist[U[i]][V[i]][pt]; for (int j=1;j<=n;j++) if (dist[U[i]][j][pt]<INF){ ret = min(ret, MOD - T[i] + dist0[j][V[i]]); } ans.push_back(ret); } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

/tmp/cc8tt3m6.o: in function `main':
grader.cpp:(.text.startup+0x1d): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x23): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x38): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x3e): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x5c): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x62): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0xf7): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x114): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x128): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x137): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x13d): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status