Submission #259171

#TimeUsernameProblemLanguageResultExecution timeMemory
259171imeimi2000한자 끝말잇기 (JOI14_kanji)C++17
100 / 100
216 ms27360 KiB
#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); } }

Compilation message (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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...