| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 259094 |
2020-08-07T07:35:27 Z |
강태규(#5095) |
한자 끝말잇기 (JOI14_kanji) |
C++17 |
|
1000 ms |
262148 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;
}
}
}
static vector<pll> edge[300];
static llong dist[300];
static int par[300], V[160], N[160];
static void add(int x) {
memcpy(N, V, sizeof(N));
memset(V, 0, sizeof(N));
for (int i = 0; i < 160; ++i) {
if (i - 2 >= 0) V[i] += N[i - 2];
if (i - 1 >= 0) V[i] += N[i - 1];
if (V[i] >= 2) V[i + 1] += V[i] / 2, V[i] %= 2;
}
for (int i = 0; i < 3; ++i) {
if (x & 1) ++V[i];
x >>= 1;
}
for (int i = 0; i < 160; ++i) if (V[i] >= 2) V[i + 1] += V[i] / 2, V[i] %= 2;
}
void Anna(int n, int m, int A[], int B[], llong C[], int q, int S[], int T[], int k, int U[]) {
for (int i = 0; i < m; ++i) edge[A[i]].emplace_back(B[i], C[i]);
for (int i = 0; i < q; ++i) {
memset(dist, 0x3f, sizeof(dist));
dijkstra(edge, dist, par, S[i]);
int idx = 0;
for (int x = T[i]; x != S[i]; x = par[x]) if (par[x] == A[U[0]]) {
for (int j = 0; j < k; ++j) if (x == B[U[j]]) idx = j + 1;
}
add(idx);
}
for (int i = 0; i < 160; ++i) Tap(V[i]);
}
#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;
}
}
}
static vector<pll> edge[300];
static llong dist[300];
static int par[300], * V;
static int sub() {
int val[8] = {};
for (int i = 0; i < 160; ++i) {
if (V[i]) val[i / 20] |= 1 << i % 20;
}
int ret = 0;
for (int i = 8; i--; ) ret = (ret << 20 | val[i]) % 6;
for (int i = 0; i < 3; ++i) {
if ((ret >> i) & 1) --V[i];
}
for (int i = 0; i < 160; ++i) {
if (V[i] < 0) V[i] += 2, --V[i + 1];
}
return ret;
}
void Bruno(int n, int m, int A[], int B[], llong C[], int q, int S[], int T[], int k, int U[], int, int X[]) {
V = X;
map<pll, int> ei;
for (int i = 0; i < m; ++i) {
if (C[i] == -1) continue;
edge[A[i]].emplace_back(B[i], C[i]);
ei[pll(A[i], B[i])] = i;
}
int idxes[100];
for (int i = q; i--; ) {
idxes[i] = sub();
}
for (int i = 0; i < q; ++i) {
int idx = idxes[i];
int mid1 = idx ? A[U[0]] : S[i], mid2 = idx ? B[U[idx - 1]] : S[i];
vector<int> path;
memset(dist, 0x3f, sizeof(dist));
dijkstra(edge, dist, par, mid2);
for (int x = T[i]; x != mid2; x = par[x]) path.push_back(ei[pll(par[x], x)]);
if (idx) path.push_back(U[idx - 1]);
memset(dist, 0x3f, sizeof(dist));
dijkstra(edge, dist, par, S[i]);
for (int x = mid1; x != S[i]; x = par[x]) path.push_back(ei[pll(par[x], x)]);
for (int j = path.size(); j--; ) Answer(path[j]);
Answer(-1);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4564 KB |
Output isn't correct - Wrong Answer [9] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
775 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
787 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
784 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
800 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Incorrect |
8 ms |
4772 KB |
Output isn't correct - Wrong Answer [7] |
| 3 |
Execution timed out |
1069 ms |
136312 KB |
Time limit exceeded |
| 4 |
Runtime error |
743 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Incorrect |
9 ms |
4696 KB |
Output isn't correct - Wrong Answer [9] |
| 6 |
Runtime error |
755 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Incorrect |
11 ms |
5196 KB |
Output isn't correct - Wrong Answer [9] |
| 8 |
Incorrect |
11 ms |
5036 KB |
Output isn't correct - Wrong Answer [9] |
| 9 |
Incorrect |
9 ms |
5168 KB |
Output isn't correct - Wrong Answer [9] |
| 10 |
Incorrect |
8 ms |
5180 KB |
Output isn't correct - Wrong Answer [9] |
| 11 |
Incorrect |
9 ms |
5156 KB |
Output isn't correct - Wrong Answer [9] |
| 12 |
Correct |
11 ms |
4908 KB |
Output isn't correct - L = 160 |
| 13 |
Correct |
223 ms |
22804 KB |
Output isn't correct - L = 160 |
| 14 |
Incorrect |
11 ms |
4820 KB |
Output isn't correct - Wrong Answer [7] |
| 15 |
Runtime error |
847 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 |
Incorrect |
16 ms |
5084 KB |
Output isn't correct - Wrong Answer [9] |
| 17 |
Incorrect |
23 ms |
5608 KB |
Output isn't correct - Wrong Answer [9] |
| 18 |
Incorrect |
34 ms |
6376 KB |
Output isn't correct - Wrong Answer [9] |
| 19 |
Execution timed out |
1097 ms |
136224 KB |
Time limit exceeded |
| 20 |
Correct |
27 ms |
6936 KB |
Output isn't correct - L = 160 |
| 21 |
Correct |
40 ms |
6888 KB |
Output isn't correct - L = 160 |
| 22 |
Incorrect |
8 ms |
5172 KB |
Output isn't correct - Wrong Answer [9] |
| 23 |
Incorrect |
8 ms |
5052 KB |
Output isn't correct - Wrong Answer [9] |
| 24 |
Incorrect |
9 ms |
4924 KB |
Output isn't correct - Wrong Answer [9] |
