QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#397442 | #3748. 买一送一 | SamponYW | AC ✓ | 87ms | 19948kb | C++14 | 1.9kb | 2024-04-24 08:49:55 | 2024-04-24 08:49:55 |
Judging History
answer
#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
#define N 100005
#define P 1000000007
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
il int qpow(int p, int n = P - 2) {
int s = 1;
while(n) {
if(n & 1) s = 1ll * s * p % P;
p = 1ll * p * p % P, n >>= 1;
}
return s;
}
int n, a[N]; vector<int> e[N];
ll ans[N]; int v[N], pre[N], s[N], mu[N];
il void upd(int x, int v) {while(x <= n) s[x] += v, x += x & -x;}
il int query(int x) {int v = 0; while(x) v += s[x], x ^= x & -x; return v;}
il int query(int l, int r) {return query(r) - query(l - 1);}
il void dfs(int x, int d = 1) {
int s = pre[a[x]]; pre[a[x]] = d;
ans[x] = query(s + 1, d); int p = mu[a[x]];
if(s > 0) ans[x] += !mu[a[x]], mu[a[x]] = 1;
if(!v[a[x]]++) upd(d, 1);
for(auto y : e[x]) dfs(y, d + 1);
if(!--v[a[x]]) upd(d, -1);
pre[a[x]] = s, mu[a[x]] = p;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
while(cin >> n) {
FOR(x, 1, n) vector<int>().swap(e[x]);
FOR(x, 2, n) {int f; cin >> f, e[f].eb(x);}
FOR(x, 1, n) cin >> a[x]; dfs(1);
FOR(x, 1, n) for(auto y : e[x]) ans[y] += ans[x];
FOR(x, 2, n) cout << ans[x] << "\n";
}
cerr << 1.0 * clock() / CLOCKS_PER_SEC;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 87ms
memory: 19948kb
input:
100 1 2 3 4 5 5 7 7 9 10 11 12 13 13 15 13 12 18 12 11 10 7 7 4 25 26 27 4 2 30 31 32 33 34 34 36 34 33 33 33 32 32 30 2 45 1 47 48 49 50 51 52 53 52 55 56 56 52 59 60 59 59 63 64 51 66 49 68 69 68 47 72 73 72 75 76 77 78 79 80 80 82 77 84 77 86 76 88 75 72 91 92 72 94 94 96 97 94 72 55 12 85 53 40 ...
output:
1 3 6 10 15 15 21 21 28 30 38 47 57 57 68 55 47 57 47 38 36 21 21 10 15 21 28 10 3 6 10 15 21 28 28 36 28 21 21 21 15 15 6 3 6 1 3 6 10 15 21 28 36 28 36 45 45 28 36 45 30 36 45 55 21 28 10 15 17 15 3 6 10 6 10 15 21 28 36 45 45 55 21 28 21 28 15 21 10 6 10 15 6 10 10 15 21 10 6 1 3 6 6 10 15 21 28 ...
result:
ok 498996 numbers