Submission #404178

#	Time	Username	Problem	Language	Result	Execution time	Memory
404178		definitelynotmee	Friend (IOI14_friend)	C++98	19 / 100	1088 ms	65540 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MAXN = 0;

vector<int> cur;
int N;
int bt(int id, int confidence[], vector<vector<bool>> &isFriend){
    if(id == N){
        int resp = 0;
        for(int i : cur)
            resp+=confidence[i];
        return resp;
    }
    int ret = bt(id+1,confidence,isFriend);
    for(int i : cur){
        if(isFriend[i][id])
            return ret;
    }
    cur.push_back(id);
    ret = max(ret, bt(id+1,confidence,isFriend));
    cur.pop_back();
    return ret;
}

int findSample(int n, int confidence[], int host[], int protocol[]){
    N =n;
    vector<vector<bool>> isFriend(n, vector<bool> (n,0));
    for(int i = 1; i < n; i++){
        for(int j = 0; j < n; j++){
            isFriend[j][i] = isFriend[host[i]][j] && protocol[i];
            isFriend[i][j] = isFriend[j][i];
        }
        if(protocol[i] == 0 || protocol[i] == 2)
            isFriend[host[i]][i] = 1, isFriend[i][host[i]] = 1;
    }
    return bt(0,confidence,isFriend);
}

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