Submission #1032143

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1032143	2024-07-23T12:26:30 Z	borisAngelov	Pictionary (COCI18_pictionary)	C++17	126 / 140	116 ms	48392 KB

pictionary

#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;
vector<int> tree[4 * maxn];

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

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)
    {
        tree[1].push_back(i);
        answers[i] = m;
    }

    int prvLevel = -1;
    int ptrLevel = 0;
    int gcd, idx, node;
    queue<ParallelNode> q;
    q.push({1, 1, m, 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)
        {
            gcd = m - i + 1;

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

        ptrLevel = mid;

        node = curr.node;

        for (int i = 0; i < tree[node].size(); ++i)
        {
            idx = tree[node][i];

            //cout << mid << " :: " << queries[idx].first << " " << queries[idx].second << " :: " << dsu.areConnected(queries[idx].first, queries[idx].second) << endl;

            if (dsu.areConnected(queries[idx].first, queries[idx].second) == true)
            {
                answers[idx] = min(answers[idx], mid);
                tree[2 * node].push_back(idx);
            }
            else
            {
                tree[2 * node + 1].push_back(idx);
            }
        }

        if (curr.l == curr.r) continue;

        if (!tree[2 * node].empty())
        {
            q.push({2 * node, curr.l, mid, curr.level + 1});
        }

        if (!tree[2 * node + 1].empty())
        {
            q.push({2 * node + 1, mid + 1, curr.r, curr.level + 1});
        }
    }

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

    return 0;
}

Compilation message

pictionary.cpp: In function 'int main()':
pictionary.cpp:120:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for (int i = 0; i < tree[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~~~

Subtask #1

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	10184 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	11220 KB	Output is correct

Subtask #3

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	14732 KB	Output is correct
2	Correct	26 ms	14024 KB	Output is correct

Subtask #4

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	17016 KB	Output is correct
2	Correct	30 ms	15876 KB	Output is correct

Subtask #5

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	15448 KB	Output is correct
2	Correct	39 ms	15032 KB	Output is correct

Subtask #6

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	16464 KB	Output is correct
2	Correct	33 ms	14588 KB	Output is correct

Subtask #7

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	19160 KB	Output is correct
2	Correct	52 ms	16348 KB	Output is correct

Subtask #8

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	16608 KB	Output is correct
2	Correct	76 ms	20860 KB	Output is correct

Subtask #9

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	91 ms	23140 KB	Output is correct
2	Correct	113 ms	21268 KB	Output is correct

Subtask #10

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	116 ms	48392 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-