Submission #1168940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168940		anmattroi	Friend (IOI14_friend)	C++17	0 / 100	1 ms	328 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;

vector<int> adj[1005], g[1005];

int cl[1005], x[1005], y[1005], d[1005];

int N;

void pfs(int u) {
    for (int v : adj[u])
        if (cl[v] == -1) {
            cl[v] = 1-cl[u];
            pfs(v);
        }
}

int bfs() {
    queue<int> q;
    for (int u = 1; u <= N; u++)
    if (x[u] == 0) {
        q.push(u);
        d[u] = 0;
    } else d[u] = INT_MAX;
    d[0] = INT_MAX;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u])
        if (d[y[v]] == INT_MAX) {
            d[y[v]] = d[u] + 1;
            if (y[v]) q.push(y[v]);
        }
    }
    return d[0] != INT_MAX;
}

int dfs(int u) {
    if (u == 0) return 1;
    for (int v : adj[u])
        if (d[y[v]] == d[u] + 1)
            if (dfs(y[v])) {
                x[u] = v;
                y[v] = u;
                d[u] = INT_MAX;
                return 1;
            }
    d[u] = INT_MAX;
    return 0;
}

int maxmatch() {
    int ans = 0;
    while (bfs()) {
        for (int u = 1; u <= N; u++)
            if (x[u] == 0) if (dfs(u)) ++ans;
    }
    return ans;
}


int findSample(int n, int confidence[], int host[], int protocol[]){
    N = n;
    for (int i = 0; i < n; i++) {
        adj[i].clear();
        g[i].clear();
        cl[i] = -1;
        x[i] = y[i] = 0;
    }
    for (int i = 1; i < n; i++)
    if (protocol[i] == 1) {
        for (int v : adj[host[i]]) {
            adj[v].emplace_back(i);
            adj[i].emplace_back(v);
        }
    } else {
        adj[host[i]].emplace_back(i);
        adj[i].emplace_back(host[i]);
    }
    for (int i = 0; i < n; i++)
    if (cl[i] == -1) {
        cl[i] = 0;
        pfs(i);
    }
    for (int i = 0; i < n; i++)
        if (cl[i] == 0)
        for (int j : adj[i]) g[i].emplace_back(j);


    return n-maxmatch();
}
/*
6
1 1 1 1 1 1
0 0
0 1
1 0
2 1
0 0
*/
//4

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