Submission #591924

#	Time	Username	Problem	Language	Result	Execution time	Memory
591924		Hanksburger	Friend (IOI14_friend)	C++17	8 / 100	2 ms	2656 KiB

friend

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

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