oj.uz

답안 #1032166

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1032166 2024-07-23T12:39:27 Z borisAngelov Pictionary (COCI18_pictionary) C++17
140 / 140
 77 ms 5712 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;

int n, m, k;
pair<int, int> queries[maxn];
int answers[maxn];

struct DSU
{
    int par[maxn];
    int dep[maxn];

    void init(int n)
    {
        for (int i = 1; i <= n; ++i)
        {
            dep[i] = 1;
            par[i] = i;
        }
    }

    int root(int node)
    {
        if (node == par[node]) return node;
        return par[node] = root(par[node]);
    }

    void connect(int x, int y)
    {
        x = root(x);
        y = root(y);

        if (x == y) return;

        if (dep[x] < dep[y]) swap(x, y);

        par[y] = x;

        if (dep[x] == dep[y]) ++dep[x];
    }

    bool areConnected(int x, int y)
    {
        return root(x) == root(y);
    }
};

DSU dsu;

struct ParallelNode
{
    int node;
    int l;
    int r;
    int ql;
    int qr;
    int level;
};

int currentQueryOrder[maxn];
int nextQueryOrder[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m >> k;

    for (int i = 1; i <= k; ++i)
    {
        cin >> queries[i].first >> queries[i].second;
    }

    for (int i = 1; i <= k; ++i)
    {
        currentQueryOrder[i] = i;
        answers[i] = m;
    }

    int prvLevel = -1;
    int ptrLevel = 0;
    queue<ParallelNode> q;
    q.push({1, 1, m, 1, k, 1});

    while (!q.empty())
    {
        ParallelNode curr = q.front();
        q.pop();

        if (prvLevel != curr.level)
        {
            prvLevel = curr.level;
            dsu.init(n);
            ptrLevel = 0;
        }

        int mid = (curr.l + curr.r) / 2;

        for (int i = ptrLevel + 1; i <= mid; ++i)
        {
            int gcd = m - i + 1;

            for (int nodeNum = gcd; nodeNum + gcd <= n; nodeNum += gcd)
            {
                dsu.connect(nodeNum, nodeNum + gcd);
            }
        }

        ptrLevel = mid;

        int node = curr.node;
        int ql = curr.ql;
        int qr = curr.qr;
        int qlPtr = ql;
        int qrPtr = qr;

        if (curr.l == curr.r)
        {
            for (int i = ql; i <= qr; ++i)
            {
                int idx = currentQueryOrder[i];

                if (dsu.areConnected(queries[idx].first, queries[idx].second) == true)
                {
                    answers[idx] = min(answers[idx], mid);
                }
            }

            continue;
        }

        for (int i = ql; i <= qr; ++i)
        {
            int idx = currentQueryOrder[i];

            if (dsu.areConnected(queries[idx].first, queries[idx].second) == true)
            {
                answers[idx] = min(answers[idx], mid);
                nextQueryOrder[qlPtr++] = idx;
            }
            else
            {
                nextQueryOrder[qrPtr--] = idx;
            }
        }

        for (int i = ql; i <= qr; ++i)
        {
            currentQueryOrder[i] = nextQueryOrder[i];
        }

        if (ql <= qlPtr - 1)
        {
            q.push({2 * node, curr.l, mid, ql, qlPtr - 1, curr.level + 1});
        }

        if (qr >= qrPtr + 1)
        {
            q.push({2 * node, mid + 1, curr.r, qrPtr + 1, qr, curr.level + 1});
        }
    }

    for (int i = 1; i <= k; ++i)
    {
        cout << answers[i] << "\n";
    }

    return 0;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 604 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 860 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 2396 KB Output is correct
2 Correct 17 ms 2476 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 3452 KB Output is correct
2 Correct 20 ms 3164 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 2388 KB Output is correct
2 Correct 21 ms 2348 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 2648 KB Output is correct
2 Correct 21 ms 2348 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 3568 KB Output is correct
2 Correct 32 ms 2908 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 3928 KB Output is correct
2 Correct 60 ms 4756 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 5060 KB Output is correct
2 Correct 63 ms 4688 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 5712 KB Output is correct
2 Correct 77 ms 5680 KB Output is correct