Submission #920831

#	Time	Username	Problem	Language	Result	Execution time	Memory
920831		rxlfd314	Friend (IOI14_friend)	C++17	46 / 100	177 ms	48376 KiB

friend

#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);
  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);
  }
  int ans = 0;
  vt<int> type(N, -1);
  FOR(ii, 0, N-1) {
    if (~type[ii])
      continue;
    ari2 cnt = {0, 0};
    function<void(int, bool)> dfs = [&](int i, bool t) {
      if (~type[i])
        return;
      cnt[type[i] = t]++;
      for (int j : adj[i]) {
        if (~type[j])
          assert(type[j] != t);
        dfs(j, t ^ 1);
      }
    }; 
    dfs(ii, 0);
    ans += max(cnt[0], cnt[1]);
  }
  return ans;
}

Compilation message (stderr)

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 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31