Submission #735018

#	Time	Username	Problem	Language	Result	Execution time	Memory
735018		Nhoksocqt1	Burza (COCI16_burza)	C++17	0 / 160	2 ms	344 KiB

burza

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

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
    inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
    inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}


class MaxFlowMinCost {
    public:
        struct Edge {
            int from, to, capa, flow, cost;
            Edge(int _u = 0, int _v = 0, int _ca = 0, int _co = 0) {
                flow = 0;
                from = _u, to = _v, capa = _ca, cost = _co;
            }

            int residual(void) const {
                return capa - flow;
            }
        };

        vector<vector<int>> adj;
        vector<Edge> E;
        vector<int> dist, tr;
        int n;

        MaxFlowMinCost(int _n = 0) {
            n = _n;
            adj.assign(_n + 7, vector<int>());
            E.clear();

            dist = vector<int>(_n + 7);
            tr = vector<int>(_n + 7);
        }

        void addEdge(int u, int v, int ca, int co) {
            adj[u].push_back(E.size());
            E.push_back(Edge(u, v, ca, co));
            adj[v].push_back(E.size());
            E.push_back(Edge(v, u, 0, -co));
        }

        bool FordBellman(int s, int t) {
            for (int i = 1; i <= n; ++i) {
                dist[i] = 1e9+7;
                tr[i] = 1;
            }

            queue<int> qu;
            vector<bool> inq = vector<bool>(n + 7, false);

            inq[s] = 1, dist[s] = 0;
            qu.push(s);

            while(!qu.empty()) {
                int u(qu.front());
                qu.pop();

                inq[u] = 0;
                for (auto &it : adj[u]) {
                    if(E[it].residual() > 0) {
                        int v(E[it].to);
                        if(dist[v] > dist[u] + E[it].cost) {
                            dist[v] = dist[u] + E[it].cost;
                            tr[v] = it;

                            if(!inq[v]) {
                                inq[v] = 1;
                                qu.push(v);
                            }
                        }
                    }
                }
            }

            return (dist[t] < 1e9+7);
        }

        ii getFlow(int s, int t) {
            for (int i = 0; i < int(E.size()); ++i) {
                E[i].flow = 0;
            }

            int totFlow(0), totCost(0);
            while(FordBellman(s, t)) {
                int delta(1e9+7);
                for (int u = t; u != s; u = E[tr[u]].from)
                    delta = min(delta, E[tr[u]].residual());

                for (int u = t; u != s; u = E[tr[u]].from) {
                    E[tr[u]].flow += delta;
                    E[tr[u] ^ 1].flow -= delta;
                }

                totFlow += delta;
                totCost += delta * dist[t];
            }

            return ii(totFlow, totCost);
        }
} G;

const int MAXN = 404;

vector<int> adj[MAXN];
int numLeaf[MAXN], depth[MAXN], pa[MAXN], numNode, numTurn;

void dfs(int u, int p) {
    numLeaf[u] = (depth[u] == numTurn);
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it]);
        if(v != p) {
            depth[v] = 1 + depth[u];
            pa[v] = u;
            dfs(v, u);

            numLeaf[u] += numLeaf[v];
        }
    }
}

void process() {
    cin >> numNode >> numTurn;
    for (int i = 1; i < numNode; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, -1);

    //for (int i = 1; i <= numNode; ++i)
    //    cout << depth[i] << ' ' << numLeaf[i] << '\n';

    if(numLeaf[1] == 0 || numTurn >= numLeaf[1]) {
        cout << "DA\n";
        return;
    }

    G = MaxFlowMinCost(numNode + numTurn + 2);
    int source(numNode + numTurn + 1), sink(1 + source);
    for (int i = 1; i <= numTurn; ++i) {
        G.addEdge(source, numNode + i, 1, 0);
        if(i > 1)
            G.addEdge(numNode + i, numNode + i - 1, 1e9+7, 0);

        for (int j = 1; j <= numNode; ++j) {
            if(depth[j] == i) {
                G.addEdge(numNode + i, j, 1, -numLeaf[j]);
            }
        }
    }

    G.addEdge(1, sink, 1e9+7, 0);
    for (int i = 2; i <= numNode; ++i)
        G.addEdge(i, pa[i], 1e9+7, 0);

    ii res = G.getFlow(source, sink);
    //cout << res.fi << ' ' << -res.se << ": ";
    if(-G.getFlow(source, sink).se == numLeaf[1]) {
        cout << "DA\n";
    } else {
        cout << "NE\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    process();
    return 0;
}

Compilation message (stderr)

burza.cpp: In function 'void process()':
burza.cpp:173:8: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  173 |     ii res = G.getFlow(source, sink);
      |        ^~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16