답안 #90953

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90953 2018-12-25T09:58:24 Z choikiwon Min-max tree (BOI18_minmaxtree) C++17
100 / 100
532 ms 104384 KB
#include<bits/stdc++.h>
using namespace std;

const int MN = 200010;

struct BIT {
    vector<int> tree;
    void init() {
        tree = vector<int>(4 * MN, 2e9);
    }
    void upd(int idx, int val, int l, int r, int n) {
        if(idx < l || r < idx) return;
        if(l == r) {
            tree[n] = val;
            return;
        }
        int m = (l + r)>>1;
        upd(idx, val, l, m, 2*n);
        upd(idx, val, m + 1, r, 2*n + 1);
        tree[n] = min(tree[2*n], tree[2*n + 1]);
    }
    int quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return 2e9;
        if(a <= l && r <= b) return tree[n];
        int m = (l + r)>>1;
        int L = quer(a, b, l, m, 2*n);
        int R = quer(a, b, m + 1, r, 2*n + 1);
        return min(L, R);
    }
} bit;

int N, M;
vector<int> adj[MN];
int lo[MN], hi[MN];
int par[20][MN], dep[MN], tin[MN], tout[MN], invt[MN], timer;

void dfs0(int u, int p) {
    tin[u] = timer++;

    par[0][u] = p;
    for(int i = 1; i < 20; i++) {
        int t = par[i - 1][u];
        if(t == -1) break;
        par[i][u] = par[i - 1][t];
    }
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if(v == p) continue;
        dep[v] = dep[u] + 1;
        dfs0(v, u);
    }
    tout[u] = timer;
}

int lca(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    int diff = dep[a] - dep[b];
    for(int i = 0; i < 20; i++) if(diff & (1 << i)) a = par[i][a];
    if(a == b) return a;
    for(int i = 20; i--;) {
        if(par[i][a] != par[i][b]) {
            a = par[i][a];
            b = par[i][b];
        }
    }
    return par[0][a];
}

struct Query {
    char t;
    int x, w, z;
    bool operator <(const Query &i) const {
        if(tin[x] != tin[i.x]) return tin[x] < tin[i.x];
        if(w != i.w) return w < i.w;
        if(z != i.z) return z < i.z;
        return false;
    }
};
vector<Query> query;
unordered_map<int, int> H;
int Z[MN];
vector<int> rem[MN];

void dfs1(int u, int p) {
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if(v == p) continue;
        dfs1(v, u);
    }

    for(int i = 0; i < rem[u].size(); i++) {
        bit.upd(rem[u][i], 2e9, 0, MN - 1, 1);
    }
    if(p != -1) {
        int a = lower_bound(query.begin(), query.end(), (Query){ 'M', u, -1, -1  }) - query.begin();
        int b = lower_bound(query.begin(), query.end(), (Query){ 'M', invt[ tout[u] - 1 ], (int)1e9, (int)1e9 }) - query.begin() - 1;
        hi[u] = bit.quer(a, b, 0, MN - 1, 1);
    }
}

void dfs2(int u, int p) {
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if(v == p) continue;
        dfs2(v, u);
    }

    for(int i = 0; i < rem[u].size(); i++) {
        bit.upd(rem[u][i], 2e9, 0, MN - 1, 1);
    }
    if(p != -1) {
        int a = lower_bound(query.begin(), query.end(), (Query){ 'm', u, -1, -1  }) - query.begin();
        int b = lower_bound(query.begin(), query.end(), (Query){ 'm', invt[ tout[u] - 1 ], (int)1e9, (int)1e9 }) - query.begin() - 1;
        lo[u] = -bit.quer(a, b, 0, MN - 1, 1);
    }
}

vector<int> bip[MN << 1];
queue<int> q;
int vis[MN << 1], deg[MN << 1], ans[MN];

void dfs3(int u) {
    vis[u] = 1;

    for(int i = 0; i < bip[u].size(); i++) {
        int v = bip[u][i];
        if(vis[v]) continue;
        if(v < N) {
            ans[v] = u - N;
        }
        dfs3(v);
        return;
    }
}

void max_matching() {
    for(int i = 0; i < M; i++) deg[N + i] = bip[N + i].size();
    for(int i = 0; i < M; i++) if(deg[N + i] == 1) {
        q.push(N + i);
        vis[N + i] = 1;
    }
    while(!q.empty()) {
        int u = q.front(); q.pop();

        for(int i = 0; i < bip[u].size(); i++) {
            int v = bip[u][i];
            if(vis[v]) continue;
            vis[v] = 1;
            ans[v] = u - N;

            for(int j = 0; j < bip[v].size(); j++) {
                int w = bip[v][j];
                if(w == u) continue;
                deg[w]--;
                if(deg[w] == 1) {
                    q.push(w);
                    vis[w] = 1;
                }
            }
        }
    }

    for(int i = 0; i < M; i++) if(!vis[N + i]) {
        dfs3(N + i);
    }
}

