QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #853200 | #9732. Gathering Mushrooms | ucup-team159# | WA | 33ms | 3672kb | C++23 | 21.1kb | 2025-01-11 16:08:27 | 2025-01-11 16:08:27 |
Judging History
answer
#line 1 "ucup3-25/G/main.cpp"
#define YOSUPO_AVX2_PRAGMA
// #undef YOSUPO_LOCAL
#line 2 "/home/vscode/yosupo-library/src/yosupo/fastio.hpp"
#include <unistd.h>
#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cctype>
#include <cstdint>
#include <cstring>
#include <sstream>
#include <string>
#include <type_traits>
#include <vector>
#line 2 "/home/vscode/yosupo-library/src/yosupo/internal_type_traits.hpp"
#line 5 "/home/vscode/yosupo-library/src/yosupo/internal_type_traits.hpp"
namespace yosupo {
namespace internal {
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral =
typename std::conditional<std::is_integral<T>::value ||
internal::is_signed_int128<T>::value ||
internal::is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
template <class T>
using is_integral_t = std::enable_if_t<is_integral<T>::value>;
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace yosupo
#line 17 "/home/vscode/yosupo-library/src/yosupo/fastio.hpp"
namespace yosupo {
struct Scanner {
public:
Scanner(const Scanner&) = delete;
Scanner& operator=(const Scanner&) = delete;
Scanner(FILE* fp) : fd(fileno(fp)) { line[0] = 127; }
void read() {}
template <class H, class... T> void read(H& h, T&... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
int read_unsafe() { return 0; }
template <class H, class... T> int read_unsafe(H& h, T&... t) {
bool f = read_single(h);
if (!f) return 0;
return 1 + read_unsafe(t...);
}
int close() { return ::close(fd); }
private:
static constexpr int SIZE = 1 << 15;
int fd = -1;
std::array<char, SIZE + 1> line;
int st = 0, ed = 0;
bool eof = false;
bool read_single(std::string& ref) {
if (!skip_space()) return false;
ref = "";
while (true) {
char c = top();
if (c <= ' ') break;
ref += c;
st++;
}
return true;
}
bool read_single(double& ref) {
std::string s;
if (!read_single(s)) return false;
ref = std::stod(s);
return true;
}
template <class T,
std::enable_if_t<std::is_same<T, char>::value>* = nullptr>
bool read_single(T& ref) {
if (!skip_space<50>()) return false;
ref = top();
st++;
return true;
}
template <class T,
internal::is_signed_int_t<T>* = nullptr,
std::enable_if_t<!std::is_same<T, char>::value>* = nullptr>
bool read_single(T& sref) {
using U = internal::to_unsigned_t<T>;
if (!skip_space<50>()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
U ref = 0;
do {
ref = 10 * ref + (line[st++] & 0x0f);
} while (line[st] >= '0');
sref = neg ? -ref : ref;
return true;
}
template <class U,
internal::is_unsigned_int_t<U>* = nullptr,
std::enable_if_t<!std::is_same<U, char>::value>* = nullptr>
bool read_single(U& ref) {
if (!skip_space<50>()) return false;
ref = 0;
do {
ref = 10 * ref + (line[st++] & 0x0f);
} while (line[st] >= '0');
return true;
}
bool reread() {
if (ed - st >= 50) return true;
if (st > SIZE / 2) {
std::memmove(line.data(), line.data() + st, ed - st);
ed -= st;
st = 0;
}
if (eof) return false;
auto u = ::read(fd, line.data() + ed, SIZE - ed);
if (u == 0) {
eof = true;
line[ed] = '\0';
u = 1;
}
ed += int(u);
line[ed] = char(127);
return true;
}
char top() {
if (st == ed) {
bool f = reread();
assert(f);
}
return line[st];
}
template <int TOKEN_LEN = 0> bool skip_space() {
while (true) {
while (line[st] <= ' ') st++;
if (ed - st > TOKEN_LEN) return true;
if (st > ed) st = ed;
for (auto i = st; i < ed; i++) {
if (line[i] <= ' ') return true;
}
if (!reread()) return false;
}
}
};
struct Printer {
public:
template <char sep = ' ', bool F = false> void write() {}
template <char sep = ' ', bool F = false, class H, class... T>
void write(const H& h, const T&... t) {
if (F) write_single(sep);
write_single(h);
write<true>(t...);
}
template <char sep = ' ', class... T> void writeln(const T&... t) {
write<sep>(t...);
write_single('\n');
}
Printer(FILE* _fp) : fd(fileno(_fp)) {}
~Printer() { flush(); }
int close() {
flush();
return ::close(fd);
}
void flush() {
if (pos) {
auto res = ::write(fd, line.data(), pos);
assert(res != -1);
pos = 0;
}
}
private:
static std::array<std::array<char, 2>, 100> small;
static std::array<unsigned long long, 20> tens;
static constexpr size_t SIZE = 1 << 15;
int fd;
std::array<char, SIZE> line;
size_t pos = 0;
std::stringstream ss;
template <class T,
std::enable_if_t<std::is_same<char, T>::value>* = nullptr>
void write_single(const T& val) {
if (pos == SIZE) flush();
line[pos++] = val;
}
template <class T,
internal::is_signed_int_t<T>* = nullptr,
std::enable_if_t<!std::is_same<char, T>::value>* = nullptr>
void write_single(const T& val) {
using U = internal::to_unsigned_t<T>;
if (val == 0) {
write_single('0');
return;
}
if (pos > SIZE - 50) flush();
U uval = val;
if (val < 0) {
write_single('-');
uval = -uval;
}
write_unsigned(uval);
}
template <class U,
internal::is_unsigned_int_t<U>* = nullptr,
std::enable_if_t<!std::is_same<char, U>::value>* = nullptr>
void write_single(U uval) {
if (uval == 0) {
write_single('0');
return;
}
if (pos > SIZE - 50) flush();
write_unsigned(uval);
}
static int calc_len(uint64_t x) {
int i = ((63 - std::countl_zero(x)) * 3 + 3) / 10;
if (x < tens[i])
return i;
else
return i + 1;
}
template <class U,
internal::is_unsigned_int_t<U>* = nullptr,
std::enable_if_t<2 >= sizeof(U)>* = nullptr>
void write_unsigned(U uval) {
size_t len = calc_len(uval);
pos += len;
char* ptr = line.data() + pos;
while (uval >= 100) {
ptr -= 2;
memcpy(ptr, small[uval % 100].data(), 2);
uval /= 100;
}
if (uval >= 10) {
memcpy(ptr - 2, small[uval].data(), 2);
} else {
*(ptr - 1) = char('0' + uval);
}
}
template <class U,
internal::is_unsigned_int_t<U>* = nullptr,
std::enable_if_t<4 == sizeof(U)>* = nullptr>
void write_unsigned(U uval) {
std::array<char, 8> buf;
memcpy(buf.data() + 6, small[uval % 100].data(), 2);
memcpy(buf.data() + 4, small[uval / 100 % 100].data(), 2);
memcpy(buf.data() + 2, small[uval / 10000 % 100].data(), 2);
memcpy(buf.data() + 0, small[uval / 1000000 % 100].data(), 2);
if (uval >= 100000000) {
if (uval >= 1000000000) {
memcpy(line.data() + pos, small[uval / 100000000 % 100].data(),
2);
pos += 2;
} else {
line[pos] = char('0' + uval / 100000000);
pos++;
}
memcpy(line.data() + pos, buf.data(), 8);
pos += 8;
} else {
size_t len = calc_len(uval);
memcpy(line.data() + pos, buf.data() + (8 - len), len);
pos += len;
}
}
template <class U,
internal::is_unsigned_int_t<U>* = nullptr,
std::enable_if_t<8 == sizeof(U)>* = nullptr>
void write_unsigned(U uval) {
size_t len = calc_len(uval);
pos += len;
char* ptr = line.data() + pos;
while (uval >= 100) {
ptr -= 2;
memcpy(ptr, small[uval % 100].data(), 2);
uval /= 100;
}
if (uval >= 10) {
memcpy(ptr - 2, small[uval].data(), 2);
} else {
*(ptr - 1) = char('0' + uval);
}
}
template <
class U,
std::enable_if_t<internal::is_unsigned_int128<U>::value>* = nullptr>
void write_unsigned(U uval) {
static std::array<char, 50> buf;
size_t len = 0;
while (uval > 0) {
buf[len++] = char((uval % 10) + '0');
uval /= 10;
}
std::reverse(buf.begin(), buf.begin() + len);
memcpy(line.data() + pos, buf.data(), len);
pos += len;
}
void write_single(const std::string& s) {
for (char c : s) write_single(c);
}
void write_single(const char* s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) write_single(s[i]);
}
template <class T> void write_single(const std::vector<T>& val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write_single(' ');
write_single(val[i]);
}
}
};
inline std::array<std::array<char, 2>, 100> Printer::small = [] {
std::array<std::array<char, 2>, 100> table;
for (int i = 0; i <= 99; i++) {
table[i][1] = char('0' + (i % 10));
table[i][0] = char('0' + (i / 10 % 10));
}
return table;
}();
inline std::array<unsigned long long, 20> Printer::tens = [] {
std::array<unsigned long long, 20> table;
for (int i = 0; i < 20; i++) {
table[i] = 1;
for (int j = 0; j < i; j++) {
table[i] *= 10;
}
}
return table;
}();
} // namespace yosupo
#line 5 "ucup3-25/G/main.cpp"
using namespace yosupo;
#line 2 "ucup3-25/G/base.hpp"
#ifdef YOSUPO_AVX2_PRAGMA
#line 5 "ucup3-25/G/base.hpp"
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#line 11 "ucup3-25/G/base.hpp"
#include <bitset>
#line 13 "ucup3-25/G/base.hpp"
#include <cmath>
#include <cstdio>
#line 16 "ucup3-25/G/base.hpp"
#include <iostream>
#include <map>
#include <queue>
#include <ranges>
#include <set>
#line 22 "ucup3-25/G/base.hpp"
#include <utility>
#line 24 "ucup3-25/G/base.hpp"
using std::abs, std::pow, std::sqrt;
using std::array, std::vector, std::string, std::queue, std::deque;
using std::countl_zero, std::countl_one, std::countr_zero, std::countr_one;
using std::istream, std::ostream, std::cerr, std::endl;
using std::min, std::max, std::swap;
using std::pair, std::tuple, std::bitset;
using std::popcount;
using std::priority_queue, std::set, std::multiset, std::map;
using std::views::iota, std::views::reverse;
namespace ranges = std::ranges;
using ranges::sort, ranges::copy_n;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#ifdef YOSUPO_LOCAL
inline ostream& operator<<(ostream& os, __int128_t x) {
if (x < 0) {
os << "-";
x *= -1;
}
if (x == 0) {
return os << "0";
}
string s;
while (x) {
s += char(x % 10 + '0');
x /= 10;
}
ranges::reverse(s);
return os << s;
}
inline ostream& operator<<(ostream& os, __uint128_t x) {
if (x == 0) {
return os << "0";
}
string s;
while (x) {
s += char(x % 10 + '0');
x /= 10;
}
ranges::reverse(s);
return os << s;
}
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p);
template <class T> ostream& operator<<(ostream& os, const V<T>& v);
template <class T> ostream& operator<<(ostream& os, const deque<T>& v);
template <class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N>& a);
template <class T> ostream& operator<<(ostream& os, const set<T>& s);
template <class T, class U>
ostream& operator<<(ostream& os, const map<T, U>& m);
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
return os << "P(" << p.first << ", " << p.second << ")";
}
template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
os << "[";
bool f = false;
for (auto d : v) {
if (f) os << ", ";
f = true;
os << d;
}
return os << "]";
}
template <class T> ostream& operator<<(ostream& os, const deque<T>& v) {
os << "[";
bool f = false;
for (auto d : v) {
if (f) os << ", ";
f = true;
os << d;
}
return os << "]";
}
template <class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N>& a) {
os << "[";
bool f = false;
for (auto d : a) {
if (f) os << ", ";
f = true;
os << d;
}
return os << "]";
}
template <class T> ostream& operator<<(ostream& os, const set<T>& s) {
os << "{";
bool f = false;
for (auto d : s) {
if (f) os << ", ";
f = true;
os << d;
}
return os << "}";
}
template <class T> ostream& operator<<(ostream& os, const multiset<T>& s) {
os << "{";
bool f = false;
for (auto d : s) {
if (f) os << ", ";
f = true;
os << d;
}
return os << "}";
}
template <class T, class U>
ostream& operator<<(ostream& os, const map<T, U>& s) {
os << "{";
bool f = false;
for (auto p : s) {
if (f) os << ", ";
f = true;
os << p.first << ": " << p.second;
}
return os << "}";
}
struct PrettyOS {
ostream& os;
bool first;
template <class T> auto operator<<(T&& x) {
if (!first) os << ", ";
first = false;
os << x;
return *this;
}
};
template <class... T> void dbg0(T&&... t) {
(PrettyOS{cerr, true} << ... << t);
}
#define dbg(...) \
do { \
cerr << __LINE__ << " : " << #__VA_ARGS__ << " = "; \
dbg0(__VA_ARGS__); \
cerr << endl; \
} while (false);
#else
#define dbg(...)
#endif
#line 8 "ucup3-25/G/main.cpp"
Scanner sc = Scanner(stdin);
Printer pr = Printer(stdout);
void solve() {
int n; ll k;
sc.read(n, k);
V<int> tv(n);
for (int i : iota(0, n)) {
sc.read(tv[i]);
}
VV<int> tr(n);
V<int> p(n);
for (int i : iota(0, n)) {
sc.read(p[i]);
p[i]--;
tr[p[i]].push_back(i);
}
dbg(p);
VV<int> cys;
V<bool> is_cy(n);
{
V<int> vis(n, -1);
for (int i : iota(0, n)) {
if (vis[i] != -1) continue;
int j = i;
do {
vis[j] = i;
j = p[j];
} while (vis[j] == -1);
dbg(i, j, vis[j]);
if (vis[j] != i) continue;
V<int> cy;
int j2 = j;
do {
cy.push_back(j2);
j2 = p[j2];
} while (j2 != j);
cys.push_back(cy);
for (int x : cy) {
is_cy[x] = true;
}
}
}
dbg(cys);
using P = pair<ll, int>; // (dist, next)
V<P> nxt(n); // (dist, next)
{
for (auto cy: cys) {
int m = int(cy.size());
map<int, V<int>> cy_mp;
for (int i : iota(0, 2 * m)) {
int t = tv[cy[i % m]];
cy_mp[t].push_back(i);
}
for (int i : iota(0, m)) {
int r = cy[i];
map<int, pair<int, int>> mp;
auto dfs = [&](auto self, int u, int dps) -> void {
int t = tv[cy[i]];
if (mp.count(t)) {
nxt[u] = {dps - mp[t].first, mp[t].second};
} else if (cy_mp.count(t)) {
const auto& v = cy_mp[t];
auto it = lower_bound(v.begin(), v.end(), u == r ? i + 1 : i);
assert(it != v.end());
int idx = *it;
dbg(u, dps, i, r, idx, u == r ? i + 1 : i);
nxt[u] = {(idx - i) + dps, cy[idx % m]};
} else {
nxt[u] = {TEN(9), u};
}
for (auto v : tr[u]) {
if (is_cy[v]) continue;
pair<int, int> pre = {-1, -1};
if (mp.count(t)) {
pre = mp[t];
}
self(self, v, dps + 1);
if (pre.first == -1) {
mp.erase(t);
} else {
mp[t] = pre;
}
}
};
dfs(dfs, r, 0);
}
}
}
dbg(nxt);
V<P> dp(n);
{
for (int i : iota(0, n)) {
dp[i] = {0, i};
}
k--;
V<bool> bits;
while (k) {
if (k % 2) {
bits.push_back(true);
k--;
}
if (k == 0) break;
bits.push_back(false);
k /= 2;
}
// calc dp
while (bits.size()) {
if (bits.back()) {
dbg("add1");
V<P> ndp(n);
for (int i : iota(0, n)) {
ndp[i].first = dp[i].first + nxt[dp[i].second].first;
ndp[i].second = nxt[dp[i].second].second;
}
dp = ndp;
dbg(dp);
} else {
dbg("mul2");
V<P> ndp(n);
for (int i : iota(0, n)) {
ndp[i].first = dp[i].first + dp[dp[i].second].first;
ndp[i].second = dp[dp[i].second].second;
}
dp = ndp;
dbg(dp);
}
bits.pop_back();
}
}
dbg(dp);
{
for (auto cy : cys) {
for (int _ : iota(0, 2)) {
int y = *cy.begin();
for (auto x : cy | reverse) {
auto dfs = [&](auto self, int u, int p) -> void {
dp[u] = min(dp[u], {dp[p].first + 1, dp[p].second});
for (int v : tr[u]) {
if (is_cy[v]) continue;
self(self, v, u);
}
};
dfs(dfs, x, y);
y = x;
}
}
}
}
dbg(dp);
ll ans = 0;
for (int i : iota(0, n)) {
ans += 1LL * tv[dp[i].second] * (i + 1);
}
pr.writeln(ans);
}
int main() {
int t;
sc.read(t);
for (int _ : iota(0, t)) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3672kb
input:
3 5 3 2 2 1 3 3 2 5 1 2 4 5 4 2 2 1 3 3 2 5 1 2 4 3 10 1 2 3 1 3 2
output:
41 45 14
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 33ms
memory: 3596kb
input:
6000 19 48 18 19 18 19 11 9 15 19 12 18 11 18 9 18 9 18 19 11 15 12 14 18 8 1 3 19 5 13 14 15 2 14 5 19 2 19 12 9 15 23 3 1 1 3 6 1 4 1 1 6 6 4 12 4 6 14 1 8 8 6 6 12 14 6 8 5 7 14 2 5 9 140979583 4 5 8 9 2 7 6 8 2 8 9 4 6 9 2 4 7 8 4 976357580 2 3 1 3 2 1 1 4 6 508962809 4 3 4 3 4 4 4 5 4 5 5 6 13 ...
output:
3420 335 257 26 84 776 126 30 1092 1 2678 2422 168 360 298 324 2426 2520 220 228 1005 9 3486 1 796 69 274 272 600 3214 32 495 40 135 140 708 1635 702 68 96 90 288 29 588 16 234 445 2844 140 40 477 1197 19 1994 1412 32 522 672 20 390 28 2204 1938 42 21 885 4 1539 196 420 11 1715 619 720 1 458 40 17 2...
result:
wrong answer 2nd lines differ - expected: '260', found: '335'