QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#649931 | #8237. Sugar Sweet II | Attiesal | WA | 374ms | 7596kb | C++14 | 2.3kb | 2024-10-18 11:35:11 | 2024-10-18 11:35:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll qsm(ll x, ll n) {
ll res = 1;
while (n) {
if (n & 1) res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
ll inv(ll a) { return qsm(a, mod - 2); }
ll fac[500003];
void solve() {
ll n;cin >> n;
vector<ll> a(n + 1), b(n + 1), w(n + 1), ans(n + 1), visit(n + 1);
for (ll i = 1; i <= n; i++) cin >> a[i];
for (ll i = 1; i <= n; i++) cin >> b[i];
for (ll i = 1; i <= n; i++) cin >> w[i];
vector<vector<ll>> g(n + 1);
for (ll i = 1; i <= n; i++) {
if (a[i] < a[b[i]]) ans[i] = a[i] + w[i];
else if (a[i] >= a[b[i]] + w[b[i]]) ans[i] = a[i], visit[i] = 1;
else if (i == b[i]) ans[i] = a[i], visit[i] = 1;
else {
//cout << i << "->" << b[i] << endl;
g[i].push_back(b[i]);
}
}
vector<ll> sz(n + 1, 1);
vector<ll> v2(n + 1);
ll flag = 0, st = 0, has_circle = 0;
auto del = [&](ll u, auto&& del) {
v2[u] = 1;
if (g[u].size() == 0) return;
for (auto i : g[u]) {
if (v2[i]) {
flag = 1, st = u, has_circle = 1;
//cout << u << "->" << i << endl;
g[u].clear();ans[u] = a[u];
return;
}
del(i, del);
}
if (flag) {
v2[u] = 1;
ans[u] = a[u];
g[u].clear();
if (u == st) flag = 0;
}
};
auto dfs = [&](ll u, auto&& dfs) {
visit[u] = 1;
if (g[u].size() == 0) return;
for (auto i : g[u]) {
if (!visit[i]) dfs(i, dfs);
sz[u] += sz[i];
ans[u] = (inv(fac[sz[u]]) * (a[u] + w[u]) % mod + ((fac[sz[u]] - 1 + mod) % mod * a[u]) % mod * inv(fac[sz[u]]) % mod) % mod;
}
};
for (ll i = 1; i <= n; i++) {
if (!v2[i]) del(i, del);
if(has_circle) break;
}
for (ll i = 1; i <= n; i++) {
if (!visit[i]) dfs(i, dfs);
cout << ans[i] << ' ';
}
cout << endl;
}
int main() {
fac[0] = 1;
fac[1] = 1;
for (ll i = 2; i <= 500000; i++) fac[i] = fac[i - 1] * i % mod;
ll t;cin >> t;
while (t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 7492kb
input:
4 4 2 5 5 2 4 2 1 3 3 2 1 4 3 5 4 3 1 1 1 6 6 6 3 5 4 3 2 3 1 1 2 3 5 2 1 3 2 1 5 1 1 3 4 1 3 4 2 4
output:
500000007 5 5 6 5 10 9 166666673 5 6 500000006 4 3 4 5
result:
ok 15 numbers
Test #2:
score: -100
Wrong Answer
time: 374ms
memory: 7596kb
input:
50000 5 508432375 168140163 892620793 578579275 251380640 3 4 4 1 3 346232959 736203130 186940774 655629320 607743104 1 863886789 1 364158084 18 864679185 463975750 558804051 604216585 694033700 499417132 375390750 337590759 467353355 111206671 983760005 984444619 322277587 138763925 205122047 97736...
output:
854665334 904343293 892620793 578579275 859123744 863886789 871186919 814243920 968784984 1206455481 694033700 1449261420 196759729 901433117 519383814 907574792 983760005 984444619 489899014 435736558 1113628633 977360756 482247153 963066959 902284038 577926775 132646723 421298438 601054667 1099...
result:
wrong answer 3rd numbers differ - expected: '590444253', found: '892620793'