Submission #1017294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017294		Ice_man	Friend (IOI14_friend)	C++14	27 / 100	47 ms	65536 KiB

friend

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <assert.h>

#include "friend.h"

#define maxn 1005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

using namespace std;


typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;
typedef long double ld;


std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}


vector <int> v[maxn];
bool nb[maxn][maxn];

void add(int a, int b)
{
    v[a].pb(b);
    v[b].pb(a);

    nb[a][b] = true;
    nb[b][a] = true;
}


int dp[maxn][2];
int c[maxn];

bool used[maxn];

void dfs(int node, int par)
{
    used[node] = true;
    dp[node][1] = c[node];

    for(int& e : v[node])
    {
        if(e == par)
            continue;

        dfs(e, node);

        dp[node][1] += dp[e][0];
        dp[node][0] += max(dp[e][0], dp[e][1]);
    }
}


int findSample(int n, int confidence[], int host[], int protocol[])
{
    for(int i = 0; i < n; i++)
        c[i] = confidence[i];

    for(int i = 1; i < n; i++)
        if(protocol[i] == 0)
            add(host[i], i);
        else if(protocol[i] == 1)
            for(int& e : v[host[i]])
                add(e, i);
        else
        {
            for(int& e : v[host[i]])
                add(e, i);
            add(host[i], i);
        }

    int ans = 0;

    for(int node = 0; node < n; node++)
        if(used[node] == false)
        {
            dfs(node , n + 1);
            ans += max(dp[node][0] , dp[node][1]);
        }
    return ans;
}
















/**int main()
{

#ifdef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ///startT = std::chrono::high_resolution_clock::now();

    add(1 , 1 , 10 , 2 , 9 , 4);
    _remove(1 , 1 , 10 , 5 , 10 , 1);
    _remove(1 , 1 , 10 , 4 , 7 , 5);
    add(1 , 1 , 10 , 1 , 6 , 3);
    add(1 , 1 , 10 , 3 , 3 , 5);
    _remove(1 , 1 , 10 , 7 , 8 , 0);

    answer(1 , 1 , 10);
    for(int i = 0; i < 10; i++)
        cout << ans[i] << " ";
    cout << endl;



    return 0;
}
*/

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