oj.uz

Submission #224275

# Submission time Handle Problem Language Result Execution time Memory
224275 2020-04-17T16:03:52 Z infinite_iq Pictionary (COCI18_pictionary) C++14
140 / 140
 440 ms 24916 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2816 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 3064 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 3704 KB Output is correct
2 Correct 223 ms 3684 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 4216 KB Output is correct
2 Correct 308 ms 4088 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 8084 KB Output is correct
2 Correct 171 ms 8084 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 10004 KB Output is correct
2 Correct 194 ms 10920 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 13124 KB Output is correct
2 Correct 213 ms 13400 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 16764 KB Output is correct
2 Correct 354 ms 18192 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 20068 KB Output is correct
2 Correct 423 ms 22380 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 24576 KB Output is correct
2 Correct 440 ms 24916 KB Output is correct