제출 #494433

#제출 시각아이디문제언어결과실행 시간메모리
494433jjang36524다리 (APIO19_bridges)C++14
14 / 100
3069 ms21308 KiB
#include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define MAX 201010 #define MAXS 20 #define INF 1000000000000000001 #define bb ' ' #define ln '\n' #define Ln '\n' #define B 1000 struct dsu { vector<vector<ll>> p, num; vector<ll> chk; ll qnum = 0; dsu(ll N) { p.resize(2); num.resize(2); p[0].resize(N + 1); p[1].resize(N + 1); num[0].resize(N + 1); num[1].resize(N + 1); ll i; for (i = 1; i <= N; i++) p[0][i] = i, num[0][i] = 1; } ll find(ll v) { if (!p[qnum][v]) { p[qnum][v] = p[0][v]; chk.push_back(v); } if (p[qnum][v] == v) return v; else return p[qnum][v] = find(p[qnum][v]); } ll get(ll v) { v = find(v); if (!num[qnum][v]) { num[qnum][v] = num[0][v]; chk.push_back(v); } return num[qnum][v]; } void uni(ll a, ll b) { a = find(a); b = find(b); if (a == b) return; if (get(b) < get(a)) swap(a, b); ll x = get(b) + get(a); p[qnum][a] = b; num[qnum][b] = x; if (qnum == 1) chk.push_back(b), chk.push_back(a); } void rb() { for (auto x : chk) { num[1][x] = p[1][x] = 0; } chk.clear(); qnum = 0; } void mark() { qnum++; } }; struct query { ll t; ll b, r, s, w; ll ind; query(ll t, ll x, ll y, ll ind) :ind(ind) { query::t = t; if (t == 1) b = x, r = y; else s = x, w = y; } query() {} }; vector<pll> edge; ll val[MAX]; vector<query> qv[2000]; query qarr[MAX]; ll ans[MAX]; ll chk[MAX]; ll nchk[MAX]; bool cmp(query& a, query& b) { return a.w > b.w; } signed main() { ios::sync_with_stdio(false), cin.tie(0); ll N, M; cin >> N >> M; ll i; edge.resize(M + 1); for (i = 1; i <= M; i++) { ll a, b; cin >> a >> b >> val[i]; edge[i] = { a, b }; } ll Q; cin >> Q; for (i = 1; i <= Q; i++) { ll a, b, c; cin >> a >> b >> c; qarr[i] = query(a, b, c, i); qv[(i - 1) / B].push_back(qarr[i]); } ll st, en; set<pll> est; for (i = 1; i <= M; i++) est.emplace(-val[i], i); for (i = 0; ; i++) { st = 1 + i * B; en = (1 + i) * B; en = min(en, Q); if (st > en) break; ll j; for (j = st; j <= en; j++) if (qarr[j].t == 1) chk[qarr[j].b] = 1; vector<query> qq; for (auto& q : qv[i]) if (q.t == 2) qq.push_back(q); if (qq.size()) sort(qq.begin(), qq.end(), cmp); dsu d(N); set<pll>::iterator it; it = est.begin(); for (ll j = 0; j < qq.size(); j++) { for (; it != est.end(); it++) { if (chk[it->second]) continue; if (qq[j].w > -it->first) break; else d.uni(edge[it->second].first, edge[it->second].second); } d.mark(); ll cnt = 0; for (ll k = qq[j].ind; k >= st; k--) { if (qarr[k].t == 1) { if (qarr[k].r >= qq[j].w && !nchk[qarr[k].b]) { d.uni(edge[qarr[k].b].first, edge[qarr[k].b].second); nchk[qarr[k].b] = 1; } } } for (ll k = en; k > qq[j].ind; k--) { if (qarr[k].t == 1) { if (!nchk[qarr[k].b] && val[qarr[k].b] >= qq[j].w) { d.uni(edge[qarr[k].b].first, edge[qarr[k].b].second); nchk[qarr[k].b] = 1; } } } for (ll k = en; k >= st; k--) if (qarr[k].t == 1) nchk[qarr[k].b] = 0; ans[qq[j].ind] = d.get(qq[j].s); d.rb(); } for (j = st; j <= en; j++) { if (qarr[j].t == 1) { chk[qarr[j].b] = 0; est.erase({ -val[qarr[j].b], qarr[j].b }); est.emplace(-qarr[j].r, qarr[j].b); val[qarr[j].b] = qarr[j].r; } } } for (i = 1; i <= Q; i++) if (ans[i]) cout << ans[i] << ln; }

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

bridges.cpp: In function 'int main()':
bridges.cpp:125:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   for (ll j = 0; j < qq.size(); j++) {
      |                  ~~^~~~~~~~~~~
bridges.cpp:132:7: warning: unused variable 'cnt' [-Wunused-variable]
  132 |    ll cnt = 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...