| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 259170 |
2020-08-07T09:45:55 Z |
강태규(#5095) |
한자 끝말잇기 (JOI14_kanji) |
C++17 |
|
202 ms |
26188 KB |
#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(j);
Answer(-1);
}
}
Compilation message
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 |
| 1 |
Incorrect |
6 ms |
4920 KB |
Output isn't correct - Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5156 KB |
Output isn't correct - Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
5168 KB |
Output isn't correct - Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
5168 KB |
Output isn't correct - Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5164 KB |
Output isn't correct - Wrong Answer [7] |
| 2 |
Incorrect |
8 ms |
5316 KB |
Output isn't correct - Wrong Answer [7] |
| 3 |
Incorrect |
8 ms |
5184 KB |
Output isn't correct - Wrong Answer [7] |
| 4 |
Incorrect |
8 ms |
5168 KB |
Output isn't correct - Wrong Answer [7] |
| 5 |
Incorrect |
8 ms |
5036 KB |
Output isn't correct - Wrong Answer [7] |
| 6 |
Incorrect |
10 ms |
5036 KB |
Output isn't correct - Wrong Answer [7] |
| 7 |
Incorrect |
10 ms |
5164 KB |
Output isn't correct - Wrong Answer [7] |
| 8 |
Incorrect |
10 ms |
5400 KB |
Output isn't correct - Wrong Answer [7] |
| 9 |
Incorrect |
7 ms |
5436 KB |
Output isn't correct - Wrong Answer [7] |
| 10 |
Incorrect |
8 ms |
5436 KB |
Output isn't correct - Wrong Answer [7] |
| 11 |
Incorrect |
8 ms |
5308 KB |
Output isn't correct - Wrong Answer [7] |
| 12 |
Incorrect |
10 ms |
5292 KB |
Output isn't correct - Wrong Answer [7] |
| 13 |
Incorrect |
202 ms |
26188 KB |
Output isn't correct - Wrong Answer [7] |
| 14 |
Incorrect |
8 ms |
5176 KB |
Output isn't correct - Wrong Answer [7] |
| 15 |
Incorrect |
9 ms |
5172 KB |
Output isn't correct - Wrong Answer [7] |
| 16 |
Incorrect |
15 ms |
5508 KB |
Output isn't correct - Wrong Answer [7] |
| 17 |
Incorrect |
20 ms |
5964 KB |
Output isn't correct - Wrong Answer [7] |
| 18 |
Incorrect |
28 ms |
6992 KB |
Output isn't correct - Wrong Answer [7] |
| 19 |
Incorrect |
7 ms |
4936 KB |
Output isn't correct - Wrong Answer [7] |
| 20 |
Incorrect |
26 ms |
7796 KB |
Output isn't correct - Wrong Answer [7] |
| 21 |
Incorrect |
38 ms |
7656 KB |
Output isn't correct - Wrong Answer [7] |
| 22 |
Incorrect |
8 ms |
5536 KB |
Output isn't correct - Wrong Answer [7] |
| 23 |
Incorrect |
7 ms |
5308 KB |
Output isn't correct - Wrong Answer [7] |
| 24 |
Incorrect |
8 ms |
5516 KB |
Output isn't correct - Wrong Answer [7] |
