제출 #296549

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296549		arayi	친구 (IOI14_friend)	C++17	46 / 100	38 ms	4480 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"
#define ad push_back
using namespace std;

const int N = 1010;
int n;
vector <int> g[N];
bool col[20][20];
int dp[N][2];
int sz[N];
bool cl[N];
void dfs(int v, int par)
{
    int sum = 0, sm = 0;
    for(auto p : g[v])
    {
        if(p == par) continue;
        dfs(p, v);
        sum += dp[p][0];
        sm += max(dp[p][1], dp[p][0]);
    }
    dp[v][0] = sm;
    dp[v][1] += sum;
}
int findSample(int n1,int c[],int host[],int pr[])
{
    n = n1;
    bool mk, erk, erq;
    mk=erk=erq=0;
	for (int i = 1; i < n; i++)
	{
	    if(pr[i] == 0)
        {
            g[host[i]].ad(i);
            g[i].ad(host[i]);
            mk = 1;
        }
        else if(pr[i] == 1)
        {
            for(auto p : g[host[i]]) g[p].ad(i), g[i].ad(p);
            erk = 1;
        }
        else
        {
            for(auto p : g[host[i]]) g[p].ad(i), g[i].ad(p);
            g[host[i]].ad(i);
            g[i].ad(host[i]);
            erq = 1;
        }
	}
	if(n <= 10)
    {
        for (int i = 0; i < n; i++)
            for(auto p : g[i]) col[i][p] = 1;//, cout << i << " " << p << endl;
        int pat = 0;
        for(int x = 0; x < (1 << n); ++x)
        {
            int sum = 0;
            vector <int> sm;
            for (int i = 0; i < n; i++)
                if(x & (1 << i)) sum += c[i], sm.ad(i);
            bool bl = 0;
            for(auto p : sm)
                for(auto p1 : sm) if(col[p][p1]) bl = true;
            if(!bl) pat = max(pat, sum);
        }
        return pat;
    }
    if(!mk && erk && !erq)
    {
        int pat = 0;
        for (int i = 0; i < n; i++)
            pat += c[i];
        return pat;
    }
    if(!mk && !erk && erq)
    {
        int pat = 0;
        for (int i = 0; i < n; i++)
            pat = max(pat, c[i]);
        return pat;
    }
    if(mk && !erk && !erq)
    {
        for (int i = 0; i < n; i++) dp[i][1] = c[i];
        dfs(0, 0);
        return max(dp[0][0], dp[0][1]);
    }
    else
    {
        int pat = 0;
        for (int i = 0; i < n; i++) sz[i] = 1;
        for(int i = n - 1; i > 0; i--)
        {
           if(pr[i] == 0)
           {
               pat += sz[i];
               if(sz[host[i]]);
                sz[host[i]]--;
           }
           else
           {
               sz[host[i]] += sz[i];
           }
        }
        return pat + sz[0];
    }
}

컴파일 시 표준 에러 (stderr) 메시지

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:99:16: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   99 |                if(sz[host[i]]);
      |                ^~
friend.cpp:100:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  100 |                 sz[host[i]]--;
      |                 ^~

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