Submission #874108

#	Time	Username	Problem	Language	Result	Execution time	Memory
874108		simuyu	Friend (IOI14_friend)	C++14	16 / 100	1 ms	600 KiB

friend

#include <bits/stdc++.h>
//#include "friend.h"
using namespace std;
#define f first
#define s second

vector<int> adjlist[1001];
int types[1001];

void st5dfs(int node, int type) {
    if (types[node] != -1) return; // if go back to parent
    types[node] = type;
    for (int idx=0; idx<(int)adjlist[node].size(); idx++) {
        st5dfs( adjlist[node][idx] , 1-type ); // push neighbours to other colour
    }
}

int findSample(int n, int confidence[], int host[], int protocol[]) {
    int p = protocol[1];
    bool st234 = true;
    for (int idx=2; idx<n; idx++) {
        if (protocol[idx] != p) {
            st234=false;
            break;
        }
    }

    if (st234 && p>0) { // RMBR TO REMOVE P>0 LATER
        // subtasks 2, 3, 4
        if (p==0) { // IAmYourFriend, st4

            /*
            // just get all pairs by host and host index
            int res = 0;
            for (int guest=1; guest<n; guest++) {
                res = max(res, confidence[host[guest]] + confidence[guest] );
            }
            return res;
            */

            // THIS FORMS A TREE!!

            // prep for bfs to bipartite graph
            vector<int> adjlist[n];
            for (int guest=1; guest<n; guest++) {
                adjlist[host[guest]].push_back(guest);
                adjlist[guest].push_back(host[guest]);
            }

            int types[n];
            for (int i=0; i<n; i++) types[i] = -1;
            // bfs
            queue<pair<int, int> > q;
            q.push(pair<int,int>(0,0));

            pair<int,int> data;
            while (!q.empty()) {
                data = q.front(); q.pop();
                if (types[data.f] != -1) continue; // if go back to parent
                types[data.f] = data.s;
                for (int idx=0; idx<(int)adjlist[data.f].size(); idx++) {
                    q.push(pair<int,int>( adjlist[data.f][idx] , 1-data.s ) ); // push neighbours to other colour
                }
            }

            int res0=0, res1=0;
            for (int i=0; i<n; i++) {
                if (types[i] == 0) res0 += confidence[i];
                else res1 += confidence[i];
            }

            //cout << "HEYYYYYY" << endl;
            //cout << res0 << ' ' << res1 << endl;

            return max(res0, res1);

        } else if (p==2) { // MyFriendsAreYourFriends, st3
            // nobody is freinds lol, just get max
            int res = 0;
            for (int person=0; person<n; person++) {
                res = max(res, confidence[person]);
            }
            return res;

        } else if (p==1) { // WeAreYourFriends, st2
            // it's just all of them summed up
            int res = 0;
            for (int person=0; person<n; person++) {
                res += confidence[person];
            }
            return res;

        } else {
            // smtg weird
            return -1;

        }
    } else {
        // check if st5
        bool st5 = true;
        for (int i=0; i<n; i++) {
            if (confidence[i] != 1) {
                st5 = false;
                break;
            }
        }

        if (st5) {
            // st5: bipartite graphs

            // prep adjlist
            for (int guest=1; guest<n; guest++) {
                if (protocol[guest] == 0) { // i am your friend
                    adjlist[host[guest]].push_back(guest);
                    adjlist[guest].push_back(host[guest]);
                } else if (protocol[guest] == 1) { // your friends are my friends
                    for (int idx=0; idx<(int)adjlist[host[guest]].size(); idx++) {
                        int person = adjlist[host[guest]][idx];
                        adjlist[person].push_back(guest);
                        adjlist[guest].push_back(person);
                    }
                }
            }

            // dfs each one
            bool completed[n];

            int res = 0, t0, t1;

            for (int i=0; i<n; i++) {
                if (completed[i]) continue;

                // prep types
                for (int j=0; j<n; j++) types[j] = -1;

                st5dfs(i, 0); // arbritrary 0

                t0=0; t1=0;
                for (int j=0; j<n; j++) {
                    if (types[j] == -1) continue;
                    completed[j] = true;
                    if (types[j] == 0) t0++;
                    else t1++;
                }

                res += max(t0, t1);
            }

            return res;

        } else {
            // do whole graph with all. st1 or st5 (or unsolved st6)
            return 0; // TODO
        }
    }

}

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