Submission #238475

#	Time	Username	Problem	Language	Result	Execution time	Memory
238475		nicolaalexandra	Friend (IOI14_friend)	C++14	35 / 100	9 ms	5248 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"
#define DIM 100010
using namespace std;

set <int> L[DIM];
int dp[DIM][2],t[DIM],sum[DIM],viz[DIM];
vector <pair<int,int> > mch;

int get_rad (int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}

void _union (int x, int y){
    int radx = get_rad(x), rady = get_rad(y);
    if (radx == rady)
        return;
    if (t[radx] > t[rady])
        swap (radx,rady);

    t[radx] += t[rady];
    t[rady] = radx;
    sum[radx] += sum[rady];
}

void dfs (int nod, int tata){

    viz[nod] = 1;
    for (auto vecin : L[nod]){
        if (vecin != tata)
            dfs (vecin,nod);
    }

    dp[nod][1] = sum[nod];
    for (auto vecin : L[nod]){
        if (vecin != tata){
            dp[nod][0] += max(dp[vecin][0],dp[vecin][1]);
            dp[nod][1] += dp[vecin][0];
        }}}

int findSample (int n, int confidence[], int host[], int tip[]){
    int i, nr0 = 0, nr1 = 0, nr2 = 0;
    for (i=1;i<n;i++){
        if (tip[i] == 0)
            nr0++;
        if (tip[i] == 1)
            nr1++;
        if (tip[i] == 2)
            nr2++;
    }
    if (nr1 == n-1){ /// nu am nicio muchie

        int sol = 0;
        for (i=0;i<n;i++)
            sol += confidence[i];

        return sol;
    }

    if (nr2 == n-1){ /// graf complet
        int sol = 0;
        for (i=0;i<n;i++)
            sol = max (sol,confidence[i]);
        return sol;
    }


    if (nr2 == 0){

        for (i=1;i<=n;i++){
            t[i] = -1;
            sum[i] = confidence[i-1];
        }

        for (i=1;i<n;i++){
            int x = host[i] + 1, y = i+1;

            if (tip[i] == 0) /// i am your friend
                mch.push_back(make_pair(x,y));
            else _union (x,y);

        }

        /// acum trb sa unesc toate multimele astea si se formeaza mai multi arbori

        for (auto it : mch){
            int x = it.first, y = it.second;
            int radx = get_rad(x), rady = get_rad(y);
            if (radx != rady){
                L[radx].insert(rady);
                L[rady].insert(radx);
            }
        }

        int sol = 0;

        for (i=1;i<=n;i++){
            if (!viz[i]){
                dfs (i,0);
                sol += max (dp[i][0],dp[i][1]);
            }}

        return sol;

    }
	/// acum devine mai complicat:)))
}

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:109:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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