oj.uz

Submission #61518

# Submission time Handle Problem Language Result Execution time Memory
61518 2018-07-26T06:31:08 Z 강태규(#1777) Min-max tree (BOI18_minmaxtree) C++11
36 / 100
 1000 ms 18560 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n;
const int inf = 1e9 + 7;

struct query {
    int x, y, z;
    char scan() {
        static char in[10];
        scanf("%s%d%d%d", in, &x, &y, &z);
        return *in;
    }
};

vector<int> edge[70001];
vector<query> qs[256];
int par[70001][17];
int nxt[70001];
int dep[70001];

void dfs(int x, int p) {
    par[x][0] = p;
    dep[x] = dep[p] + 1;
    for (int i = 1; i < 17; ++i) {
        par[x][i] = par[par[x][i - 1]][i - 1];
    }
    for (int i : edge[x]) {
        if (i == p) continue;
        dfs(i, x);
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 17; i--; ) {
        if ((dep[x] - dep[y]) >> i) x = par[x][i];
    }
    if (x == y) return x;
    for (int i = 17; i--; ) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}

int mn[70001];
int mx[70001];

int paint(int c[], int s, int e, int x) {
    if (dep[s] <= dep[e]) return s;
    if (c[s]) nxt[s] = paint(c, nxt[s], e, x);
    c[s] = x;
    return nxt[s] = paint(c, par[s][0], e, x);
}

int find(vector<int> &v, int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

struct matching {
    vector<int> edge[70001];
    int mat[70001];
    int rev[70001];
    int visited[70001];
    int lv[70001];
    int n;
    
    void bfs() {
        queue<int> q;
        for (int i = 2; i <= n; ++i) {
            if (visited[i]) lv[i] = inf;
            else lv[i] = 0, q.push(i);
        }
        
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int i : edge[x]) {
                if (rev[i]) {
                    if (lv[rev[i]] < inf) continue;
                    lv[rev[i]] = lv[x] + 1;
                    q.push(rev[i]);
                }
            }
        }
    }
    
    int dfs(int x) {
        for (int i : edge[x]) {
            if (rev[i] == 0 || lv[rev[i]] == lv[x] + 1 && dfs(rev[i])) {
                visited[x] = 1;
                mat[x] = i;
                rev[i] = x;
                return 1;
            }
        }
        return 0;
    }
    
    int process(int N) {
        n = N;
        int ret = 0;
        while (1) {
            bfs();
            int res = 0;
            for (int i = 2; i <= n; ++i) {
                if (visited[i]) continue;
                res += dfs(i);
            }
            if (res == 0) break;
            ret += res;
        }
        return ret;
    }
} mt;

int ans[70001];

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    dfs(1, 0);
    int k;
    scanf("%d", &k);
    vector<int> cp;
    for (int i = 0; i < k; ++i) {
        query q;
        char c = q.scan();
        qs[c].push_back(q);
        cp.push_back(q.z);
    }
    cp.push_back(0);
    sort(cp.begin(), cp.end());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    
    sort(qs['m'].begin(), qs['m'].end(), [&](const query &x, const query &y) {
        return x.z < y.z;
    });
    sort(qs['M'].begin(), qs['M'].end(), [&](const query &x, const query &y) {
        return x.z > y.z;
    });
    
    for (query i : qs['m']) {
        int p = lca(i.x, i.y);
        paint(mn, i.x, p, i.z);
        paint(mn, i.y, p, i.z);
    }
    
    for (query i : qs['M']) {
        int p = lca(i.x, i.y);
        paint(mx, i.x, p, i.z);
        paint(mx, i.y, p, i.z);
    }
    
    for (int i = 2; i <= n; ++i) {
        if (mn[i]) mt.edge[i].push_back(find(cp, mn[i]));
        if (mx[i]) mt.edge[i].push_back(find(cp, mx[i]));
    }
    
    mt.process(n);
    
    for (int i = 1; i < cp.size(); ++i) {
        ans[mt.rev[i]] = cp[i];
    }
    
    for (int i = 2; i <= n; ++i) {
        printf("%d %d %d\n", i, par[i][0], ans[i] ? ans[i] : (mn[i]));
    }
    
	return 0;
}

Compilation message

minmaxtree.cpp: In member function 'int matching::dfs(int)':
minmaxtree.cpp:110:56: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             if (rev[i] == 0 || lv[rev[i]] == lv[x] + 1 && dfs(rev[i])) {
                                ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:154:13: warning: array subscript has type 'char' [-Wchar-subscripts]
         qs[c].push_back(q);
             ^
minmaxtree.cpp:187:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < cp.size(); ++i) {
                     ~~^~~~~~~~~~~
minmaxtree.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
minmaxtree.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~
minmaxtree.cpp:149:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
minmaxtree.cpp: In member function 'char query::scan()':
minmaxtree.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s%d%d%d", in, &x, &y, &z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3576 KB Output is correct
2 Correct 6 ms 3684 KB Output is correct
3 Correct 6 ms 3736 KB Output is correct
4 Correct 6 ms 3736 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 14928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 16240 KB Output is correct
2 Correct 160 ms 16432 KB Output is correct
3 Correct 198 ms 17588 KB Output is correct
4 Correct 154 ms 18560 KB Output is correct
5 Correct 157 ms 18560 KB Output is correct
6 Correct 193 ms 18560 KB Output is correct
7 Correct 179 ms 18560 KB Output is correct
8 Correct 173 ms 18560 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3576 KB Output is correct
2 Correct 6 ms 3684 KB Output is correct
3 Correct 6 ms 3736 KB Output is correct
4 Correct 6 ms 3736 KB Output is correct
5 Execution timed out 1062 ms 14928 KB Time limit exceeded
6 Halted 0 ms 0 KB -