Submission #1161035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161035		trufanov.p	Pictionary (COCI18_pictionary)	C++20	140 / 140	83 ms	28996 KiB

pictionary

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>
#include <numeric>

using namespace std;

struct DSU {
    vector<int> p, d;
    DSU(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        d.resize(n);
    }
    int get_par(int v) {
        if (v == p[v]) {
            return v;
        }
        return p[v] = get_par(p[v]);
    }
    void unite(int u, int v) {
        u = get_par(u);
        v = get_par(v);
        if (u != v) {
            if (d[u] > d[v]) {
                swap(u, v);
            }
            p[u] = v;
            if (d[u] == d[v]) {
                d[v]++;
            }
        }
    }
};

const int LOG = 18;

void dfs(int v, const vector<vector<pair<int, int>>>& gr,
    vector<vector<int>>& up, vector<vector<int>>& maxup,
    vector<int>& tin, vector<int>& tout, int& timer,
    int p, int pedge) {

    tin[v] = timer++;
    up[v][0] = p;
    maxup[v][0] = pedge;
    for (int i = 1; i < LOG; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
        maxup[v][i] = max(maxup[v][i - 1], maxup[up[v][i - 1]][i - 1]);
    }
    for (const auto& [u, w] : gr[v]) {
        if (u != p) {
            dfs(u, gr, up, maxup, tin, tout, timer, v, w);
        }
    }
    tout[v] = timer++;
}

inline bool ispar(int u, int v, const vector<int>& tin, const vector<int>& tout) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int maxonpath(int u, int v,
    const vector<vector<int>>& up, const vector<vector<int>>& maxup,
    const vector<int>& tin, const vector<int>& tout) {
    int ans = 0;
    if (!ispar(u, v, tin, tout)) {
        int u1 = u;
        for (int i = LOG - 1; i > -1; --i) {
            if (!ispar(up[u1][i], v, tin, tout)) {
                ans = max(ans, maxup[u1][i]);
                u1 = up[u1][i];
            }
        }
        ans = max(ans, maxup[u1][0]);
    }
    if (!ispar(v, u, tin, tout)) {
        int v1 = v;
        for (int i = LOG - 1; i > -1; --i) {
            if (!ispar(up[v1][i], u, tin, tout)) {
                ans = max(ans, maxup[v1][i]);
                v1 = up[v1][i];
            }
        }
        ans = max(ans, maxup[v1][0]);
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<pair<int, int>>> gr(n + 1);
    DSU d(n + 1);
    for (int i = m; i >= 1; --i) {
        for (int j = 2 * i; j <= n; j += i) {
            if (d.get_par(i) != d.get_par(j)) {
                d.unite(i, j);
                gr[i].push_back({ j, m - i + 1 });
                gr[j].push_back({ i, m - i + 1 });
            }
        }
    }
    vector<vector<int>> up(n + 1, vector<int>(LOG));
    vector<vector<int>> maxup(n + 1, vector<int>(LOG));
    vector<int> tin(n + 1), tout(n + 1);
    int timer = 0;
    dfs(1, gr, up, maxup, tin, tout, timer, 1, 0);
    for (int i = 0; i < q; ++i) {
        int u, v;
        cin >> u >> v;
        cout << maxonpath(u, v, up, maxup, tin, tout) << '\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: 14 / 14
• Subtask 10: 14 / 14