Submission #285704

#	Time	Username	Problem	Language	Result	Execution time	Memory
285704		Kastanda	Friend (IOI14_friend)	C++11	35 / 100	3 ms	2816 KiB

friend

// M
#include<bits/stdc++.h>
#include "friend.h"
using namespace std;
const int N = 100005;
int n, W[N], P[N], M[N];
vector < int > Ch[N];
pair < int , int > DFS(int v)
{
        M[v] = 1;
        pair < int , int > rs = {W[v], 0};
        for (int u : Ch[v])
        {
                pair < int , int > tmp = DFS(u);
                rs.first += tmp.second;
                rs.second += tmp.first;
        }
        rs.first = max(rs.first, rs.second);
        return rs;
}

int findSample(int _n, int confidence[], int host[], int protocol[])
{
        n = _n;
        for (int i = 0; i < n; i ++)
                W[i] = confidence[i], P[i] = i;
        for (int i = 1; i < n; i ++)
                if (protocol[i] == 1)
                        W[P[host[i]]] += W[i], P[i] = P[host[i]], W[i] = 0;
        for (int i = 1; i < n; i ++)
                if (protocol[i] == 2)
                        W[P[host[i]]] = max(W[P[host[i]]], W[P[i]]), P[i] = P[host[i]], W[i] = 0;
        for (int i = 1; i < n; i ++)
                if (protocol[i] == 0)
                        Ch[P[host[i]]].push_back(i), assert(P[i] == i);
        int tot = 0;
        for (int i = 0; i < n; i ++)
                if (!M[i])
                {
                        pair < int , int > tmp = DFS(i);
                        tot += max(tmp.first, tmp.second);
                }
        return tot;
}

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