제출 #886888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
886888		vjudge1	Pictionary (COCI18_pictionary)	C++17	140 / 140	1258 ms	5712 KiB

pictionary

#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 / 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