제출 #1177570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177570		lam	Pictionary (COCI18_pictionary)	C++20	112 / 140	146 ms	77776 KiB

pictionary

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

#define _DEBUG 0

struct Tree {
    int n, root;
    vector <vector<int>> adj;
    vector <int> in, out, head, par, h, s;
    vector <int> euler;
    Tree(int n, vector<vector<int>> adj, int root) : n(n), adj(adj), root(root), in(n), out(n), 
    h(n), head(n), par(n), s(n), euler() {
        auto dfs = [&](auto dfs, int u, int p, int depth = 0) -> void {
            h[u] = depth;
            par[u] = p;
            s[u] = 1;
            for (int v : adj[u])
                if (v != p) {
                    dfs(dfs, v, u, depth + 1);
                    s[u] += s[v];
                }
        };
        dfs(dfs, root, root);

        auto build = [&](auto self, int u, int p, int _head) -> void {
            in[u] = euler.size();
            euler.push_back(u);
            head[u] = _head;
            int it = -1;
            for (int v : adj[u])
                if (v != p)
                    if (it == -1 || s[it] < s[v]) it = v;
            if (it != -1)
                self(self, it, u, _head);
            for (int v : adj[u])
                if (v != p && v != it) {
                    self(self, v, u, v);
                }
            out[u] = euler.size();
        };  

        build(build, root, root, root);
    }
    int lca(int u, int v) {
        while (head[u] != head[v]) {
            if (h[head[u]] > h[head[v]]) swap(u, v);
            v = par[head[v]];
        }
        if (h[u] > h[v]) swap(u, v);
        return u;
    }
};

template<class Info>
struct SegmentTree {
    vector <Info> f;
    int n;
    SegmentTree(int n, vector <Info> a) : n(n), f(4 * n, Info()) {
        auto dfs = [&](auto dfs, int x, int lx, int rx) -> void {
            if (lx + 1 == rx) {
                f[x] = a[lx];
                return;
            }
            int mid = (lx + rx) / 2;
            dfs(dfs, 2*x, lx, mid);
            dfs(dfs, 2*x + 1, mid, rx);
            pull(x);
        };
        dfs(dfs, 1, 0, n);
    }
    void modify(int idx, Info val) {
        auto dfs = [&](auto dfs, int x, int lx, int rx) -> void {
            if (lx + 1 == rx) {
                f[x] = val;
                return;
            }
            int mid = (lx + rx) / 2;
            if (idx < mid)
                dfs(dfs, 2*x, lx, mid);
            else
                dfs(dfs, 2*x + 1, mid, rx);
            pull(x);
        };
        dfs(dfs, 1, 0, n);
    }
    
    Info rangeQuery(int l, int r) {
        auto dfs = [&](auto dfs, int x, int lx, int rx) -> Info {
            if (lx >= r || rx <= l) return Info();
            if (lx >= l && rx <= r) return f[x];
            int mid = (lx + rx) / 2;
            return dfs(dfs, 2*x, lx, mid) + dfs(dfs, 2*x + 1, mid, rx);
        };
        return dfs(dfs, 1, 0, n);
    }

    void pull(int x) {
        f[x] = f[2*x] + f[2*x+1];
    }
    SegmentTree(int n) {
        SegmentTree(n, vector<Info>(n, Info()));
    }
};

struct Info {
    array<int, 2> mx = {0, 0};
    Info() {}
    Info(int x, int y) : mx({x, y}) {}
    Info operator+(const Info &b) {
        Info z;
        z.mx = max(mx, b.mx);
        return z;
    }

};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, m, q; cin >> n >> m >> q;

    vector <array<int, 3>> e;

    for (int i = m; i >= 1; i--) {
        for (int j = i + i; j <= n; j += i) {
            if (_DEBUG)  cout << j-1 << ',' << j-i-1 << ',' << m-i << '\n';
            e.push_back({j - 1, j - i - 1, m - i});
        }
    }
    { /// DSU tree
        vector <vector <int>> adj(n);
        vector <int> p(n), t(n, -1); iota(p.begin(), p.end(), 0);
        int root = 0;
        {

            auto regis = [&](int w = -1) -> int {
                int sz = p.size();
                p.push_back(sz);
                adj.push_back(vector<int>());
                t.push_back(w);
                return p.size() - 1;
            };
                
            auto addedge = [&](int u, int v) -> void {
                adj[u].push_back(v);
                adj[v].push_back(u);
            };

            auto get = [&](auto self, int u) -> int {
                return p[u] = (p[u] == u) ? u : self(self, p[u]);
            };

            auto U = [&](int u, int v, int time) -> void {
                u = get(get, u), v = get(get, v);
                if (u == v) return ;
                int x = regis(time);
                addedge(x, u);
                addedge(x, v);
                p[u] = p[v] = x;
                if (_DEBUG) cout << u << " & " << v << " --> " << x << " " << t[x] << endl;
                root = x;
            };

            for (int i = 0; i < e.size(); i++)
                U(e[i][0], e[i][1], e[i][2]);


            vector <int> rts;
            for (int i = 0; i < p.size(); i++) {
                if (i == get(get, i)) rts.push_back(i);
            } 
            if (rts.size() > 1) {
                for (int i = 1; i < rts.size(); i++) 
                    U(rts[i-1], rts[i], 2);
            }

        }

        Tree tree(p.size(), adj, root);

        for (int i = 0; i < q; i++) {
            int u, v; cin >> u >> v;
            u--; v--;
            int x = tree.lca(u, v);
            cout << t[x] + 1 << '\n';
        }
    }

    
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14