Submission #207691

#	Time	Username	Problem	Language	Result	Execution time	Memory
207691		bibabas	Pictionary (COCI18_pictionary)	C++17	140 / 140	344 ms	9960 KiB

pictionary

#include <bits/stdc++.h>
 
#define ll long long
#define ull unsigned ll
#define vi vector<ll>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ld long double
#define pii pair<ll, ll>
#define mt make_tuple
#define mn(a, b) a = min(a, b)
#define mx(a, b) a = max(a, b)
 
using namespace std;
 
const ll INF = (ll)2e9;
const ll inf = (ll)2e18;
const ld eps = (ld)1e-10;
const ll mod = (ll)1e9 + 7;
const ll MAXN = (ll)1e5 + 1;
const ll MAXC = (ll)2001;
const ll MAXE = (ll)1000;
const ll MAXLOG = 21;
const ll maxlen = (ll)1e5;
const ll asci = (ll)256;
const ll block = 50000;
const ld PI = acos(-1);
//
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<
ll,
null_type,
less<ll>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;*/
 
template <class T>
istream& operator >>(istream &in, vector<T> &arr){
     for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};

struct dsu{
    int p[MAXN], sz[MAXN];

    void clear(int n) {
        for (int i = 0; i <= n; ++i) {
            p[i] = i; sz[i] = 1;
        }
    }

    int par(int v) {
        if (p[v] == v) return v;
        return p[v] = par(p[v]);
    }

    void unite(int v, int u) {
        v = par(v), u = par(u);
        if (v == u) return;
        if (sz[v] < sz[u]) swap(v, u);
        sz[v] += sz[u];
        p[u] = v;
    }

    bool in(int v, int u) {
        v = par(v), u = par(u);
        if (v == u) return true;
        return false;
    }
};

dsu snm;

void solve() {
    int n, m, q; cin >> n >> m >> q;
    vi L(q, -1), R(q, m - 1), ok(q);
    vector<pii> mid(q), check(q);
    for (int i = 0; i < q; ++i) {
        int v, u; cin >> v >> u;
        check[i] = mp(v, u);
    }
    for (int i = 0; i < q; ++i) {
        if (L[i] + 1 == R[i]) mid[i] = mp(-1, -1);
        mid[i] = mp((L[i] + R[i]) / 2, i);
    }
    while (mid != vector<pii>(q, mp(-1, -1))) {
        sort(all(mid)); snm.clear(n);
        ok.assign(q, -1);
        int it = 0;
        for (int i = m; i >= 1; --i) {
            for (int j = i; j + i <= n; j += i) {
                snm.unite(j, j + i);
            }
            while (it < q && m - i >= mid[it].first) {
                if (mid[it].first != -1) ok[mid[it].second] = snm.in(check[mid[it].second].first, check[mid[it].second].second);
                it++;
            }
        }
        for (int i = 0; i < q; ++i) {
            if (ok[i] == -1) continue;
            if (ok[i]) R[i] = (L[i] + R[i]) / 2;
            else L[i] = (L[i] + R[i]) / 2;
        }
        for (int i = 0; i < q; ++i) {
            if (L[i] + 1 == R[i]) mid[i] = mp(-1, -1);
            else mid[i] = mp((L[i] + R[i]) / 2, i);
        }
    }
    for (int i = 0; i < q; ++i) {
        cout << R[i] + 1 << "\n";
    }
}
 
int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#endif
    cout.precision(30);
    solve();
 
    return 0;
}

• 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