이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "Annalib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long llong;
typedef pair<llong, llong> pll;
static void dijkstra(vector<pll> edge[], llong dist[], int prev[], int s) {
priority_queue<pll> pq;
pq.emplace(dist[s] = 0, s);
while (!pq.empty()) {
auto [d, x] = pq.top(); pq.pop();
d = -d;
if (dist[x] != d) continue;
for (auto [i, c] : edge[x]) {
if (d + c < dist[i]) pq.emplace(-(dist[i] = d + c), i), prev[i] = x;
}
}
}
const static llong inf = 4e18;
static vector<pll> edge[300];
static llong distK[6][300], distQ[60][300];
static int par[300], a;
static llong get_dist(int i, int x, int k) {
if (k) return distQ[i][a] + distK[k][x];
return distQ[i][x];
}
void Anna(int n, int m, int A[], int B[], llong C[], int q, int S[], int T[], int k, int U[]) {
a = A[U[0]];
for (int i = 0; i < m; ++i) {
bool in = 0;
for (int j = 0; j < k; ++j) if (i == U[j]) in = 1;
if (!in) edge[A[i]].emplace_back(B[i], C[i]);
}
memset(distQ, 0x3f, sizeof(distQ));
for (int i = 0; i < q; ++i) {
dijkstra(edge, distQ[i], par, S[i]);
}
memset(distK, 0x3f, sizeof(distK));
for (int i = 1; i <= k; ++i) {
dijkstra(edge, distK[i], par, B[U[i - 1]]);
for (int j = 0; j < n; ++j) distK[i][j] += C[U[i - 1]];
}
vector<int> G[6];
for (int i = 0; i < q; ++i) G[0].push_back(i);
unsigned long long ret = 0;
vector<unsigned> mul, add;
for (int w = 1; w <= k; ++w) {
for (int i = 0; i < w; ++i) {
vector<int> O, N;
for (int g : G[i]) {
if (distQ[g][a] >= inf || distK[w][T[g]] >= inf) O.push_back(g);
else if (!i && distQ[g][T[g]] >= inf || i && (distQ[g][a] >= inf || distK[i][T[g]] >= inf)) N.push_back(g);
else (get_dist(g, T[g], i) <= get_dist(g, T[g], w) ? O : N).push_back(g);
}
mul.push_back(G[i].size() + 1u);
add.push_back(O.size());
G[i] = O;
for (int j : N) G[w].push_back(j);
}
}
for (int i = mul.size(); i--; ) ret = ret * mul[i] + add[i];
while (ret) Tap(ret & 1u), ret >>= 1;
}
#include "Brunolib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long llong;
typedef pair<llong, llong> pll;
static void dijkstra(vector<pll> edge[], llong dist[], int prev[], int s) {
priority_queue<pll> pq;
pq.emplace(dist[s] = 0, s);
while (!pq.empty()) {
auto [d, x] = pq.top(); pq.pop();
d = -d;
if (dist[x] != d) continue;
for (auto [i, c] : edge[x]) {
if (d + c < dist[i]) pq.emplace(-(dist[i] = d + c), i), prev[i] = x;
}
}
}
const static llong inf = 4e18;
static vector<pll> edge[300];
static llong distK[6][300], distQ[60][300];
static int parK[6][300], parQ[60][300], a;
static llong get_dist(int i, int x, int k) {
if (k) return distQ[i][a] + distK[k][x];
return distQ[i][x];
}
void Bruno(int n, int m, int A[], int B[], llong C[], int q, int S[], int T[], int k, int U[], int l, int V[]) {
unsigned long long ret = 0;
while (l--) ret = ret << 1 | unsigned(V[l]);
a = A[U[0]];
map<pll, int> idx;
for (int i = 0; i < m; ++i) {
idx[pll(A[i], B[i])] = i;
if (C[i] != -1) edge[A[i]].emplace_back(B[i], C[i]);
}
memset(distQ, 0x3f, sizeof(distQ));
for (int i = 0; i < q; ++i) {
dijkstra(edge, distQ[i], parQ[i], S[i]);
}
memset(distK, 0x3f, sizeof(distK));
for (int i = 1; i <= k; ++i) {
dijkstra(edge, distK[i], parK[i], B[U[i - 1]]);
}
vector<int> G[6];
for (int i = 0; i < q; ++i) G[0].push_back(i);
for (int w = 1; w <= k; ++w) {
for (int i = 0; i < w; ++i) {
int cnt = ret % (G[i].size() + 1u);
ret /= G[i].size() + 1u;
vector<int> nG, O, N;
for (int g : G[i]) {
if (distQ[g][a] >= inf || distK[w][T[g]] >= inf) O.push_back(g), --cnt;
else if (!i && distQ[g][T[g]] >= inf || i && (distQ[g][a] >= inf || distK[i][T[g]] >= inf)) N.push_back(g);
else nG.push_back(g);
}
sort(nG.begin(), nG.end(), [&](int a, int b) {
return get_dist(a, T[a], i) - get_dist(a, T[a], w) < get_dist(b, T[b], i) - get_dist(b, T[b], w);
});
for (int j = 0; j < int(nG.size()); ++j) (j < cnt ? O : N).push_back(nG[j]);
G[i] = O;
for (int j : N) G[w].push_back(j);
}
}
int res[60];
for (int i = 0; i <= k; ++i) for (int j : G[i]) res[j] = i;
for (int i = 0; i < q; ++i) {
int x = T[i];
vector<int> path;
if (res[i]) {
for (; x != B[U[res[i] - 1]]; x = parK[res[i]][x]) path.push_back(idx[pll(parK[res[i]][x], x)]);
path.push_back(U[res[i] - 1]);
x = a;
}
for (; x != S[i]; x = parQ[i][x]) path.push_back(idx[pll(parQ[i][x], x)]);
for (int j = path.size(); j--; ) Answer(path[j]);
Answer(-1);
}
}
컴파일 시 표준 에러 (stderr) 메시지
Anna.cpp: In function 'void Anna(int, int, int*, int*, llong*, int, int*, int*, int, int*)':
Anna.cpp:56:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
else if (!i && distQ[g][T[g]] >= inf || i && (distQ[g][a] >= inf || distK[i][T[g]] >= inf)) N.push_back(g);
~~~^~~~~~~~~~~~~~~~~~~~~~~~
Bruno.cpp: In function 'void Bruno(int, int, int*, int*, llong*, int, int*, int*, int, int*, int, int*)':
Bruno.cpp:57:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
else if (!i && distQ[g][T[g]] >= inf || i && (distQ[g][a] >= inf || distK[i][T[g]] >= inf)) N.push_back(g);
~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |