Submission #920829

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
920829	2024-02-03T04:52:43 Z	rxlfd314	Friend (IOI14_friend)	C++17	Compilation error	0 ms	0 KB

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 (seen[ii])
      continue;
    ari2 cnt = {0, 0};
    function<void(int)> dfs = [&](int i, bool t) {
      if (~type[i])
        return;
      cnt[type[i] = t]++;
      for (int j : adj[i])
        dfs(j, t ^ 1);
    }; 
    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) {
      |                                  ~^~
friend.cpp:95:9: error: 'seen' was not declared in this scope
   95 |     if (seen[ii])
      |         ^~~~
friend.cpp: In lambda function:
friend.cpp:103:21: error: no match for call to '(std::function<void(int)>) (int&, int)'
  103 |         dfs(j, t ^ 1);
      |                     ^
In file included from /usr/include/c++/10/functional:59,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from friend.cpp:2:
/usr/include/c++/10/bits/std_function.h:617:5: note: candidate: '_Res std::function<_Res(_ArgTypes ...)>::operator()(_ArgTypes ...) const [with _Res = void; _ArgTypes = {int}]'
  617 |     function<_Res(_ArgTypes...)>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/std_function.h:617:5: note:   candidate expects 1 argument, 2 provided
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:104:5: error: conversion from 'findSample(int, int*, int*, int*)::<lambda(int, bool)>' to non-scalar type 'std::function<void(int)>' requested
  104 |     };
      |     ^