Submission #1266147

#TimeUsernameProblemLanguageResultExecution timeMemory
1266147icebearBridges (APIO19_bridges)C++20
14 / 100
2053 ms7604 KiB
// ~~ icebear ~~ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef pair<int, ii> iii; template<class T> bool minimize(T &a, const T &b) { if (a > b) return a = b, true; return false; } template<class T> bool maximize(T &a, const T &b) { if (a < b) return a = b, true; return false; } #define FOR(i,a,b) for(int i=(a); i<=(b); ++i) #define FORR(i,a,b) for(int i=(a); i>=(b); --i) #define REP(i, n) for(int i=0; i<(n); ++i) #define RED(i, n) for(int i=(n)-1; i>=0; --i) #define MASK(i) (1LL << (i)) #define BIT(S, i) (((S) >> (i)) & 1) #define mp make_pair #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() #define task "icebear" const int MOD = 1e9 + 7; const int inf = 1e9 + 27092008; const ll INF = 1e18 + 27092008; const int N = 100000 + 5; const int S = 500; int n, m, q; array<int, 3> tmp[N], queries[N]; struct DSU { int lab[N]; vector<array<int, 4>> history; void reset() { memset(lab, -1, sizeof lab); } void del_history() { history.clear(); } int root(int v) { return (lab[v] < 0 ? v : root(lab[v])); } bool unite(int u, int v) { u = root(u); v = root(v); if (u == v) return false; if (lab[u] > lab[v]) swap(u, v); history.pb({u, lab[u], v, lab[v]}); lab[u] += lab[v]; lab[v] = u; return true; } void roll_back() { while(!history.empty()) { auto T = history.back(); lab[T[0]] = T[1]; lab[T[2]] = T[3]; history.pop_back(); } } int sz(int x) { x = root(x); return -lab[x]; } } dsu; void init(void) { cin >> n >> m; FOR(i, 1, m) REP(j, 3) cin >> tmp[i][j]; cin >> q; FOR(i, 1, q) REP(j, 3) cin >> queries[i][j]; } void process(void) { vector<bool> change(m + 5, false); vector<int> ans(q + 5, -1), firstVal(m + 5, -1); for(int B = 1; B <= q; B += S) { int L = B, R = min(q, B + S - 1); vector<array<int, 3>> Q, edges; vector<ii> indexs; FOR(i, L, R) if (queries[i][0] == 1) { indexs.pb(mp(queries[i][1], i)); change[queries[i][1]] = true; } else { Q.push_back({queries[i][1], queries[i][2], i}); } FOR(i, 1, m) if (change[i] == false) edges.pb(tmp[i]); sort(all(edges), [&](const array<int, 3> &x, const array<int, 3> &y){ return x[2] > y[2]; }); sort(all(Q), [&](const array<int, 3> &x, const array<int, 3> &y){ return x[1] > y[1]; }); dsu.reset(); int j = 0; for(auto &x : Q) { while(j < (int)edges.size() && edges[j][2] >= x[1]) { dsu.unite(edges[j][0], edges[j][1]); j++; } dsu.del_history(); for(auto &e : indexs) { if (e.se > x[2]) break; if (firstVal[e.fi] == -1) firstVal[e.fi] = tmp[e.fi][2]; tmp[e.fi][2] = queries[e.se][2]; } for(auto &e : indexs) { if (tmp[e.fi][2] >= x[1]) dsu.unite(tmp[e.fi][0], tmp[e.fi][1]); } for(auto &e : indexs) { if (e.se > x[2]) break; tmp[e.fi][2] = firstVal[e.fi]; firstVal[e.fi] = -1; } ans[x[2]] = dsu.sz(x[0]); dsu.roll_back(); } for(auto &e : indexs) { change[e.fi] = false; tmp[e.fi][2] = queries[e.se][2]; } } for(int &x : ans) if (x != -1) cout << x << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int tc = 1; // cin >> tc; while(tc--) { init(); process(); } return 0; }

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:161:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:162:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...