Submission #90948

#	Time	Username	Problem	Language	Result	Execution time	Memory
90948		choikiwon	Min-max tree (BOI18_minmaxtree)	C++17	0 / 100	375 ms	33256 KiB

minmaxtree

#include<bits/stdc++.h>
using namespace std;

const int MN = 70010;

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();
        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();
        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 (stderr)

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);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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