Submission #920820

#	Time	Username	Problem	Language	Result	Execution time	Memory
920820		rxlfd314	Friend (IOI14_friend)	C++17	11 / 100	23 ms	2640 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 (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;
  }
  if (accumulate(P, P+N, 0) == N<<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;
  }
  ari2 ans = {0, 0};
  vt<bool> type(N);
  FOR(i, 1, N-1)
    ans[type[i]=type[H[i]]^!P[i]] += C[i];
  return max(ans[0], ans[1]);
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31