Submission #1313287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313287		Jer	Tug of War (BOI15_tug)	C++20	23 / 100	39 ms	5212 KiB

tug

#include <bits/stdc++.h>
using namespace std;

struct edge
{
    int to, cap, rev;
};

struct dinic
{
    vector<vector<edge>> g;
    vector<int> level, it;
    int n;

    dinic(int n) : n(n), g(n), level(n), it(n) {}

    void add_edge(int u, int v, int cap)
    {
        edge a = {v, cap, (int)g[v].size()};
        edge b = {u, 0, (int)g[u].size()};
        g[u].push_back(a);
        g[v].push_back(b);
    }

    bool bfs(int s, int t)
    {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto &e : g[u])
            {
                if (level[e.to] == -1 && e.cap > 0)
                {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1;
    }

    int dfs(int u, int t, int f)
    {
        if (!f || u == t)
            return f;
        for (int &i = it[u]; i < g[u].size(); i++)
        {
            auto &e = g[u][i];
            if (e.cap > 0 && level[e.to] == level[u] + 1)
            {
                int pushed = dfs(e.to, t, min(f, e.cap));
                if (pushed)
                {
                    e.cap -= pushed;
                    g[e.to][e.rev].cap += pushed;
                    return pushed;
                }
            }
        }
        return 0;
    }

    int max_flow(int s, int t)
    {
        int flow = 0;
        while (bfs(s, t))
        {
            fill(it.begin(), it.end(), 0);
            while (int pushed = dfs(s, t, INT_MAX))
                flow += pushed;
        }
        return flow;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> l(2 * n), r(2 * n), s(2 * n);
    for (int i = 0; i < 2 * n; i++)
        cin >> l[i] >> r[i] >> s[i];

    int S = 0;
    int C = 1;
    int L = C + 2 * n;
    int R = L + n;
    int T = R + n;
    int N = T + 1;

    dinic d(N);

    for (int i = 0; i < 2 * n; i++)
    {
        d.add_edge(S, C + i, 1);
        d.add_edge(C + i, L + (l[i] - 1), 1);
        d.add_edge(C + i, R + (r[i] - 1), 1);
    }

    for (int i = 0; i < n; i++)
    {
        d.add_edge(L + i, T, 1);
        d.add_edge(R + i, T, 1);
    }

    int flow = d.max_flow(S, T);

    if (flow == 2 * n)
        cout << "YES\n";
    else
        cout << "NO\n";
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 23 / 23
• Subtask 4: 0 / 29