oj.uz

Submission #920828

# Submission time Handle Problem Language Result Execution time Memory
920828 2024-02-03T04:51:11 Z rxlfd314 Friend (IOI14_friend) C++17
46 / 100
 168 ms 48160 KB 
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

int findSample(int N, int *C, int *H, int *P){
  if (accumulate(P+1, P+N, 0) == N-1<<1) {
    vt<vt<int>> adj(N);
    FOR(i, 1, N-1) {
      adj[i].push_back(H[i]);
      adj[H[i]].push_back(i);
    }
    vt<bool> seen(N);
    int ans = 0;
    FOR(ii, 0, N-1) {
      if (seen[ii])
        continue;
      int mx = 0;
      queue<int> qu;
      qu.push(ii);
      seen[ii] = true;
      while (size(qu)) {
        int i = qu.front();
        qu.pop();
        mx = max(mx, C[i]);
        for (int j : adj[i])
          if (!seen[j])
            seen[j] = true, qu.push(j);
      }
      ans += mx;
    }
    return ans;
  }
  if (*max_element(P+1, P+N) == 1 && *min_element(P+1, P+N) == 1)
    return accumulate(C, C+N, 0);
  if (*max_element(P+1, P+N) == 0) {
    vt<vt<int>> adj(N);
    FOR(i, 1, N-1)
      adj[H[i]].push_back(i);
    vt<ari2> dp(N, {0, 0});
    function<void(int)> dfs = [&](int i) {
      dp[i][1] = C[i];
      for (int j : adj[i]) {
        dfs(j);
        dp[i][0] += max(dp[j][0], dp[j][1]);
        dp[i][1] += dp[j][0];
      }
    };
    dfs(0);
    return max(dp[0][0], dp[0][1]);
  }
  if (N <= 10) {
    vt<vt<bool>> adj(N, vt<bool>(N));
    FOR(i, 1, N-1) {
      if (!(P[i] & 1))
        adj[i][H[i]] = adj[H[i]][i] = true;
      if (P[i])
        FOR(j, 0, N-1)
          if (adj[H[i]][j] && i != j && j != H[i])
            adj[i][j] = adj[j][i] = true;
    }
    vt<int> dp(1<<N, INT_MIN);
    dp[0] = 0;
    int ans = 0;
    FOR(bm, 1, (1<<N)-1) {
      int i = __builtin_ctz(bm);
      for (int j = bm; j; j &= j - 1)
        if (adj[i][__builtin_ctz(j)])
          goto jail;
      if (dp[bm^1<<i] > INT_MIN)
        ans = max(ans, dp[bm] = dp[bm^1<<i] + C[i]);
      jail:;
    }
    return ans;
  }
  vt<vt<int>> adj(N);
  vt<bool> type(N);
  FOR(i, 1, N-1) {
    if (P[i])
      for (int j : adj[H[i]])
        adj[j].push_back(i), adj[i].push_back(j);
    else
      adj[i].push_back(H[i]), adj[H[i]].push_back(i);
    if (size(adj[i]))
      type[i] = type[adj[i][0]] ^ 1;
  }
  int ans = 0;
  vt<bool> seen(N);
  FOR(ii, 0, N-1) {
    if (seen[ii])
      continue;
    ari2 cnt = {0, 0};
    function<void(int)> dfs = [&](int i) {
      if (seen[i])
        return;
      cnt[type[i]]++;
      seen[i] = true;
      for (int j : adj[i])
        dfs(j);
    }; 
    dfs(ii);
    ans += max(cnt[0], cnt[1]);
  }
  return ans;
}

Compilation message

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:15:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   15 |   if (accumulate(P+1, P+N, 0) == N-1<<1) {
      |                                  ~^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Runtime error 168 ms 48160 KB Memory limit exceeded
13 Halted 0 ms 0 KB -