oj.uz

Submission #59736

# Submission time Handle Problem Language Result Execution time Memory
59736 2018-07-23T02:01:19 Z model_code Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 224 ms 17548 KB 
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100000 + 5;

int N;
vector <int> tree[NMAX];
int fathers[NMAX], h[NMAX];
void dfs(int node) {
    for (auto it: tree[node])
        if (it != fathers[node]) {
            h[it] = 1 + h[node], fathers[it] = node;
            dfs(it);
        }
}

int father[NMAX], lowest[NMAX];
inline void init() {
    for (int i = 1; i <= N; ++ i)
        father[i] = lowest[i] = i;
}
inline int find(int node) {
    if (father[father[node]] != father[node])
        father[node] = find(father[node]);
    return father[node];
}
inline void unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b)
        return ;
    if (rand() & 1)
        father[a] = b;
    else
        father[b] = a, lowest[a] = lowest[b];
}

int queryValues[NMAX];
struct Query {
    int a, b, index;
    Query(int _a = 0, int _b = 0, int _index = 0):
        a(_a), b(_b), index(_index) {}
    friend bool operator<(const Query &arg0, const Query &arg1) {
        return queryValues[arg0.index] < queryValues[arg1.index];
    }
};
vector <Query> minQueries, maxQueries;

int lowerBound[NMAX], upperBound[NMAX];
void mark(int bound[], int a, int b, int index) {
    a = lowest[find(a)], b = lowest[find(b)];
    while (a != b) {
        if (h[a] > h[b])
            swap(a, b);
        bound[b] = index;
        unite(b, fathers[b]);
        b = lowest[find(b)];
    }
}

vector <int> matchGraph[NMAX];
int l[NMAX], r[NMAX];
bool vis[NMAX];

bool pairUp(int node) {
    if (vis[node])
        return false;
    vis[node] = true;
    for (auto it: matchGraph[node])
        if (!r[it] || pairUp(r[it])) {
            l[node] = it, r[it] = node;
            return true;
        }
    return false;
}

void hopcroft() {
    bool ok = true;
    while (ok) {
        ok = false;
        for (int i = 2; i <= N; ++ i)
            vis[i] = false;
        for (int i = 2; i <= N; ++ i)
            if (!l[i] && pairUp(i))
                ok = true;
    }
}

int main() {
    ios_base :: sync_with_stdio(false);
    //freopen("minmaxarb.in", "r", stdin);

    cin >> N;
    for (int i = 1; i < N; ++ i) {
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b), tree[b].push_back(a);
    }
    dfs(1);

    int M;
    cin >> M;

    for (int i = 1; i <= M; ++ i) {
        char type;
        cin >> type;

        int a, b, c;
        cin >> a >> b >> c;
        queryValues[i] = c;

        assert(c > 0);

        if (type == 'm')
            minQueries.emplace_back(a, b, i);
        else
            maxQueries.emplace_back(a, b, i);
    }

    sort(maxQueries.begin(), maxQueries.end());
    sort(minQueries.begin(), minQueries.end());
    reverse(minQueries.begin(), minQueries.end());

    init();
    for (auto it: maxQueries)
        mark(upperBound, it.a, it.b, it.index);
    init();
    for (auto it: minQueries)
        mark(lowerBound, it.a, it.b, it.index);

    for (int i = 2; i <= N; ++ i) {
        if (lowerBound[i])
            matchGraph[i].push_back(lowerBound[i]);
        if (upperBound[i])
            matchGraph[i].push_back(upperBound[i]);
    }

    hopcroft();
    for (int i = 2; i <= N; ++ i) {
        int val = queryValues[l[i]];
        if (!l[i]) {
            if (lowerBound[i])
                val = queryValues[lowerBound[i]];
            else
                val = 1;
        }
        cout << i << ' ' << fathers[i] << ' ' << val << '\n';
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5188 KB Output is correct
3 Correct 7 ms 5264 KB Output is correct
4 Correct 8 ms 5264 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 16040 KB Output is correct
2 Correct 190 ms 16040 KB Output is correct
3 Correct 180 ms 16040 KB Output is correct
4 Correct 218 ms 16616 KB Output is correct
5 Correct 148 ms 16616 KB Output is correct
6 Correct 151 ms 16616 KB Output is correct
7 Correct 156 ms 16616 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 16616 KB Output is correct
2 Correct 158 ms 16616 KB Output is correct
3 Correct 122 ms 16616 KB Output is correct
4 Correct 141 ms 16616 KB Output is correct
5 Correct 119 ms 16616 KB Output is correct
6 Correct 128 ms 16616 KB Output is correct
7 Correct 149 ms 16616 KB Output is correct
8 Correct 161 ms 16616 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5188 KB Output is correct
3 Correct 7 ms 5264 KB Output is correct
4 Correct 8 ms 5264 KB Output is correct
5 Correct 187 ms 16040 KB Output is correct
6 Correct 190 ms 16040 KB Output is correct
7 Correct 180 ms 16040 KB Output is correct
8 Correct 218 ms 16616 KB Output is correct
9 Correct 148 ms 16616 KB Output is correct
10 Correct 151 ms 16616 KB Output is correct
11 Correct 156 ms 16616 KB Output is correct
12 Correct 116 ms 16616 KB Output is correct
13 Correct 158 ms 16616 KB Output is correct
14 Correct 122 ms 16616 KB Output is correct
15 Correct 141 ms 16616 KB Output is correct
16 Correct 119 ms 16616 KB Output is correct
17 Correct 128 ms 16616 KB Output is correct
18 Correct 149 ms 16616 KB Output is correct
19 Correct 161 ms 16616 KB Output is correct
20 Correct 188 ms 16616 KB Output is correct
21 Correct 224 ms 16616 KB Output is correct
22 Correct 137 ms 16616 KB Output is correct
23 Correct 168 ms 16616 KB Output is correct
24 Correct 157 ms 16616 KB Output is correct
25 Correct 171 ms 17548 KB Output is correct
26 Correct 177 ms 17548 KB Output is correct
27 Correct 202 ms 17548 KB Output is correct
28 Correct 155 ms 17548 KB Output is correct
29 Correct 165 ms 17548 KB Output is correct
30 Correct 143 ms 17548 KB Output is correct
31 Correct 149 ms 17548 KB Output is correct
32 Correct 198 ms 17548 KB Output is correct
33 Correct 221 ms 17548 KB Output is correct
34 Correct 204 ms 17548 KB Output is correct
35 Correct 198 ms 17548 KB Output is correct