Submission #224275

#	Time	Username	Problem	Language	Result	Execution time	Memory
224275		infinite_iq	Pictionary (COCI18_pictionary)	C++14	140 / 140	440 ms	24916 KiB

pictionary

#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 500
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll inf=1e18;
const ll mod=1e9+7;
const ld pai=acos(-1);
int n , m , q ;
// 
vpi v[100009] ;
int dp[100009][20] , w[100009] , Mx[100009][20] ;
void dfs ( int node , int p ) {
        dp [node][0] = p ;
        w [node] = w[p] + 1 ;
        for ( auto U : v[node] ) {
                int u = U.fi ;
                int x = U.se ;
                if ( u == p ) C ;
                Mx [u][0] = x ;
                dfs ( u , node ) ;
        }
}
void build () {
        dfs( 0 , 0 ) ;
        for ( int j = 1 ; j < 20 ; j ++ ) {
                for ( int i = 0 ; i < n ; i ++ ) {
                        dp [i][j] = dp [ dp[i][j-1] ][ j-1 ] ;
                        Mx [i][j] = max ( Mx [ i ][ j-1 ] , Mx  [ dp[i][j-1] ][ j-1 ] ) ;
                }
        }
}
int query ( int a , int b ) {
        int ans = 0 ;
        if ( w[a] < w[b] ) swap ( a , b ) ;
        int l = w[a] - w[b] ;
        for ( int i = 0 ; i < 20 ; i ++ ) {
                if ( ( l & ( 1<<i ) ) ) {
                        ans = max ( ans , Mx[a][i] ) ;
                        a = dp [a][i] ;
                }
        }
        if ( a == b ) return ans ;
        for ( int i = 19 ; i >= 0 ; i -- ) {
                if ( dp [a][i] != dp [b][i] ) {
                        ans = max ( ans , Mx[a][i] ) ;
                        ans = max ( ans , Mx[b][i] );
                        a = dp [a][i] ;
                        b = dp [b][i] ;
                }
        }
        ans = max ( ans , Mx [a][0] ) ;
        ans = max ( ans , Mx [b][0] ) ;
        return ans ;
}

//
int p[100009] ;
int get ( int node ) {
        if ( node == p[node] ) return node ;
        return p[node] = get ( p [node] ) ;
}
void merge ( int a , int b , int len ) {
        int A = get ( a ) ;
        int B = get ( b ) ;
        if ( A == B ) return ;
        v[a] .pb ( { b , len } ) ;
        v[b] .pb ( { a , len } ) ;
        p [B] = A ;
}
int main () {
        cin >> n >> m >> q ;
        for ( int i = 0 ; i < n ; i ++ ) {
                p[i] = i ;
        }
        for ( int i = m ; i >= 1 ; i -- ) {
                vi nodes ;
                for ( int j = i ; j <= n ; j += i ) {
                        nodes .pb ( j -1 ) ;
                }
                for ( int j = 1 ; j < nodes.size() ; j ++ ) {
                        merge ( nodes[0] , nodes[j] , m-i+1 ) ;
                }
        }
        build () ;
        while ( q -- ) {
                int a , b ;
                cin >> a >> b ;
                a -- , b -- ;
                cout << query ( a , b ) << endl ;
        }
}

Compilation message (stderr)

pictionary.cpp: In function 'int main()':
pictionary.cpp:101:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for ( int j = 1 ; j < nodes.size() ; j ++ ) {
                                   ~~^~~~~~~~~~~~~~

• 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