Submission #1277140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277140		andrei_iorgulescu	Friend (IOI14_friend)	C++20	69 / 100	20 ms	12080 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[NMAX + 5], cr;///pentru cei > n, 1 -> normal, 2 -> sus
set<int> roots;
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])
            dfs(fiu);
        for (auto fiu : fr[nod - n])
            dfs(fiu);
        dp[nod] = dp2[nod] = 0;
        if (tip[nod] == 1)
        {
            for (auto fiu : fl[nod - n])
                dp2[nod] += dp2[fiu];
            for (auto fiu : fr[nod - n])
                dp2[nod] += dp2[fiu];
            int crr;
            crr = 0;
            for (auto fiu : fl[nod - n])
                crr += dp[fiu];
            for (auto fiu : fr[nod - n])
                crr += dp2[fiu];
            dp[nod] = max(dp[nod], crr);
            crr = 0;
            for (auto fiu : fr[nod - n])
                crr += dp[fiu];
            for (auto fiu : fl[nod - n])
                crr += dp2[fiu];
            dp[nod] = max(dp[nod], crr);
        }
        else
        {
            for (auto fiu : fl[nod - n])
                dp2[nod] += dp2[fiu];
            for (auto fiu : fr[nod - n])
                dp2[nod] += dp[fiu];
            int crr;
            crr = 0;
            for (auto fiu : fl[nod - n])
                crr += dp[fiu];
            for (auto fiu : fr[nod - n])
                crr += dp2[fiu];
            dp[nod] = max(dp[nod], crr);
            crr = 0;
            for (auto fiu : fr[nod - n])
                crr += dp[fiu];
            for (auto fiu : fl[nod - n])
                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;
    roots.insert(1);
    for (int i = 2; i <= n; i++)
    {
        if (!idk[hosst[i]] and p[i] == 1)
            roots.insert(i);
        else
        {
            idk[i] = true;
            if (!idk[hosst[i]])
            {
                idk[hosst[i]] = true;
                cr++;
                tip[cr] = 1;
                roots.erase(hosst[i]);
                roots.insert(cr);
                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;
                    }
                }
            }
        }
    }
    /*for (int i = n + 1; i <= cr; i++)
    {
        cout << i << ' ' << tip[i] << endl;
        for (auto it : fl[i])
            cout << it << ' ';
        cout << endl;
        for (auto it : fr[i])
            cout << it << ' ';
        cout << endl;
        cout << endl;
    }*/
    int ans = 0;
    for (auto it : roots)
        ans += solve(it);
    return ans;
}

/*
6
13 3 6 20 10 15
0 0
0 1
1 2
2 1
0 0
*/

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