oj.uz

Submission #44388

# Submission time Handle Problem Language Result Execution time Memory
44388 2018-04-01T11:50:55 Z chonka Pictionary (COCI18_pictionary) C++
140 / 140
 687 ms 27644 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3192 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4256 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 8188 KB Output is correct
2 Correct 63 ms 8188 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 11592 KB Output is correct
2 Correct 78 ms 11592 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 11592 KB Output is correct
2 Correct 124 ms 11592 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 12992 KB Output is correct
2 Correct 182 ms 12992 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 16504 KB Output is correct
2 Correct 236 ms 16504 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 16504 KB Output is correct
2 Correct 405 ms 20420 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 23252 KB Output is correct
2 Correct 504 ms 23368 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 27644 KB Output is correct
2 Correct 610 ms 27644 KB Output is correct