Submission #742700

#	Time	Username	Problem	Language	Result	Execution time	Memory
742700		vjudge1	친구 (IOI14_friend)	C++17	0 / 100	1 ms	340 KiB

friend

#include <bits/stdc++.h>
#include "friend.h"

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

vector<int> g[1005];
bool visited[1005];
int p[1005], col[1005];

int dfs(int n) {
    for (auto x : g[n]) {
        if (visited[x]) continue;
        visited[x] = 1;
        if (p[x] == -1 || dfs(p[x])) {
            p[x] = n;
            return 1;
        }
    }
    return 0;
}

int findSample(int n, int confidence[], int host[], int protocol[]) {
    memset(p, -1, sizeof(p));
    for (int i = 0; i < n; i++) {
        if (protocol[i] == 0) {
            g[host[i]].push_back(i);
            g[i].push_back(host[i]);
            col[i] = col[host[i]] ^ 1;
        }
    }
    int ans = n;
    for (int i = 0; i < n; i++) {
        if (col[i] == 0) {
            memset(visited, 0, sizeof(visited));
            ans -= dfs(i);
        }
    }
    return ans;
}

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