답안 #59736 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59736	2018-07-23T02:01:19 Z	model_code	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	224 ms	17548 KB

minmaxtree

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #59736

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 22.0 / 22.0

Subtask #3 29.0 / 29.0

Subtask #4 42.0 / 42.0

Subtask #1
7.0 / 7.0

Subtask #2
22.0 / 22.0

Subtask #3
29.0 / 29.0

Subtask #4
42.0 / 42.0