Submission #59737

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
59737	2018-07-23 02:01:53	model_code	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	642 ms	35996 KiB

minmaxtree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
#define SZ(x) ((int) (x).size())
using namespace std;
const int INF = 0x3f3f3f3f;
class GeneralBipartiteMatcher {
public:
    GeneralBipartiteMatcher(int n, int m):
            adj(n), m(m) {}
    void addEdge(int from, int to) {
        adj[from].push_back(to);
    }
    vector<int> matching() const {
        int n = SZ(adj);
        vector<int> l(n, -1), r(m, -1);
        vector<bool> used(n, false);
        for (bool ok = true; ok; ) {
            ok = false;
            fill(used.begin(), used.end(), false);
            for (int node = 0; node < n; ++node) {
                if (l[node] == -1) {
                    ok |= pairUp(l, r, used, node);
                }
            }
        }
        return l;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 7 / 7
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 42 / 42