oj.uz

Submission #466744

# Submission time Handle Problem Language Result Execution time Memory
466744 2021-08-20T15:34:50 Z Lam_lai_cuoc_doi Pictionary (COCI18_pictionary) C++17
140 / 140
 265 ms 19392 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = __int128_t;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 1e5 + 5;

struct dsu
{
    int par[N];
    dsu()
    {
        memset(par, -1, sizeof par);
    }
    int findpar(int v)
    {
        return par[v] < 0 ? v : par[v] = findpar(par[v]);
    }
    void Merge(int u, int v)
    {
        u = findpar(u);
        v = findpar(v);
        if (u == v)
            return;

        if (par[u] < par[v])
            swap(u, v);

        par[v] += par[u];
        par[u] = v;
    }
    bool Check(int u, int v)
    {
        return findpar(u) == findpar(v);
    }
};

int n, m, q, a[N], b[N], l[N], h[N], mid[N];
vector<pair<int, int>> adj[N];

void Read()
{
    cin >> n >> m >> q;

    for (int i = m; i; --i)
        for (int j = i * 2; j <= n; j += i)
            adj[i].emplace_back(i, j);

    for (int i = 1; i <= q; ++i)
    {
        cin >> a[i] >> b[i];
        l[i] = 1;
        h[i] = m;
        mid[i] = (l[i] + h[i]) / 2;
    }
}

void Solve()
{
    vector<int> x[2];
    for (int i = 1; i <= q; ++i)
        x[0].emplace_back(i);

    while (!x[0].empty())
    {
        sort(x[0].begin(), x[0].end(), [&](const int &x, const int &y)
             { return mid[x] > mid[y]; });

        dsu f;

        for (int i = 0, j = m; i < (int)x[0].size(); ++i)
        {
            while (j >= mid[x[0][i]])
            {
                for (auto t : adj[j])
                    f.Merge(t.first, t.second);
                --j;
            }

            if (f.Check(a[x[0][i]], b[x[0][i]]))
                l[x[0][i]] = mid[x[0][i]] + 1;
            else
                h[x[0][i]] = mid[x[0][i]] - 1;

            if (l[x[0][i]] <= h[x[0][i]])
            {
                mid[x[0][i]] = (l[x[0][i]] + h[x[0][i]]) / 2;
                x[1].emplace_back(x[0][i]);
            }
        }

        swap(x[0], x[1]);
        x[1].clear();
    }

    for (int i = 1; i <= q; ++i)
        cout << m - h[i] + 1 << "\n";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        //cout << "Case #" << _ << "\n";
        Read();
        Solve();
    }
    //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message

pictionary.cpp: In function 'void read(T&)':
pictionary.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3276 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3916 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6004 KB Output is correct
2 Correct 43 ms 6180 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 7220 KB Output is correct
2 Correct 64 ms 6752 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 7484 KB Output is correct
2 Correct 65 ms 7388 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 8636 KB Output is correct
2 Correct 67 ms 8092 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 11424 KB Output is correct
2 Correct 103 ms 10364 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 9940 KB Output is correct
2 Correct 161 ms 14648 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 16108 KB Output is correct
2 Correct 186 ms 16820 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 19392 KB Output is correct
2 Correct 226 ms 18752 KB Output is correct