QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55416#3748. 买一送一hyx000AC ✓143ms64900kbC++171.7kb2022-10-13 17:18:222022-10-13 17:18:25

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-13 17:18:25]
  • Judged
  • Verdict: AC
  • Time: 143ms
  • Memory: 64900kb
  • [2022-10-13 17:18:22]
  • Submitted

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