Submission #94697

#	Time	Username	Problem	Language	Result	Execution time	Memory
94697		johnjq	Pictionary (COCI18_pictionary)	C++17	140 / 140	490 ms	53432 KiB

pictionary

#include <bits/stdc++.h>
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> ii;
using std::swap;

const int MAX_N = 100000;
#if 0
#include "../codes/uf-partial-1.cpp"
#include "../codes/uf-partial-2.cpp"
#else
int tempo;
int pai[MAX_N+1];
int tam[MAX_N+1];
int his[MAX_N+1];
void init() {
    tempo = 0;
    for (int i = 1; i <= MAX_N; ++i) {
        pai[i] = i;
        tam[i] = 1;
        his[i] = 0;
    }
}
int find(int x, int t) {
    if (pai[x] == x) return x;
    if (his[x] > t)  return x;
    return find(pai[x], t);
}
void merge(int u, int v) {
    tempo += 1;
    int a = find(u, tempo);
    int b = find(v, tempo);
    if (tam[a] > tam[b]) swap(a, b);
    pai[a] = b;
    his[a] = tempo;
    tam[b] += tam[a];
}
#endif

bool same(int u, int v, int t) {
    return find(u, t) == find(v, t);
}

inline int find_time(int a, int b) {
    int ans = -1;
    int l = 0, r = tempo;
    while (l <= r) {
        const int m = (l+r)/2;
        if (same(a, b, m)) {
            ans = m;
            r = m-1;
        } else {
            l = m+1;
        }
    }
    return ans;
}

int32_t main() {
    using namespace std;
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();

    int n, m, q;
    cin>>n>>m>>q;
    map<int, int> ans;
    ans[tempo] = 0;
    for (int day = m; day >= 1; --day) {
        for (int i = 2; i*day <= n; ++i) {
            if (!same(day, i*day, tempo))
                merge(day, i*day);
            else
                tempo += 1;
            ans[tempo] = m-day+1;
        }
    }
    while (q--) {
        int a, b;
        cin>>a>>b;
        int time = find_time(a, b);
        cout<<ans[time]<<'\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