Submission #1277158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277158		andrei_iorgulescu	Friend (IOI14_friend)	C++20	100 / 100	38 ms	12456 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];

vector<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];
bool sonl[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].push_back(hosst[i]);
                fr[cr - n].push_back(i);
                t[i] = t[hosst[i]] = cr;
                sonl[i] = false;
                sonl[hosst[i]] = true;
            }
            else
            {
                if (p[i] == 1)
                {
                    int cn = t[hosst[i]];
                    t[i] = cn;
                    if (sonl[hosst[i]])
                        fl[cn - n].push_back(i), sonl[i] = true;
                    else
                        fr[cn - n].push_back(i), sonl[i] = false;
                }
                else if (p[i] == 0)
                {
                    int cn = t[hosst[i]];
                    cr++;
                    tip[cr] = 2;
                    t[cr] = cn;
                    bool inst = false;
                    if (sonl[hosst[i]])
                        inst = true;
                    if (inst)
                    {
                        //fl[cn - n].erase(hosst[i]);
                        sonl[cr] = true;
                        fl[cn - n].push_back(cr);
                        fl[cr - n].push_back(hosst[i]);
                        fr[cr - n].push_back(i);
                        t[i] = t[hosst[i]] = cr;
                        sonl[hosst[i]] = true;
                        sonl[i] = false;
                    }
                    else
                    {
                        //fr[cn - n].erase(hosst[i]);
                        sonl[cr] = false;
                        fr[cn - n].push_back(cr);
                        fl[cr - n].push_back(hosst[i]);
                        fr[cr - n].push_back(i);
                        t[i] = t[hosst[i]] = cr;
                        sonl[hosst[i]] = true;
                        sonl[i] = false;
                    }
                }
                else if (p[i] == 2)
                {
                    int cn = t[hosst[i]];
                    cr++;
                    tip[cr] = 1;
                    t[cr] = cn;
                    bool inst = false;
                    if (sonl[hosst[i]])
                        inst = true;
                    if (inst)
                    {
                        //fl[cn - n].erase(hosst[i]);
                        sonl[cr] = true;
                        fl[cn - n].push_back(cr);
                        fl[cr - n].push_back(hosst[i]);
                        fr[cr - n].push_back(i);
                        t[i] = t[hosst[i]] = cr;
                        sonl[hosst[i]] = true;
                        sonl[i] = false;
                    }
                    else
                    {
                        //fr[cn - n].erase(hosst[i]);
                        sonl[cr] = false;
                        fr[cn - n].push_back(cr);
                        fl[cr - n].push_back(hosst[i]);
                        fr[cr - n].push_back(i);
                        t[i] = t[hosst[i]] = cr;
                        sonl[hosst[i]] = true;
                        sonl[i] = false;
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int it = 1; it <= cr; it++)
        if (isroot[it])
            ans += solve(it);
    return ans;
}

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