oj.uz

답안 #224331

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
224331 2020-04-17T17:12:07 Z infinite_iq Pictionary (COCI18_pictionary) C++14
140 / 140
 347 ms 43148 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 ;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 10752 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 13184 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 347 ms 43148 KB Output is correct
2 Correct 335 ms 41212 KB Output is correct