Submission #592057

#	Time	Username	Problem	Language	Result	Execution time	Memory
592057		Hanksburger	Friend (IOI14_friend)	C++17	8 / 100	3 ms	2644 KiB

friend

#include <bits/stdc++.h>
using namespace std;
bool grp[100005], ok[100005];
queue<pair<int, bool> > q;
vector<int> adj[100005];
int findSample(int n, int c[], int h[], int p[])
{
    for (int i=1; i<n; i++)
    {
        if (!p[i])
        {
            grp[i]=!grp[h[i]];
            ok[i]=ok[h[i]]=1;
        }
        else if (p[i]==1)
        {
            grp[i]=grp[h[i]];
            if (ok[h[i]])
                ok[i]=1;
        }
        else
        {
            grp[i]=grp[h[i]];
            ok[i]=ok[h[i]]=1;
            adj[i].push_back(h[i]);
            adj[h[i]].push_back(i);
        }
    }
    int ans[2]={}, num=0;
    for (int i=0; i<n; i++)
        if (!ok[i])
            num+=c[i];
    for (int i=0; i<n; i++)
    {
        if (ok[i])
        {
            int cnt[2]={c[i], 0};
            q.push({i, 0});
            ok[i]=0;
            while (!q.empty())
            {
                int u=q.front().first, g=q.front().second;
                q.pop();
                for (int v:adj[u])
                {
                    if (ok[v])
                    {
                        cnt[!g]+=c[v];
                        q.push({v, !g});
                        ok[v]=0;
                    }
                }
            }
            ans[grp[i]]+=max(cnt[0], cnt[1]);
        }
    }
    return max(ans[0], ans[1])+num;
}

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