Submission #592093

#	Time	Username	Problem	Language	Result	Execution time	Memory
592093		Hanksburger	Friend (IOI14_friend)	C++17	8 / 100	4 ms	5076 KiB

friend

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

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