oj.uz

Submission #94697

# Submission time Handle Problem Language Result Execution time Memory
94697 2019-01-22T20:37:08 Z johnjq Pictionary (COCI18_pictionary) C++17
140 / 140
 490 ms 53432 KB 
#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.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2552 KB Output is correct
2 Correct 36 ms 2424 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2936 KB Output is correct
2 Correct 49 ms 2808 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 11856 KB Output is correct
2 Correct 109 ms 11616 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 16320 KB Output is correct
2 Correct 139 ms 14932 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 23896 KB Output is correct
2 Correct 221 ms 25080 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 18296 KB Output is correct
2 Correct 360 ms 36404 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 41160 KB Output is correct
2 Correct 412 ms 45732 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 53432 KB Output is correct
2 Correct 490 ms 52124 KB Output is correct