QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #308232 | #6645. 百合 | ckiseki# | Compile Error | / | / | C++20 | 1.6kb | 2024-01-19 19:27:10 | 2024-01-19 19:27:10 |
Judging History
answer
#pragma GCC optimize("Ofast")
#pragma GCC target("arch=skylake")
#include <bits/stdc++.h>
using namespace std;
constexpr int B = 6;
constexpr int K = 17;
constexpr int C = K - B;
constexpr int B2 = 1 << B;
constexpr int C2 = 1 << C;
constexpr int N = 1 << K;
constexpr int64_t INF = 1LL << 60;
vector<int> s[B2][C2][K + 1];
int a[K + 1];
vector<pair<int, int>> g[N];
int64_t d[N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int k, m, S;
cin >> k >> m >> S;
for (int i = 1; i <= k; ++i)
cin >> a[i];
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
const int n = 1 << k;
fill_n(d, n, INF);
for (int i = 0; i < B2; ++i) {
for (int j = 0; j < C2; ++j) {
for (int jj = 0; jj < C2; ++jj) {
int c = popcount(uint32_t(j) ^ uint32_t(jj));
s[i][j][c].push_back((i << C) + jj);
}
}
}
priority_queue<pair<int64_t, int>> pq;
pq.emplace(d[S] = 0, S);
while (not pq.empty()) {
auto [l, u] = pq.top();
pq.pop();
if (l != -d[u])
continue;
for (auto [v, w] : g[u]) {
if (d[u] + w < d[v]) {
pq.emplace(-(d[v] = d[u] + w), v);
}
}
const int j = u & (C2 - 1);
for (int i = 0; i < B2; ++i) {
for (int c = 0; c <= C; ++c) {
int cost = a[popcount(uint32_t(i) ^ uint32_t(u >> C)) + c];
for (int v : s[i][j][c]) {
if (d[u] + cost < d[v]) {
pq.emplace(-(d[v] = d[u] + cost), v);
}
}
s[i][j][c].clear();
}
}
}
for (int i = 0; i < n; ++i)
cout << d[i] << " \n"[i + 1 == n];
return 0;
}
Details
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/gthr.h:148,
from /usr/include/c++/13/ext/atomicity.h:35,
from /usr/include/c++/13/bits/ios_base.h:39,
from /usr/include/c++/13/streambuf:43,
from /usr/include/c++/13/bits/streambuf_iterator.h:35,
from /usr/include/c++/13/iterator:66,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54,
from answer.code:3:
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:121:1:...