Submission #1183036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183036		AMnu	Pictionary (COCI18_pictionary)	C++20	140 / 140	84 ms	23812 KiB

pictionary

#include <bits/stdc++.h>
#define fi first
#define se second
#define bupo __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MAXN = 2e5+5;

int N, M, Q, A[MAXN], B[MAXN];
int P, L[MAXN], R[MAXN], ans[MAXN], par[MAXN];
vector <int> mid[MAXN];
vector <pii> edge[MAXN];

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

void join(int x,int y) {
    x = find(x);
    y = find(y);
    par[x] = y;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M >> Q;
    for (int i=1;i<=N;i++) {
        par[i] = i;
    }
    for (int i=M;i>1;i--) {
        for (int j=2*i;j<=N;j+=i) {
            if (find(i) != find(j)) {
                join(i,j);
                edge[M+1-i].push_back({i,j});
            }
        }
    }
    for (int i=1;i<=Q;i++) {
        cin >> A[i] >> B[i];
        L[i] = 1;
        R[i] = M-1;
        ans[i] = M;
        if (L[i] <= R[i]) {
            mid[(L[i]+R[i])/2].push_back(i);
        }
        else {
            P++;
        }
    }
    while (P < Q) {
        for (int i=1;i<=N;i++) {
            par[i] = i;
        }
        for (int i=1;i<M;i++) {
            for (pii x : edge[i]) {
                join(x.fi,x.se);
            }
            for (int j : mid[i]) {
                if (find(A[j]) == find(B[j])) {
                    ans[j] = i;
                    R[j] = i - 1;
                }
                else {
                    L[j] = i + 1;
                }
                if (L[j] <= R[j]) {
                    mid[(L[j]+R[j])/2].push_back(j);
                }
                else {
                    P++;
                }
            }
            mid[i].clear();
        }
    }
    for (int i=1;i<=Q;i++) {
        cout << ans[i] << "\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