Submission #39718

#	Time	Username	Problem	Language	Result	Execution time	Memory
39718		funcsr	Friend (IOI14_friend)	C++14	30 / 100	40 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;
  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 {
    for (int i=1; i<N; i++) {
      if (protocol[i] != 0) abort();
      G[host[i]].pb(i);
    }
    dfs(0);
    m = dp[0][1];
  }
  return m;
}

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