Submission #1166436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166436		pg_mazen	Pictionary (COCI18_pictionary)	C++20	140 / 140	120 ms	7064 KiB

pictionary

#include <bits/stdc++.h>

using namespace std;

#define el '\n'
#define sp ' '
#define all(v) v.begin(), v.end()
#define rall(v) (v).rbegin(), (v).rend()
#define YES cout << "YES\n"
#define Yes cout << "Yes\n"
#define yes cout << "yes\n"
#define NO cout << "NO\n"
#define No cout << "No\n"
#define no cout << "no\n"
//#define int long long
#define double long double
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll,ll>
#define loop int t; cin >> t; for(int i=1;i<=t;++i)
#define mms(arr, val) memset(arr, val, sizeof arr)

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

const double EPS = 1e-7, PI = acos(-1);
const int N = 1e5 + 5, MOD = 1e9 + 7, oo = 0x3f3f3f3f;
const int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
const int knightX[] = {-2, -2, 2, 2, 1, 1, -1, -1};
const int knightY[] = {-1, 1, -1, 1, -2, 2, -2, 2};
const ll ooo = 0x3f3f3f3f3f3f3f3f;

struct DSU {
    vector<int> par, sz;

    DSU(int n) {
        par = sz = vector<int>(n + 1);
        for (int i = 0; i <= n; ++i) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int getParent(int x) {
        if (par[x] == x)
            return x;
        return par[x] = getParent(par[x]);
    }

    bool connect(int u, int v) {
        u = getParent(u);
        v = getParent(v);
        if (u == v)
            return false;
        if (sz[u] < sz[v])
            par[u] = v, sz[v] += sz[u];
        else
            par[v] = u, sz[u] += sz[v];
        return true;
    }

    bool isConnected(int u, int v) {
        return getParent(u) == getParent(v);
    }
};

int ql[N], qr[N], ans[N];

void testCase() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> que(q);
    for (int i = 0; i < q; ++i) {
        cin >> que[i].first >> que[i].second;
        ql[i] = 1;
        qr[i] = m;
    }
    bool all_answered = false;
    while (!all_answered) {
        all_answered = true;
        vector<vector<int>> mids(m + 1);
        for (int i = 0; i < q; ++i) {
            if (ql[i] <= qr[i]) {
                mids[(ql[i] + qr[i]) / 2].push_back(i);
                all_answered = false;
            }
        }
        DSU dsu(n + 1);
        for (int mid = 1; mid <= m; ++mid) {
            int cur = m - mid + 1;
            for (int j = cur * 2; j <= n; j += cur)
                dsu.connect(cur, j);
            for (auto &i: mids[mid]) {
                int a = que[i].first, b = que[i].second;
                if (dsu.isConnected(a, b))
                    qr[i] = mid - 1, ans[i] = mid;
                else
                    ql[i] = mid + 1;
            }
        }
    }
    for (int i = 0; i < q; ++i)
        cout << ans[i] << el;
}

int32_t main() {
    PG_Mazen();
    //sieve();
    //sieveSPF();
    //precompute();
    testCase();
    //cerr << clock() / 1000.0 << " Secs";
}

• 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