Submission #1309286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309286		anarch_y	Pictionary (COCI18_pictionary)	C++20	140 / 140	142 ms	15336 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

struct DSU{
    vector<int> link, size;
 
    DSU(int n){
        link.resize(n+1, 0);
        size.resize(n+1, 1);
        for(int i=1; i<=n; i++) link[i] = i;
    }
 
    int find(int x){
        if(x != link[x]) link[x] = find(link[x]);
        return link[x];
    }
 
    bool same(int a, int b){
        return find(a) == find(b);
    }
    
    void merge(int a, int b){
        if(same(a, b)) return;
        a = find(a); b = find(b);
        if(size[a] > size[b]) swap(a, b);
        link[a] = b;
        size[b] += size[a];
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, q; cin >> n >> m >> q;
    vector<int> a(q+1), b(q+1);
    for(int i=1; i<=q; i++){
        cin >> a[i] >> b[i];
    }
    vector<int> L(q+1), R(q+1), ans(q+1);
    vector<int> chk[m+1];
    for(int i=1; i<=q; i++){
        L[i] = 1, R[i] = m;
    }
    bool ch = true;
    while(ch){
        ch = false;
        DSU D(n);
        for(int i=1; i<=q; i++){
            if(L[i] <= R[i]){
                int mid = (L[i]+R[i])/2;
                chk[mid].pb(i);
            }
        }
        for(int i=1; i<=m; i++){
            int g = m-i+1;
            for(int j=2*g; j<=n; j+=g){
                D.merge(g, j);
            }
            while(!chk[i].empty()){
                ch = true;
                int k = chk[i].back();
                chk[i].pop_back();
                if(D.same(a[k], b[k])){
                    ans[k] = i;
                    R[k] = i-1;
                }
                else L[k] = i+1;
            }
        }
    }
    for(int i=1; i<=q; i++) cout << ans[i] << "\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