QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#55416 | #3748. 买一送一 | hyx000 | AC ✓ | 143ms | 64900kb | C++17 | 1.7kb | 2022-10-13 17:18:22 | 2022-10-13 17:18:25 |
Judging History
answer
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define int long long
#define x first
#define y second
#define ps push_back
#define endl '\n'
#define kd \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
using namespace std;
typedef pair<int, int> pi;
const int N = 2e6 + 100, mod = 1e9 + 7, INF = 1e10;
int lowbit(int x) { return x & -x; }
int gcd(int a, int b) { return a % b == 0 ? b : gcd(b, a % b); }
int last[N], w[N];
int vis[N], cnt, sum;
vector<int> v[N];
int ans[N];
void add(int x, int y) { v[x].ps(y); }
void dfs(int u, int pr) {
int temp;
if (!vis[w[u]]) {
temp = cnt;
cnt++;
} else if (vis[w[u]] == 1) {
temp = cnt - last[w[u]] + 1;
} else {
temp = cnt - last[w[u]];
}
vis[w[u]]++;
ans[u] = sum + temp;
int fa = last[w[u]];
sum += temp;
last[w[u]] = cnt;
// cout << u << " " << last[w[u]] << endl;
for (int j : v[u]) {
dfs(j, u);
}
last[w[u]] = fa;
vis[w[u]]--;
sum -= temp;
if (!vis[w[u]]) cnt--;
}
void solve() {
int n;
while (cin >> n) {
sum = 0, cnt = 0;
for (int i = 1; i <= n; i++)
v[i].clear(), last[i] = 0, vis[i] = 0, ans[i] = 0;
for (int i = 2; i <= n; i++) {
int x;
cin >> x;
add(x, i);
}
for (int i = 1; i <= n; i++) cin >> w[i];
dfs(1, -1);
for (int i = 2; i <= n; i++) {
cout << ans[i] << endl;
}
// cout << endl;
}
}
signed main() {
kd;
int _;
_ = 1;
// cin>>_;
while (_--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 143ms
memory: 64900kb
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