int main() {
    scanf("%d", &N);

    for(int i = 0; i < N - 1; i++) {
        int u, v; scanf("%d %d", &u, &v);
        u--; v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    memset(par, -1, sizeof(par));
    dfs0(0, -1);
    for(int i = 0; i < N; i++) invt[tin[i]] = i;

    scanf("%d", &M);

    for(int i = 0; i < M; i++) {
        char t; int x, y, z; scanf("\n%c %d %d %d", &t, &x, &y, &z);
        x--; y--;

        int w = lca(x, y);
        query.push_back({ t, x, w, z });
        query.push_back({ t, y, w, z });
        H[z] = i;
        Z[i] = z;
    }

    sort(query.begin(), query.end());

    bit.init();
    for(int i = 0; i < query.size(); i++) {
        if(query[i].t == 'M') {
            bit.upd(i, query[i].z, 0, MN - 1, 1);
            rem[ query[i].w ].push_back(i);
        }
    }

    dfs1(0, -1);

    for(int i = 0; i < N; i++) rem[i].clear();
    bit.init();
    for(int i = 0; i < query.size(); i++) {
        if(query[i].t == 'm') {
            bit.upd(i, -query[i].z, 0, MN - 1, 1);
            rem[ query[i].w ].push_back(i);
        }
    }

    dfs2(0, -1);

    /*
    for(int i = 1; i < N; i++) {
        cout << lo[i] << ' ' << hi[i] << endl;
    }
    //*/

    for(int i = 1; i < N; i++) {
        if(lo[i] != -2e9) {
            bip[i].push_back(N + H[ lo[i] ]);
            bip[ N + H[ lo[i] ] ].push_back(i);
        }
        if(hi[i] != 2e9) {
            bip[i].push_back(N + H[ hi[i] ]);
            bip[ N + H[ hi[i] ] ].push_back(i);
        }
    }

    memset(ans, -1, sizeof(ans));
    max_matching();

    for(int i = 1; i < N; i++) {
        if(ans[i] == -1) printf("%d %d %d\n", i + 1, par[0][i] + 1, hi[i]);
        else printf("%d %d %d\n", i + 1, par[0][i] + 1, Z[ ans[i] ]);
    }
}

Compilation message

minmaxtree.cpp: In function 'void dfs0(int, int)':
minmaxtree.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dfs1(int, int)':
minmaxtree.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
minmaxtree.cpp:91:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < rem[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dfs2(int, int)':
minmaxtree.cpp:102:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
minmaxtree.cpp:108:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < rem[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dfs3(int)':
minmaxtree.cpp:125:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < bip[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void max_matching()':
minmaxtree.cpp:145:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < bip[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~
minmaxtree.cpp:151:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < bip[v].size(); j++) {
                            ~~^~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:199:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < query.size(); i++) {
                    ~~^~~~~~~~~~~~~~
minmaxtree.cpp:210:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < query.size(); i++) {
                    ~~^~~~~~~~~~~~~~
minmaxtree.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
minmaxtree.cpp:172:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf("%d %d", &u, &v);
                   ~~~~~^~~~~~~~~~~~~~~~~
minmaxtree.cpp:183:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &M);
     ~~~~~^~~~~~~~~~
minmaxtree.cpp:186:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         char t; int x, y, z; scanf("\n%c %d %d %d", &t, &x, &y, &z);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 41080 KB Output is correct
2 Correct 37 ms 41080 KB Output is correct
3 Correct 38 ms 41196 KB Output is correct
4 Correct 37 ms 41228 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 499 ms 60932 KB Output is correct
2 Correct 396 ms 60932 KB Output is correct
3 Correct 401 ms 62068 KB Output is correct
4 Correct 365 ms 69240 KB Output is correct
5 Correct 341 ms 69240 KB Output is correct
6 Correct 351 ms 69240 KB Output is correct
7 Correct 354 ms 70264 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 70264 KB Output is correct
2 Correct 203 ms 70264 KB Output is correct
3 Correct 288 ms 70264 KB Output is correct
4 Correct 227 ms 70264 KB Output is correct
5 Correct 248 ms 70264 KB Output is correct
6 Correct 306 ms 70264 KB Output is correct
7 Correct 309 ms 70264 KB Output is correct
8 Correct 306 ms 70264 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 41080 KB Output is correct
2 Correct 37 ms 41080 KB Output is correct
3 Correct 38 ms 41196 KB Output is correct
4 Correct 37 ms 41228 KB Output is correct
5 Correct 499 ms 60932 KB Output is correct
6 Correct 396 ms 60932 KB Output is correct
7 Correct 401 ms 62068 KB Output is correct
8 Correct 365 ms 69240 KB Output is correct
9 Correct 341 ms 69240 KB Output is correct
10 Correct 351 ms 69240 KB Output is correct
11 Correct 354 ms 70264 KB Output is correct
12 Correct 206 ms 70264 KB Output is correct
13 Correct 203 ms 70264 KB Output is correct
14 Correct 288 ms 70264 KB Output is correct
15 Correct 227 ms 70264 KB Output is correct
16 Correct 248 ms 70264 KB Output is correct
17 Correct 306 ms 70264 KB Output is correct
18 Correct 309 ms 70264 KB Output is correct
19 Correct 306 ms 70264 KB Output is correct
20 Correct 405 ms 71996 KB Output is correct
21 Correct 299 ms 72308 KB Output is correct
22 Correct 380 ms 74364 KB Output is correct
23 Correct 390 ms 76348 KB Output is correct
24 Correct 511 ms 86404 KB Output is correct
25 Correct 423 ms 90920 KB Output is correct
26 Correct 349 ms 92020 KB Output is correct
27 Correct 375 ms 92304 KB Output is correct
28 Correct 532 ms 92304 KB Output is correct
29 Correct 457 ms 93860 KB Output is correct
30 Correct 307 ms 93960 KB Output is correct
31 Correct 428 ms 96176 KB Output is correct
32 Correct 435 ms 99572 KB Output is correct
33 Correct 318 ms 100556 KB Output is correct
34 Correct 432 ms 102852 KB Output is correct
35 Correct 405 ms 104384 KB Output is correct