Submission #1282644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282644		repmann	Friend (IOI14_friend)	C++20	46 / 100	15 ms	4416 KiB

friend

#include <bits/stdc++.h>
//#include "friend.h"
using namespace std;
int N, sol;
int A[1000];
vector <int> VG[1000];
inline void Sub1()
{
  if(N > 10) return;
  for(int i = 1; i < (1 << N); i++)
  {
    int temp = 0;
    for(int j = 0; (j < N) && (temp >= 0); j++)
    {
      if(!(i & (1 << j))) continue;
      temp += A[j];
      for(int x : VG[j]) if(i & (1 << x)) temp = -1;
    }
    sol = max(temp, sol);
  }
  return;
}
inline void Sub2(int t[])
{
  bool flag = true;
  for(int i = 1; i < N; i++) flag &= t[i] == 1;
  if(!flag) return;
  sol = 0;
  for(int i = 0; i < N; i++) sol += A[i];
  return;
}
inline void Sub3(int t[])
{
  bool flag = true;
  for(int i = 1; i < N; i++) flag &= t[i] == 2;
  if(!flag) return;
  sol = 0;
  for(int i = 0; i < N; i++) sol = max(A[i], sol);
  return;
}
int DP[2][1000];
inline void DPDFS(int node, int parent = -1)
{
  for(int x : VG[node]) if(x != parent) DPDFS(x, node);
  DP[0][node] = 0;
  for(int x : VG[node]) DP[0][node] += (x != parent) * max(DP[0][x], DP[1][x]);
  DP[1][node] = A[node];
  for(int x : VG[node]) DP[1][node] += (x != parent) * DP[0][x];
  return;
}
inline void Sub4(int t[])
{
  bool flag = true;
  for(int i = 1; i < N; i++) flag &= t[i] == 0;
  if(!flag) return;
  DPDFS(0);
  sol = max(DP[0][0], DP[1][0]);
  return;
}
inline void Sub5(int t[])
{
  bool flag = true;
  for(int i = 1; i < N; i++) flag &= A[i] == 1;
  if(!flag) return;
  return;
}
int findSample(int n, int a[], int p[], int t[])
{
  if(n > 1000) return 0;
  N = n;
  for(int i = 0; i < N; i++) A[i] = a[i];
  for(int i = 1; i < N; i++)
  {
    if(t[i] != 0) for(int x : VG[p[i]]) {VG[x].push_back(i); VG[i].push_back(x);}
    if(t[i] != 1) {VG[p[i]].push_back(i); VG[i].push_back(p[i]);}
  }
  Sub1();
  Sub2(t);
  Sub3(t);
  Sub4(t);
  Sub5(t);
  return sol;
}

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