Submission #224331

#TimeUsernameProblemLanguageResultExecution timeMemory
224331infinite_iqPictionary (COCI18_pictionary)C++14
140 / 140
347 ms43148 KiB
#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 (stderr)

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);
                 ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...