Submission #1063853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063853		kkzyr	Friend (IOI14_friend)	C++17	27 / 100	24 ms	2792 KiB

friend

#include <iostream>
#include <vector>
using namespace std;

bool a[10];

int answer;
vector<int> adj[1000];

void brute_force(int n, int confidence[], int choose, bool used[], int total_sum){
    if (choose == n){
        if (total_sum > answer){
            answer = total_sum;
        }
        return;
    }
    brute_force(n, confidence, choose + 1, used, total_sum);
    bool ok_add = true;
    for (int i = 0;i < adj[choose].size();i++){
        if (used[adj[choose][i]]){
            ok_add = false;
        }
    }
    if (ok_add){
        used[choose] = true;
        brute_force(n, confidence, choose + 1, used, total_sum + confidence[choose]);
        used[choose] = false;
    }
}

int done[1000];
int dp[1000][2];

void do_dp(int node, int confidence[]){
    done[node] = true;
    dp[node][1] = confidence[node];
    cout << node << ' ' << dp[node][1] << '\n';
    for (int i = 0;i < adj[node].size();i++){
        int child = adj[node][i];
        if (!done[child]){
            do_dp(child, confidence);
            dp[node][0] += max(dp[child][0], dp[child][1]);
            dp[node][1] += dp[child][0];
        }
    }
}

int parent[1000];
int ans_taken[1000];

void init(int n){
    for (int i = 0;i < n;i++){
        parent[i] = -1;
    }
}

int find(int x){
    if (parent[x] == -1){
        return x;
    }
    parent[x] = find(parent[x]);
    return parent[x];
}

void merge(int x, int y){
    int component1 = find(x);
    int component2 = find(y);
    if (component1 != component2){
        parent[component1] = component2;
    }
}

int findSample(int n, int confidence[], int host[], int protocol[]){
    if (n <= 10){
        for (int i = 1;i < n;i++){
            if (protocol[i] == 0){
                adj[host[i]].push_back(i);
                adj[i].push_back(host[i]);
            }
            else if (protocol[i] == 1){
                for (int j = 0;j < adj[host[i]].size();j++){
                    int child = adj[host[i]][j];
                    adj[child].push_back(i);
                    adj[i].push_back(child);
                }
            }
            else{
                adj[host[i]].push_back(i);
                adj[i].push_back(host[i]);
                for (int j = 0;j < adj[host[i]].size();j++){
                    int child = adj[host[i]][j];
                    adj[child].push_back(i);
                    adj[i].push_back(child);
                }
            }
        }
        brute_force(n, confidence, 0, a, 0);
        return answer;
    }
    bool all_one_kind = true;
    for (int i = 1;i < n - 1;i++){
        if (protocol[i] != protocol[i + 1]){
            all_one_kind = false;
            break;
        }
    }
    if (all_one_kind and protocol[1] == 0){
        for (int i = 0;i < n;i++){
            adj[host[i]].push_back(i);
            adj[i].push_back(host[i]);
        }
        do_dp(0, confidence);
        return max(dp[0][0], dp[0][1]);
    }
    else if (all_one_kind and protocol[1] == 1){
        int sum = 0;
        for (int i = 0;i < n;i++){
            sum += confidence[i];
        }
        return sum;
    }
    else{
        init(n);
        for (int i = 1;i < n;i++){
            merge(host[i], i);
        }
        for (int i = 0;i < n;i++){
            ans_taken[find(i)] = max(ans_taken[find(i)], confidence[i]);
        }
        int sum = 0;
        for (int i = 0;i < n;i++){
            sum += ans_taken[i];
        }
        return sum;
    }
}

Compilation message (stderr)

friend.cpp: In function 'void brute_force(int, int*, int, bool*, int)':
friend.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0;i < adj[choose].size();i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~
friend.cpp: In function 'void do_dp(int, int*)':
friend.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0;i < adj[node].size();i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:81:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |                 for (int j = 0;j < adj[host[i]].size();j++){
      |                                ~~^~~~~~~~~~~~~~~~~~~~~
friend.cpp:90:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                 for (int j = 0;j < adj[host[i]].size();j++){
      |                                ~~^~~~~~~~~~~~~~~~~~~~~

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