Submission #896177

#TimeUsernameProblemLanguageResultExecution timeMemory
896177thunoproBridges (APIO19_bridges)C++14
13 / 100
85 ms19100 KiB
#include<bits/stdc++.h> using namespace std ; #define ll long long #define maxn 100009 #define fi first #define se second #define pb push_back #define left id<<1 #define right id<<1|1 #define re exit(0); #define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1 const int mod = 1e9+7 ; const int INF = 1e9 ; const int LOG = 18 ; typedef vector<int> vi ; typedef pair<int,int> pii ; typedef vector<ll> vl ; typedef vector<pii> vii ; void add ( int &a , int b ) { a += b ; if ( a < 0 ) a += mod ; if ( a >= mod ) a -= mod ; } template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } void rf () { freopen ("bai1.inp","r",stdin) ; // freopen ("bai1.out","w",stdout) ; } int _pow ( int a , int n ) { if ( n == 0 ) return 1 ; int res = _pow (a,n/2) ; if ( n % 2 ) return 1ll*res*res%mod*a%mod ; else return 1ll*res*res%mod ; } int n , m , nq ; struct edge { int u , v , w ; }a[maxn]; struct query { int t , s , w ; }q[maxn]; const int block = 600 ; bool cmp_aw ( int u , int v ) { return a [u].w > a [v].w ; } bool cmp_qw ( int u , int v ) { return q [u].w > q [v].w ; } int par [maxn] , sz [maxn] , changed [maxn] ; void reset () { for ( int i = 1 ; i <= n ; i ++ ) par [i] = i , sz [i] = 1 ; for ( int i = 1 ; i <= m ; i ++ ) changed [i] = false ; } vi to_join [maxn] ; int find ( int u ) { if ( par [u] == u ) return u ; return find (par[u]) ; } int *roll [maxn*2] , val [maxn*2] , top ; void update_roll ( int *a , int b ) { if ( *a == b ) return ; roll [++top] = a ; val [top] = *a ; *a = b ; } void rollback ( int cur ) { while ( top > cur ) { *roll [top] = val [top] ; top -- ; } } void uni ( int u , int v ) { int p = find (u) , q = find (v) ; if ( p == q ) return ; if ( sz [p] > sz [q] ) swap (p,q) ; update_roll (&sz[q],sz[p]+sz[q]) ; update_roll (&par[p],q) ; } int ans [maxn] ; int main () { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0) ; // rf () ; cin >> n >> m ; for ( int i = 1 ; i <= m ; i ++ ) cin >> a[i].u >> a[i].v >> a[i].w ; cin >> nq ; for ( int i = 1 ; i <= nq ; i ++ ) cin >> q[i].t >> q[i].s >> q[i].w ; for ( int l = 1 ; l <= nq ; l += block ) { int r = min (nq+1,l+block) - 1 ; reset () ; vi upd , unchanged , ask ; for ( int i = l ; i <= r ; i ++ ) { if ( q[i].t == 1 ) { changed[q[i].s] = true ; upd . pb (i) ; } else ask . pb (i) ; } for ( int i = 1 ; i <= m ; i ++ ) if ( changed [i] == false ) unchanged . pb (i) ; for ( int i = l ; i <= r ; i ++ ) { if ( q[i].t == 1 ) { a[q[i].s].w = q[i].w ; } else { for ( auto x : upd ) { if ( a[q[x].s].w >= q[i].w ) to_join [i] . pb (q[x].s) ; } } } sort (unchanged.begin(),unchanged.end(),cmp_aw) ; sort (ask.begin(),ask.end(),cmp_qw) ; int j = 0 ; for ( auto x : ask ) { while ( j < unchanged.size() && a[unchanged[j]].w >= q[x].w ) { int u = a[unchanged[j]].u , v = a[unchanged[j]].v ; uni (u,v) ; j ++ ; } int cur = top ; for ( auto y : to_join [x] ) { int u = a[y].u , v = a[y].v ; uni (u,v) ; } ans [x] = sz[find(q[x].s)] ; rollback (cur) ; } } for ( int i = 1 ; i <= nq ; i ++ ) if ( q[i].t == 2 ) cout << ans [i] << "\n" ; } // range , error , check special , ... // find key , find key //'-std=c++11' stay hard // there is no tomorrow hb

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:156:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |    while ( j < unchanged.size() && a[unchanged[j]].w >= q[x].w )
      |            ~~^~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'void rf()':
bridges.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...