Submission #39719

#	Time	Username	Problem	Language	Result	Execution time	Memory
39719		funcsr	Friend (IOI14_friend)	C++14	38 / 100	33 ms	7488 KiB

friend

#include "friend.h"
#include <iostream>
#include <vector>
#include <cassert>
#include <set>
#include <algorithm>
#include <map>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define INF 1145141919
#define _1 first
#define _2 second

int N;
int A[100000];
vector<int> G[100000];

long long dp[100000][2];
void dfs(int x) {
  long long a = 0, b = A[x];
  for (int t : G[x]) {
    dfs(t);
    a += dp[t][1];
    b += dp[t][0];
  }
  dp[x][0] = a;
  dp[x][1] = max(a, b);
}

int findSample(int n, int confidence[], int host[], int protocol[]){
  N = n;
  rep(i, N) A[i] = confidence[i];
  long long m = 0;
  bool all0 = true, all1 = true, all2 = true;
  for (int i=1; i<N; i++) {
    if (protocol[i] != 0) all0 = false;
    if (protocol[i] != 1) all1 = false;
    if (protocol[i] != 2) all2 = false;
  }
  if (N <= 10) {
    for (int i=1; i<N; i++) {
      if (protocol[i] == 0) {
        G[host[i]].pb(i);
        G[i].pb(host[i]);
      }
      else if (protocol[i] == 1) {
        for (int t : G[host[i]]) G[i].pb(t), G[t].pb(i);
      }
      else {
        for (int t : G[host[i]]) G[i].pb(t), G[t].pb(i);
        G[host[i]].pb(i);
        G[i].pb(host[i]);
      }
    }
    rep(S, 1<<N) {
      bool good = true;
      rep(i, N) if ((S>>i)&1) {
        for (int t : G[i]) if ((S>>t)&1) {
          good = false;
          break;
        }
      }
      if (!good) continue;
      long long s = 0;
      rep(i, N) if ((S>>i)&1) s += A[i];
      m = max(m, s);
    }
  }
  else if (all0) {
    for (int i=1; i<N; i++) {
      G[host[i]].pb(i);
    }
    dfs(0);
    m = dp[0][1];
  }
  else if (all2) {
    rep(i, N) m = max(m, (long long)A[i]);
  }
  else abort();
  return m;
}

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:37:21: warning: variable 'all1' set but not used [-Wunused-but-set-variable]
   bool all0 = true, all1 = true, all2 = true;
                     ^

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