제출 #1282766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282766		repmann	친구 (IOI14_friend)	C++20	46 / 100	15 ms	4424 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[])
{
  if(sol) return;
  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[])
{
  if(sol) return;
  bool flag = true;
  for(int i = 1; i < N; i++) flag &= t[i] == 2;
  if(!flag) return;
  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[])
{
  if(sol) return;
  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;
}
int cnt[2], V[1000];
inline void DFS(int node)
{
  if((V[node] < 0) || (V[node] > 1)) exit(333);
  cnt[V[node]]++;
  for(int x : VG[node]) if(V[x] < 0) {V[x] = V[node] ^ 1; DFS(x);}
  return;
}
inline void Sub5(int t[])
{
  if(sol) return;
  bool flag = true;
  for(int i = 0; i < N; i++) flag &= A[i] == 1;
  for(int i = 1; i < N; i++) flag &= t[i] <= 1;
  if(!flag) return;
  for(int i = 0; i < N; i++) V[i] = -1;
  for(int i = 0; i < N; i++)
  {
    if(V[i] >= 0) continue;
    V[i] = cnt[0] = cnt[1] = 0;
    DFS(i);
    sol += max(cnt[0], cnt[1]);
  }
  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