Submission #1267098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267098		rayan_bd	Pictionary (COCI18_pictionary)	C++20	126 / 140	460 ms	74840 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5 + 10;
set<int> v[mxN];
vector<int> point[mxN];
int sz[mxN], par[mxN], query[mxN][2], st[mxN], en[mxN], ans[mxN];
int find(int u){
    if(par[u] == u) return u;
    return par[u] = find(par[u]);
}
void unite(int u, int v){
    u = find(u), v = find(v);
    if(u ^ v){
        if(sz[u] > sz[v]) sz[u] += sz[v], par[v] = u;
        else sz[v] += sz[u], par[u] = v;
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    for(int  i = 1; i <= m; ++i){
        for(int j = i; j <= n; j += i){
           if(v[i + 1].find(j) == v[i + 1].end()){
            v[i].insert(j);
        }
        }
    }
    for(int i = 0; i < q; ++i){
        cin >> query[i][0] >> query[i][1];
        st[i] = 1, en[i] = m, ans[i] = 1e9;
        point[(en[i] + st[i]) / 2].push_back(i);
    }
    // 3 6
    // 2 4,6, 8
    for(int i = 0; i < 19; ++i){
        for(int j = 1; j <= n; ++j){
            par[j] = j, sz[j] = 1;
        }
        for(int j = m; j >= 1; --j){
            int fi = -1;
            for(auto k : v[j]){
                if(fi != -1) unite(fi, k);
                else fi = k;
            }
            for(auto it : point[j]){
                if(find(query[it][0]) == find(query[it][1])){
                    st[it] = j + 1;
                    ans[it] = min(ans[it], m - j + 1);
                }else{
                    en[it] = j - 1;
                }
            }
            point[j].clear();
        }
        for(int j = 0; j < q; ++j){
            if(st[j] <= en[j]){
                point[(en[j] + st[j]) / 2].push_back(j);
            }
        }
    }
    for(int i = 0; i < q; ++i) cout << ans[i] << "\n";
    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: 0 / 14