Submission #421000

#	Time	Username	Problem	Language	Result	Execution time	Memory
421000		marcipan5000	Friend (IOI14_friend)	C++14	69 / 100	41 ms	4344 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>

using namespace std;

bool q1=1,q2=1,q3=1;
int n1;
int ans=0;
int uu;



int conff[1002];
vector<int> t[1002];
bool z[15];
int w=0;
void rek(int p) {
    if (p==n1) {
        for (int i=0;i<n1;i++) {
            if (z[i]==1) {
                for (int j=0;j<t[i].size();j++) {
                    if (z[t[i][j]]==1) {
                        return;
                    }
                }
            }
        }
        ans=max(ans,w);
        return;
    }
    z[p]=0;
    rek(p+1);
    z[p]=1; w+=conff[p];
    rek(p+1);
    z[p]=0; w-=conff[p];
    return;
}

const int maxn = (int)1e3;

vector<bool> volt;
vector<int> par;
bool javit(int akt, bool p){
    volt[akt] = true;
    if(par[akt] != -1 && p)
        return javit(par[akt], !p);
    for(int x : t[akt]){
        if(!volt[x] && (par[x] == -1 || javit(x, !p))){
            par[akt] = x;
            par[x] = akt;
            return true;
        }
    }
    return false;
}

int subtask5(int n){
    par.assign(n, -1);
    int maxmatching = 0;
    for(int i = 0; i < n; i++){
        volt.assign(n, false);
        if(par[i] == -1 && javit(i, false))
            maxmatching++;
    }
    return n-maxmatching;
}

bool vo[1002];
pair<int,int> z2;
pair<int,int> dfs(int p) {
    vo[p]=1;
    pair<int,int> ans;
    ans.first=0;
    ans.second=0;
    for (int i=0;i<t[p].size();i++) {
        if (vo[t[p][i]]==0) {
            z2=dfs(t[p][i]);
            ans.second+=max(z2.first,z2.second);
            ans.first+=z2.second;
        }
    }
    ans.first+=conff[p];
    return(ans);
}

int findSample(int n,int confidence[],int host[],int protocol[]) {
    n1=n;
    for (int i=1;i<n;i++) {
        if (protocol[i]!=0) {
            q1=0;
        }
        if (protocol[i]!=1) {
            q2=0;
        }
        if (protocol[i]!=2) {
            q3=0;
        }
    }
    for (int i=0;i<n;i++) {
        conff[i]=confidence[i];
    }
    for (int i=1;i<n;i++) {
            if (protocol[i]==0) {
               t[i].push_back(host[i]);
               t[host[i]].push_back(i);
            }
            if (protocol[i]==1) {
                uu=t[host[i]].size();
                for (int j=0;j<uu;j++) {
                    t[i].push_back(t[host[i]][j]);
                    t[t[host[i]][j]].push_back(i);
                }
            }
            if (protocol[i]==2) {
                uu=t[host[i]].size();
                for (int j=0;j<uu;j++) {
                    t[i].push_back(t[host[i]][j]);
                    t[t[host[i]][j]].push_back(i);
                }
                t[i].push_back(host[i]);
                t[host[i]].push_back(i);
            }
    }
    if (q3==1) {
        int ma=0;
        for (int i=0;i<n;i++) {
            ma=max(ma,confidence[i]);
        }
        return(ma);
    }
    if (q2==1) {
        int ma=0;
        for (int i=0;i<n;i++) {
            ma=ma+confidence[i];
        }
        return(ma);
    }
    if (q1==1) {
        z2=dfs(0);
        return(max(z2.first,z2.second));
    }


    if (n<=10) {


            /*
            for (int i2=0;i2<=i;i2++) {
                for (int j=0;j<t[i2].size();j++) {
                    cout << t[i2][j] << " ";
                }
                    cout << endl;
                }
            cout << endl;
            */


        rek(0);
        return(ans);
    }
    return(subtask5(n));
}

Compilation message (stderr)

friend.cpp: In function 'void rek(int)':
friend.cpp:21:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |                 for (int j=0;j<t[i].size();j++) {
      |                              ~^~~~~~~~~~~~
friend.cpp: In function 'std::pair<int, int> dfs(int)':
friend.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i=0;i<t[p].size();i++) {
      |                  ~^~~~~~~~~~~~

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