oj.uz

Submission #886888

# Submission time Handle Problem Language Result Execution time Memory
886888 2023-12-13T06:33:40 Z vjudge1 Pictionary (COCI18_pictionary) C++17
140 / 140
 1258 ms 5712 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=2e5+100;
#else
    const int lim=1e4+100;
#endif

#include "bits/stdc++.h"
using namespace std;

#define int int64_t
#define pb push_back

const int mod=1e9+7;
using pii=pair<int,int>;

int parent[lim],sz[lim],t[lim];
int find(int i){
    if(parent[i]==i)return i;
    return find(parent[i]);
}
void unite(int i,int j,int tm){
    int x=find(i),y=find(j);
    if(x==y)return;
    if(sz[x]<sz[y])swap(x,y);
    t[y]=tm;
    parent[y]=x;
    sz[x]+=sz[y];
}
int find(int i,int tm){
    if(parent[i]==i||tm<t[i])return i;
    return find(parent[i],tm);
}

inline void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        parent[i]=i;
    }
    for(int i=1;i<=m;i++){
        int inc=m-i+1;
        for(int j=inc;j<=n;j+=inc){
            unite(inc,j,i);
        }
    }
    while(q--){
        int a,b;
        cin>>a>>b;
        int l=1,r=m-1,ans=m;
        while(l<=r){
            int mid=(l+r)>>1;
            int x=find(a,mid),y=find(b,mid);
            if(x==y){
                ans=mid;
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        cout<<ans<<"\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    //freopen("boards.in","r",stdin);
    //freopen("boards.out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2652 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3196 KB Output is correct
2 Correct 31 ms 3164 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 3580 KB Output is correct
2 Correct 48 ms 3408 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 3544 KB Output is correct
2 Correct 143 ms 3412 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 3668 KB Output is correct
2 Correct 224 ms 3568 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 4084 KB Output is correct
2 Correct 363 ms 3728 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 4280 KB Output is correct
2 Correct 724 ms 4696 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 867 ms 4992 KB Output is correct
2 Correct 1022 ms 5056 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1258 ms 5712 KB Output is correct
2 Correct 1246 ms 5308 KB Output is correct