Submission #44388

#	Time	Username	Problem	Language	Result	Execution time	Memory
44388		chonka	Pictionary (COCI18_pictionary)	C++98	140 / 140	687 ms	27644 KiB

pictionary

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std ;

#define MAXN 100007

int n , m , q ;

struct tuhla {
    int x , y ;
    int l , r ;
};

tuhla a[ MAXN ] ;

int prv[ MAXN ] ;
int ans[ MAXN ] ;

vector < int > v[ MAXN ] ;

int find ( int x ) {
    if ( prv[ x ] == -1 ) { return x ; }
    int y = find ( prv[ x ] ) ;
    prv[ x ] = y ;
    return y ;
}

void UNITE ( int x , int y ) {
    int k1 = find ( x ) ;
    int k2 = find ( y ) ;
    if ( k1 != k2 ) {
        prv[ k1 ] = k2 ;
    }
}

void input ( ) {
    scanf ( "%d%d%d" , &n , &m , &q ) ;
    int i ;
    for ( i = 1 ; i <= q ; i ++ ) {
        scanf ( "%d%d" , &a[ i ].x , &a[ i ].y ) ;
        a[ i ].l = 1 ;
        a[ i ].r = m ;
    }
}

void solve ( ) {
    int i , j , t ;
    for ( t = 1 ; t <= 20 ; t ++ ) {
        for ( i = 1 ; i <= n ; i ++ ) { prv[ i ] = -1 ; }
        for ( i = 1 ; i <= m ; i ++ ) { v[ i ].clear ( ) ; }
        for ( i = 1 ; i <= q ; i ++ ) {
            int mid = ( a[ i ].l + a[ i ].r ) / 2 ;
            v[ mid ].push_back ( i ) ;
        }
        for ( i = 1 ; i <= m ; i ++ ) {
            int step = ( m - i + 1 ) ;
            for ( j = 2 * step ; j <= n ; j += step ) {
                UNITE ( j - step , j ) ;
            }
            int sz = v[ i ].size ( ) ;
            for ( j = 0 ; j < sz ; j ++ ) {
                int id = v[ i ][ j ] ;
                int k1 = find ( a[ id ].x ) ;
                int k2 = find ( a[ id ].y ) ;
                if ( k1 == k2 ) {
                    ans[ id ] = i ;
                    a[ id ].r = i - 1 ;
                }
                else {
                    a[ id ].l = i + 1 ;
                }
            }
        }
    }
    for ( i = 1 ; i <= q ; i ++ ) {
        printf ( "%d\n" , ans[ i ] ) ;
    }
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message (stderr)

pictionary.cpp: In function 'void input()':
pictionary.cpp:38:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d%d" , &n , &m , &q ) ;
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
pictionary.cpp:41:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d%d" , &a[ i ].x , &a[ i ].y ) ;
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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