Submission #224331

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
224331	2020-04-17T17:12:07 Z	infinite_iq	Pictionary (COCI18_pictionary)	C++14	140 / 140	347 ms	43148 KB

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 ;
int p [100009] , ans [100009] ;
set < int >who [100009];
map < int , vi > que [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 ) {
        a = get ( a ) ;
        b = get ( b ) ;
        if ( a == b ) return ;
        if ( que [a] .size() <= who [b] .size() ) {
                vi ret ;
                for ( auto u : que [a] ) {
                        if ( who [b] . count ( u.fi ) ) {
                                ret .pb ( u.fi ) ;
                                for ( auto id : u.se ) {
                                        ans [id] = len ;
                                }
                        }
                }
                for ( auto u : ret ) que[a] .era ( u ) ;
        }
        else {
                vi ret ;
                for ( auto u : who [b] ) {
                        if ( que [a].count ( u ) ) {
                                ret .pb ( u ) ;
                                for ( auto id : que[a][u] ) {
                                        ans [id] = len  ;
                                }
                        }
                }
                for ( auto u : ret ) que[a] .era ( u ) ;
        }
        if ( que [b] .size() <= who [a] .size() ) {
                vi ret ;
                for ( auto u : que[b] ) {
                        if ( who [a] .count ( u.fi ) ) {
                                ret .pb ( u.fi ) ;
                                for ( auto id : u.se ) {
                                        ans [id] = len ;
                                }
                        }
                }
                for ( auto u : ret ) que [b] .era ( u ) ;
        }
        else {
                vi ret ;
                for ( auto u : who [a] ) {
                        if ( que[b] .count ( u ) ) {
                                ret .pb ( u ) ;
                                for ( auto id : que[b][u] ) {
                                        ans [id] = len ;
                                }
                        }
                }
                for ( auto u : ret ) que [b] .era ( u ) ;
        }
        if ( who[a].size() > who[b].size() ) swap ( a , b ) ;
        for ( auto u : who [a] ) who [b] . ins ( u ) ;
        for ( auto u : que [a] ) {
                for ( auto it : u.se ){
                        que[b][u.fi] .pb ( it ) ;
                }
        }
        p [a] = b ;
}
int main () {
        scanf("%d%d%d",&n,&m,&q);
        for ( int i = 0 ; i < n ; i ++ ) {
                p[i] = i ;
                who[i] .ins ( i ) ;
        }
        for ( int i = 0 ; i < q ; i ++ ) {
                int a , b ;
                scanf("%d%d",&a,&b);
                a -- , b -- ;
                if ( a > b ) swap ( a , b ) ;
                que[a][b] .pb ( 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 ) ;
                }
        }
        for ( int i = 0 ; i < q ; i ++ ) printf("%d\n",ans[i]) ;
}

Compilation message

pictionary.cpp: In function 'int main()':
pictionary.cpp:116:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for ( int j = 1 ; j < nodes.size() ; j ++ ) {
                                   ~~^~~~~~~~~~~~~~
pictionary.cpp:99:14: 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:106:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d",&a,&b);
                 ~~~~~^~~~~~~~~~~~~~

Subtask #1

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	10752 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	13184 KB	Output is correct

Subtask #3

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	94 ms	22268 KB	Output is correct
2	Correct	89 ms	19580 KB	Output is correct

Subtask #4

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	28024 KB	Output is correct
2	Correct	121 ms	24056 KB	Output is correct

Subtask #5

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	21280 KB	Output is correct
2	Correct	102 ms	20768 KB	Output is correct

Subtask #6

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	122 ms	23036 KB	Output is correct
2	Correct	117 ms	20528 KB	Output is correct

Subtask #7

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	179 ms	28524 KB	Output is correct
2	Correct	185 ms	24796 KB	Output is correct

Subtask #8

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	203 ms	25148 KB	Output is correct
2	Correct	244 ms	34508 KB	Output is correct

Subtask #9

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	292 ms	37676 KB	Output is correct
2	Correct	295 ms	37360 KB	Output is correct

Subtask #10

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	347 ms	43148 KB	Output is correct
2	Correct	335 ms	41212 KB	Output is correct