Submission #874111

#	Time	Username	Problem	Language	Result	Execution time	Memory
874111		simuyu	Friend (IOI14_friend)	C++14	0 / 100	0 ms	348 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[]) {
    // 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;

}

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