제출 #1309411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309411		Jean7	Pictionary (COCI18_pictionary)	C++20	112 / 140	140 ms	91276 KiB

pictionary

#include <bits/stdc++.h>
#define int long long

using namespace std ;

const int N = 2e5+5 ;
const int L = 23 ;

int n , m , q ;

struct Reachability_Tree {
    vector <int> g[N] ;
    int par[N] , w[N] , rt ;
    void init () {
        rt = n ;
        for ( int i = 1 ; i < 2*n ; i++ ) {
            par[i] = i ;
        }
    }
    int fin ( int x ) {
        if ( x == par[x] ) {
            return x ;
        }
        return par[x] = fin ( par[x] ) ;
    }
    bool uni ( int x , int y , int we ) {
        if ( ( x = fin(x) ) == ( y = fin(y) ) ) {
            return 0 ;
        }
        rt++ ;
        par[x] = rt ;
        par[y] = rt ;
        g[rt].push_back(x) ;
        g[rt].push_back(y) ;
        w[rt] = we ;
        return 1 ;
    }
} krt ;

struct LCA_Sparse_Table {
    int in[N] , eu[N<<1] , logs[N<<1] , st[N<<1][L] , t = 0 ;
    void tour ( int i ) {
        t++ ;
        eu[t] = i ;
        in[i] = t ;
        for ( auto it : krt.g[i] ) {
            tour ( it ) ;
            t++ ;
            eu[t] = i ;
        }
    }
    void build () {
        logs[1] = 0 ;
        for ( int i = 2 ; i <= t ; i++ ) {
            logs[i] = logs[i>>1] + 1 ;
        }
        for ( int i = 1 ; i <= t ; i++ ) {
            st[i][0] = eu[i] ;
        }
        for ( int j = 1 ; j <= logs[t] ; j++ ) {
            for ( int i = 1 ; i + ( 1 << j ) - 1 <= t ; i++ ) {
                int x = st[i][j-1] , y = st[i+(1<<(j-1))][j-1] ;
                st[i][j] = ( in[x] < in[y] ? x : y ) ;
            }
        }
    }
    int query ( int x , int y ) {
        x = in[x] ;
        y = in[y] ;
        if ( x > y ) {
            swap ( x , y ) ;
        }
        int j = logs[y-x+1] ;
        x = st[x][j] ;
        y = st[y-(1<<j)+1][j] ;
        return ( in[x] < in[y] ? x : y ) ;
    }
} lca ;

inline void solve () {
    cin >> n >> m >> q ;
    krt.init () ;
    for ( int i = 1 ; i <= m ; i++ ) {
        int g = m-i+1 ;
        for ( int j = 2*g ; j <= n ; j += g ) {
            krt.uni ( g , j , i ) ;
        }
    }
    lca.tour ( krt.rt ) ;
    lca.build () ;
    while ( q-- ) {
        int x , y ;
        cin >> x >> y ;
        cout << krt.w[lca.query(x,y)] << "\n" ;
    }
}

signed main () {
    //freopen ( ".in" , "r" , stdin ) ;
    //freopen ( ".out" , "w" , stdout ) ;
    ios_base::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;
    int tc = 1 ;
    //cin >> tc ;
    while ( tc-- ) {
        solve() ;
    }
    return 0 ;
}

///  JJJJJJJ EEEEEEE  AAAAA  NN   NN 7777777
///     JJ   EE      AA   AA NNN  NN     77
///     JJ   EEEEEE  AAAAAAA NN N NN    77
///  JJ JJ   EE      AA   AA NN  NNN   77
///  JJJJJ   EEEEEEE AA   AA NN   NN  77

• 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: 0 / 14
• Subtask 10: 0 / 14