Submission #938257

#TimeUsernameProblemLanguageResultExecution timeMemory
938257Zero_OPBridges (APIO19_bridges)C++14
100 / 100
2965 ms58208 KiB
#include<bits/stdc++.h> using namespace std; using int64 = int64_t; #define REP(i, n) for(int i = 0, _n = n; i < _n; ++i) #define REPD(i, n) for(int i = n - 1; i >= 0; --i) #define FOR(i, l, r) for(int i = l, _r = r; i <= _r; ++i) #define FORD(i, r, l) for(int i = r, _l = l; i >= _l; --i) #define left __left #define right __right #define prev __prev #define next __next #define div __div #define pb push_back #define pf push_front #define sz(v) (int)v.size() #define range(v) begin(v), end(v) #define compact(v) v.erase(unique(range(v)), end(v)) #define debug(v) "[" #v " = " << (v) << "]" template<typename T> bool minimize(T& a, const T& b){ if(a > b){ a = b; return true; } return false; } template<typename T> bool maximize(T& a, const T& b){ if(a < b){ a = b; return true; } return false; } template<int dimension, class T> struct vec : public vector<vec<dimension - 1, T>> { static_assert(dimension > 0, "Dimension must be positive !\n"); template<typename... Args> vec(int n = 0, Args... args) : vector<vec<dimension - 1, T>>(n, vec<dimension - 1, T>(args...)) {} }; template<class T> struct vec<1, T> : public vector<T> { vec(int n = 0, T val = T()) : vector<T>(n, val) {} }; void init(void); void process(void); int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #define task "antuvu" if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int T = 1; //cin >> T; while(T--) { init(); process(); } return 0; } const int N = 1e5 + 5; const int B = 400; int n, m, q, u[N], v[N], d[N], t[N], a[N], b[N], ans[N]; bool modified[N]; vector<int> edges[N]; struct DisjointSet{ stack<tuple<int, int, int, int>> operations; vector<int> lab; DisjointSet(int n) : lab(n, -1), operations() {} int root(int u){ return lab[u] < 0 ? u : root(lab[u]); } 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); operations.push({u, lab[u], v, lab[v]}); lab[u] += lab[v]; lab[v] = u; return true; } bool same_set(int u, int v){ return root(u) == root(v); } int get_size(int u){ return -lab[root(u)]; } void rollback(){ int u, pu, v, pv; tie(u, pu, v, pv) = operations.top(); operations.pop(); lab[u] = pu; lab[v] = pv; } void roll(int cnt){ while(cnt--) rollback(); } void reset(){ while(!operations.empty()) operations.pop(); fill(range(lab), -1); } }; void init(){ cin >> n >> m; REP(i, m){ cin >> u[i] >> v[i] >> d[i]; --u[i], --v[i]; } cin >> q; REP(i, q){ cin >> t[i] >> a[i] >> b[i]; --a[i]; } } void process(){ DisjointSet dsu(n); for(int l = 0; l < q; l += B){ int r = min(l + B - 1, q - 1); dsu.reset(); memset(modified, false, sizeof(modified)); vector<int> updates, queries; FOR(i, l, r){ if(t[i] == 1){ modified[a[i]] = true; updates.pb(i); } else queries.push_back(i); } vector<int> unchanged_edges; REP(i, m) if(!modified[i]) unchanged_edges.pb(i); sort(range(unchanged_edges), [&](int i, int j){ return d[i] > d[j]; }); sort(range(queries), [&](int i, int j){ return b[i] > b[j]; }); FOR(i, l, r){ if(t[i] == 1){ d[a[i]] = b[i]; } else{ for(int x : updates){ if(d[a[x]] >= b[i]){ edges[i].pb(a[x]); } } } } int j = 0; REP(i, sz(queries)){ int id = queries[i]; while(j < sz(unchanged_edges) && d[unchanged_edges[j]] >= b[id]){ dsu.unite(u[unchanged_edges[j]], v[unchanged_edges[j]]); ++j; } int cnt = 0; for(int k : edges[id]) { cnt += dsu.unite(u[k], v[k]); } ans[id] = dsu.get_size(a[id]); dsu.roll(cnt); } } REP(i, q){ if(t[i] == 2) cout << ans[i] << '\n'; } }

Compilation message (stderr)

bridges.cpp: In constructor 'DisjointSet::DisjointSet(int)':
bridges.cpp:82:17: warning: 'DisjointSet::lab' will be initialized after [-Wreorder]
   82 |     vector<int> lab;
      |                 ^~~
bridges.cpp:81:38: warning:   'std::stack<std::tuple<int, int, int, int> > DisjointSet::operations' [-Wreorder]
   81 |     stack<tuple<int, int, int, int>> operations;
      |                                      ^~~~~~~~~~
bridges.cpp:83:5: warning:   when initialized here [-Wreorder]
   83 |     DisjointSet(int n) : lab(n, -1), operations() {}
      |     ^~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         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...