oj.uz

Submission #874111

# Submission time Handle Problem Language Result Execution time Memory
874111 2023-11-16T09:18:58 Z simuyu Friend (IOI14_friend) C++14
0 / 100
 0 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -