제출 #821940

#제출 시각아이디문제언어결과실행 시간메모리
821940smirichto다리 (APIO19_bridges)C++17
59 / 100
3022 ms78952 KiB
#include<bits/stdc++.h> using namespace std ; // dsu with rollback int n , q , m ; const int B = 500 , N = 2e5 + 5 ; stack<int> stck; int sz[N], cmp[N]; void reset() { iota(cmp + 1, cmp + 1 + n, 1); fill(sz + 1, sz + n + 1, 1); while (!stck.empty()) stck.pop() ; } inline int find(int a) { while (cmp[a] != a) a = cmp[a]; return a; } void onion(int a, int b) { a = find(a), b = find(b); if (a == b) return; if (sz[a] > sz[b]) swap(a, b); stck.push(a); sz[b] += sz[a]; cmp[a] = cmp[b]; } void rollback(int x) { assert(x>=0) ; while (stck.size() > x) { int k = stck.top(); stck.pop(); sz[cmp[k]] -= sz[k]; cmp[k] = k; } } vector<array<int,4>> qr[N]; int ans[N] , typ[N]; int old[N] , changed[N] , u[N] , v[N] ; vector<int> bonus[N] ; void solve(){ cin>>n>>m ; for(int i = 1 ; i<=m ; i++){ cin>>u[i]>>v[i]>>old[i] ; } cin>>q ; for(int i = 1 ; i<=q ; i++){ int tp , a , b ; cin>>tp>>a>>b ; qr[i/B].push_back({tp , a , b , i}) ; typ[i] = tp ; } for(int block = 0 ; block<=q/B ; block++){ reset() ; for(int i = 1 ; i<=m ; i++) changed[i] = 0 ; vector<array<int,3>> vec ; for(auto a : qr[block]){ if(a[0]==1){ changed[a[1]] = 1 ; old[a[1]] = a[2] ; } else{ vec.push_back({a[2] , a[1] , a[3]}) ; bonus[a[3]].clear() ; for(auto e : qr[block]){ if(e[0]==1 && old[e[1]] >= a[2]){ bonus[a[3]].push_back(e[1]) ; } } } } vector<array<int,2>> edges ; for(int j = 1 ; j<=m ; j++){ if(changed[j]) continue; edges.push_back({old[j] , j}) ; } sort(edges.rbegin() , edges.rend()) ; sort(vec.rbegin() , vec.rend()) ; int j = 0 ; for(auto & i : vec){ while(j<edges.size() && edges[j][0]>=i[0]){ onion(u[edges[j][1]] , v[edges[j][1]]) ; ++j ; } int c = stck.size() ; for(auto & e : bonus[i[2]]){ onion(u[e] , v[e]) ; } ans[i[2]] = sz[find(i[1])] ; rollback(c) ; } } for(int i = 1 ; i<=q ; i++){ if(typ[i]==1) continue; cout<<ans[i]<<endl; } } int main(){ ios::sync_with_stdio(false) ; cin.tie(nullptr) ; solve() ; }

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:33:24: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |     while (stck.size() > x) {
      |            ~~~~~~~~~~~~^~~
bridges.cpp: In function 'void solve()':
bridges.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             while(j<edges.size() && edges[j][0]>=i[0]){
      |                   ~^~~~~~~~~~~~~
#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...