제출 #166596

#제출 시각아이디문제언어결과실행 시간메모리
166596Feeder다리 (APIO19_bridges)C++11
0 / 100
1102 ms7404 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; int par[50001], sz[50001], rnk[50001]; int findp(int x){ return x == par[x] ? x : findp(par[x]); } void merge(int x, int y){ x = findp(x), y = findp(y); if(x == y) return; if(rnk[x] < rnk[y]) swap(x, y); par[y] = x; if(rnk[x] == rnk[y]) rnk[x]++; sz[x] += sz[y]; } int edgea[100001], edgeb[100001], ans[100001]; vector<tuple<int, int> > edgelist; vector<tuple<int, int, int> > uvec; // query, bridge, weight vector<tuple<int, int, int> > qvec; // weight, query, island int qcnt = 0; int cbridges[100001]; void findans(int qnum){ vector<tuple<int, int, int> > st; vector<int> vec; int qw, qi, qq; tie(qw, qq, qi) = qvec[qnum]; int aa, bb, ww; for(int i=int(uvec.size())-1; i>=0; i--){ if(get<0>(uvec[i]) > qq) continue; int bnum = get<1>(uvec[i]); ww = get<2>(uvec[i]); if(cbridges[bnum] == 2) continue; cbridges[bnum] = 2; vec.push_back(bnum); if(ww < qw) continue; aa = edgea[bnum], bb = edgeb[bnum]; aa = findp(aa), bb = findp(bb); if(aa == bb) continue; if(rnk[aa] < rnk[bb]) swap(aa, bb); if(rnk[aa] == rnk[bb]){ st.emplace_back(aa, bb, sz[aa]); rnk[aa]++; } else st.emplace_back(aa, bb, -sz[aa]); par[bb] = aa; sz[aa] += sz[bb]; } for(auto i:vec) cbridges[i] = 1; ans[qq] = sz[findp(qi)]; for(int i=int(st.size())-1; i>=0; i--){ tie(aa, bb, ww) = st[i]; if(ww > 0) rnk[aa]--; else ww = -ww; par[bb] = bb; sz[aa] = ww; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, m, a, b, w, q, warr[100001], rt = 200; cin >> n >> m; for(int i=1; i<=m; i++){ cin >> edgea[i] >> edgeb[i] >> warr[i]; edgelist.emplace_back(-warr[i], i); } cin >> q; int tarr[100001], aarr[100001], barr[100001], curq = 0; for(int i=0; i<q; i++) cin >> tarr[i] >> aarr[i] >> barr[i]; for(int i=0; i<q; i++){ a = aarr[i], b = barr[i]; if(tarr[i] == 1){ uvec.emplace_back(i, a, b); if(!cbridges[a]){ cbridges[a] = 1; uvec.emplace_back(-1, a, warr[a]); } curq += 1; } else qvec.emplace_back(b, i, a); if(curq != rt - 1 && i != q - 1) continue; curq = 0; qcnt = int(qvec.size()) - 1; sort(qvec.begin(), qvec.end()); sort(uvec.begin(), uvec.end()); for(int j=1; j<=n; j++) par[j] = j; fill(sz + 1, sz + n + 1, 1); fill(rnk + 1, rnk + n + 1, 0); for(auto it:edgelist){ tie(w, a) = it; w = -w; while(qcnt >= 0 && get<0>(qvec[qcnt]) > w) findans(qcnt--); if(cbridges[a]) continue; merge(edgea[a], edgeb[a]); } while(qcnt >= 0) findans(qcnt--); vector<tuple<int, int> > vec; vector<tuple<int, int> > newvec; for(int j=int(uvec.size())-1; j>=0; j--){ tie(qcnt, b, w) = uvec[j]; if(qcnt < 0) break; if(cbridges[b] == 0 || cbridges[b] == 2) continue; vec.emplace_back(-w, b); warr[b] = w; cbridges[b] = 2; } int cnt1 = 0, cnt2 = 0; for(auto j:edgelist) newvec.push_back(j); edgelist.clear(); while(cnt1 < newvec.size() || cnt2 < vec.size()){ if(cnt1 == newvec.size()) edgelist.push_back(vec[cnt2++]); else if(cnt2 == vec.size()){ if(cbridges[get<1>(newvec[cnt1])] != 2) edgelist.push_back(newvec[cnt1++]); else cnt1++; } else if(get<0>(newvec[cnt1]) < get<0>(vec[cnt2])){ if(cbridges[get<1>(newvec[cnt1])] != 2) edgelist.push_back(newvec[cnt1++]); else cnt1++; } else edgelist.push_back(vec[cnt2++]); } for(int j=int(uvec.size())-1; j>=0; j--){ tie(qcnt, b, w) = uvec[j]; if(qcnt < 0) break; if(cbridges[b] == 2) cbridges[b] = 0; } uvec.clear(); qvec.clear(); } for(int i=0; i<q; i++){ if(ans[i]) cout << ans[i] << '\n'; } }

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

bridges.cpp: In function 'int main()':
bridges.cpp:117:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(cnt1 < newvec.size() || cnt2 < vec.size()){
         ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:117:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(cnt1 < newvec.size() || cnt2 < vec.size()){
                                 ~~~~~^~~~~~~~~~~~
bridges.cpp:118:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(cnt1 == newvec.size()) edgelist.push_back(vec[cnt2++]);
       ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:119:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    else if(cnt2 == vec.size()){
            ~~~~~^~~~~~~~~~~~~
#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...