제출 #1277145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277145		andrei_iorgulescu	Friend (IOI14_friend)	C++20	50 / 100	43 ms	22924 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"

using namespace std;

const int NMAX = 100000;

int n;

int a[NMAX + 5], hosst[NMAX + 5], p[NMAX + 5];

set<int> fl[NMAX + 5], fr[NMAX + 5];
int t[2 * NMAX + 5];
int tip[2 * NMAX + 5], cr;///pentru cei > n, 1 -> normal, 2 -> sus
bool isroot[2 * NMAX + 5];
bool idk[NMAX + 5];

int dp[2 * NMAX + 5], dp2[2 * NMAX + 5];

void dfs(int nod)
{
    if (nod <= n)
        dp[nod] = a[nod], dp2[nod] = 0;
    else
    {
        for (auto fiu : fl[nod - n])
            if (t[fiu] == nod)
                dfs(fiu);
        for (auto fiu : fr[nod - n])
            if (t[fiu] == nod)
                dfs(fiu);
        dp[nod] = dp2[nod] = 0;
        if (tip[nod] == 1)
        {
            for (auto fiu : fl[nod - n])
                if (t[fiu] == nod)
                    dp2[nod] += dp2[fiu];
            for (auto fiu : fr[nod - n])
                if (t[fiu] == nod)
                    dp2[nod] += dp2[fiu];
            int crr;
            crr = 0;
            for (auto fiu : fl[nod - n])
                if (t[fiu] == nod)
                    crr += dp[fiu];
            for (auto fiu : fr[nod - n])
                if (t[fiu] == nod)
                    crr += dp2[fiu];
            dp[nod] = max(dp[nod], crr);
            crr = 0;
            for (auto fiu : fr[nod - n])
                if (t[fiu] == nod)
                    crr += dp[fiu];
            for (auto fiu : fl[nod - n])
                if (t[fiu] == nod)
                    crr += dp2[fiu];
            dp[nod] = max(dp[nod], crr);
        }
        else
        {
            for (auto fiu : fl[nod - n])
                if (t[fiu] == nod)
                    dp2[nod] += dp2[fiu];
            for (auto fiu : fr[nod - n])
                if (t[fiu] == nod)
                    dp2[nod] += dp[fiu];
            int crr;
            crr = 0;
            for (auto fiu : fl[nod - n])
                if (t[fiu] == nod)
                    crr += dp[fiu];
            for (auto fiu : fr[nod - n])
                if (t[fiu] == nod)
                    crr += dp2[fiu];
            dp[nod] = max(dp[nod], crr);
            crr = 0;
            for (auto fiu : fr[nod - n])
                if (t[fiu] == nod)
                    crr += dp[fiu];
            for (auto fiu : fl[nod - n])
                if (t[fiu] == nod)
                    crr += dp2[fiu];
            dp[nod] = max(dp[nod], crr);
        }
    }
}

int solve(int root)
{
    dfs(root);
    return dp[root];
}

int findSample(int N, int Confidence[], int Host[], int Protocol[])
{
    n = N;
    for (int i = 1; i <= n; i++)
        a[i] = Confidence[i - 1];
    for (int i = 2; i <= n; i++)
        hosst[i] = Host[i - 1] + 1;
    for (int i = 2; i <= n; i++)
        p[i] = Protocol[i - 1];
    cr = n;
    isroot[1] = true;
    for (int i = 2; i <= n; i++)
    {
        if (!idk[hosst[i]] and p[i] == 1)
            isroot[i] = true;
        else
        {
            idk[i] = true;
            if (!idk[hosst[i]])
            {
                idk[hosst[i]] = true;
                cr++;
                tip[cr] = 1;
                isroot[hosst[i]] = false;
                isroot[cr] = true;
                fl[cr - n].insert(hosst[i]);
                fr[cr - n].insert(i);
                t[i] = t[hosst[i]] = cr;
            }
            else
            {
                if (p[i] == 1)
                {
                    int cn = t[hosst[i]];
                    t[i] = cn;
                    if (fl[cn - n].find(hosst[i]) != fl[cn - n].end())
                        fl[cn - n].insert(i);
                    else
                        fr[cn - n].insert(i);
                }
                else if (p[i] == 0)
                {
                    int cn = t[hosst[i]];
                    cr++;
                    tip[cr] = 2;
                    t[cr] = cn;
                    bool inst = false;
                    if (fl[cn - n].find(hosst[i]) != fl[cn - n].end())
                        inst = true;
                    if (inst)
                    {
                        //fl[cn - n].erase(hosst[i]);
                        fl[cn - n].insert(cr);
                        fl[cr - n].insert(hosst[i]);
                        fr[cr - n].insert(i);
                        t[i] = t[hosst[i]] = cr;
                    }
                    else
                    {
                        //fr[cn - n].erase(hosst[i]);
                        fr[cn - n].insert(cr);
                        fl[cr - n].insert(hosst[i]);
                        fr[cr - n].insert(i);
                        t[i] = t[hosst[i]] = cr;
                    }
                }
                else if (p[i] == 2)
                {
                    int cn = t[hosst[i]];
                    cr++;
                    tip[cr] = 1;
                    bool inst = false;
                    if (fl[cn - n].find(hosst[i]) != fl[cn - n].end())
                        inst = true;
                    if (inst)
                    {
                        fl[cn - n].erase(hosst[i]);
                        fl[cn - n].insert(cr);
                        fl[cr - n].insert(hosst[i]);
                        fr[cr - n].insert(i);
                        t[i] = t[hosst[i]] = cr;
                    }
                    else
                    {
                        fr[cn - n].erase(hosst[i]);
                        fr[cn - n].insert(cr);
                        fl[cr - n].insert(hosst[i]);
                        fr[cr - n].insert(i);
                        t[i] = t[hosst[i]] = cr;
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int it = 1; it <= cr; it++)
        if (isroot[it])
            ans += solve(it);
    return ans;
}

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