Submission #1166590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166590		black_third	Pictionary (COCI18_pictionary)	C++20	140 / 140	141 ms	15244 KiB

pictionary

#include <iostream>
#include <sstream>
#include <set>
#include <fstream>
#include <algorithm>
#include <cctype>
#include <iomanip>
#include <vector>
#include <map>
#include <queue>
#include <numeric>
#include <string>
#include <cmath>
#include <climits>
#include <stack>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <bitset>
#include <cassert>
#include <tuple>

using namespace std;
typedef long long ll;
typedef long double ld;
//const int mod = 998244353;
const int mod = 1e9+7;
const int N=5e5+5;

struct DSU {
    vector<int> par, sz;

    DSU(int n) : par(n), sz(n, 1) { iota(par.begin(), par.end(), 0); }

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

    bool same(int x, int y) { return find(x) == find(y); }

    bool join(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y])
            swap(x, y);
        sz[x] += sz[y];
        par[y] = x;
        return true;
    }

    int size(int x) { return sz[find(x)]; }
};

void solve() {

    int n,m,q;
    cin>>n>>m>>q;
    vector <vector<int>> div(m+1);
    for (int i=1;i<=m;i++) {
        for (int j=2*i;j<=n;j+=i) div[i].push_back(j);
    }
    vector <pair<int,int>> quer;
    quer.push_back({0,0});
    for (int i=1;i<=q;i++) {
        int a,b;
        cin>>a>>b;
        quer.push_back({a,b});
    }
    vector <int> qe(q+1,m),qs(q+1,1);
    bool lessa=true;
    while (lessa) {
        lessa=false;
        vector <vector<int>> mids(m+1);
        DSU dsu(n+1);
        for (int i=1;i<=q;i++) {
            if (qe[i]>=qs[i]) {
                mids[(qe[i]+qs[i])>>1].push_back(i);
                lessa=true;
            }
        }
        for (int mid=1;mid<=m;mid++) {
            for (auto i : div[m-mid+1]) {
                dsu.join(m-mid+1,i);
            }
            for (auto j : mids[mid]) {
                if (dsu.same(quer[j].first,quer[j].second)) {
                    qe[j]=mid-1;
                } else {
                    qs[j]=mid+1;
                }
            }
        }
    }
    for (int i=1;i<=q;i++) {
        if (qe[i]==m) cout<<"-1\n";
        else cout<<qe[i]+1<<'\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;
    while (t--) {
        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