이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define maxn 200009
#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 = 1000 ;
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
컴파일 시 표준 에러 (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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |