Submission #1184343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184343		pensive	Friend (IOI14_friend)	C++20	27 / 100	219 ms	131072 KiB

friend

#include <iostream>
#include <algorithm>
#include <vector>
#include <algorithm>


using namespace std;
#define ll long long
#define REP(a,i,n) for (int i=a;i<n;i++)
#define f first
#define s second

void iayf(int n, int i, int host, vector<vector<int>> &adjList) {
    adjList[host].push_back(i);
    adjList[i].push_back(host);
}
void mfayf(int n, int i, int host, vector<vector<int>> &adjList) {
    for (auto j : adjList[host]) {
        adjList[j].push_back(i);
        adjList[i].push_back(j);
    }
}
void wayf(int n, int i, int host, vector<vector<int>> &adjList) {
    mfayf(n,i,host,adjList);
    iayf(n, i, host, adjList);
}
int maxSample(int n, int i, vector<vector<int>> &adjList, vector<int> &includes, int confidence[]) {
    if (i==n) {
        return 0;
    }
    int cleared=0;
    for (auto j : adjList[i]) {
        cleared += includes[j];
    }
    int ans= maxSample(n,i+1,adjList,includes,confidence);
    if (cleared==0) {
        includes[i]=1;
        ans = max(ans, confidence[i]+maxSample(n,i+1,adjList,includes,confidence));
        includes[i]=0;
    }
    return ans;
}

int memoing(int n, int node, int parent, vector<vector<int>> &adjList, vector<pair<int,int> > &memo, int confidence[]) {
    if (memo[node].f == -1) {
        if (adjList[node].size()==0) { //alone
            memo[node].f =0;
            memo[node].s = confidence[node];
        }
        else if (adjList[node].size()==1 && adjList[node][0]==parent) { //leaf
            memo[node].f =0;
            memo[node].s = confidence[node];
        }
        else {
            int sm=0, sm2=0;
            for (auto j : adjList[node]) {
                sm += memoing(n, j, node, adjList, memo, confidence);
                sm2 += memo[j].s;
            }
            memo[node].f= sm; memo[node].s= sm2;
        }
    }
    return max(memo[node].f, memo[node].s);
}

int findSample(int n, int confidence[], int host[], int protocol[]) {
    if (n>10 && protocol[1]==1) {
        int sm=0;
        REP(0,i,n) {
            sm += confidence[i];
        }
        return sm;
    }
    vector<vector<int> > adjList(n);
    REP(1,i,n) {
        if (protocol[i]==0) iayf(n,i,host[i],adjList);
        else if (protocol[i]==1) mfayf(n,i,host[i],adjList);
        else if (protocol[i]==2) wayf(n,i,host[i],adjList);
    }
    if (n>10 && protocol[1]==0) {
        vector<pair<int,int> > memo(n,{-1,-1});
        return memoing(n,0,-1,adjList,memo,confidence);
    }
    vector<int> includes(n, 0);
    return maxSample(n,0,adjList,includes,confidence);
} 

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