Submission #1260381

#TimeUsernameProblemLanguageResultExecution timeMemory
1260381khanhdangiuuBridges (APIO19_bridges)C++20
100 / 100
1745 ms59760 KiB
//#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define int long long #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define fi first #define se second #define rep(i, a, b) for (int i = a; i <= b; ++i) #define per(i, b, a) for (int i = b; i >= a; --i) #define pb push_back #define eb emplace_back #define all(v) (v).begin(), (v).end() #define lsb(x) (x)&(-x) #define bug(x) cerr << #x << " " << x << endl; void setIO(string name = "") { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); if (!name.empty()) { freopen((name + ".in").c_str(), "r", stdin); freopen((name + ".out").c_str(), "w", stdout); } } ll fexp(ll a, ll b, ll m) { if (b == 0) return 1LL; ll p = a; ll ans = 1; while (b > 0) { if (b % 2 != 0) ans = (ans * p) % m; p = (p * p) % m; b >>= 1; } return ans; } const int MAXN = 1e5 + 10; const int INF = 1e18 + 5; const int MOD = 1e9+7; const int B = 1e3; int u[MAXN],v[MAXN],w[MAXN],n,m,k,q; int t[MAXN],x[MAXN], y[MAXN], ans[MAXN]; bool mk[MAXN]; vector<int> tj[MAXN]; stack<int> stk; int sz[MAXN],pr[MAXN]; void reset() { iota(pr+1,pr+n+1, 1); fill(sz + 1, sz + n + 1, 1); fill(mk + 1, mk + m + 1, false); } int find(int a) { if (a == pr[a]) return a; return find(pr[a]); } void join(int a, int b) { a = find(a); b = find(b); if (a==b) return; if (sz[a] > sz[b]) swap(a,b); stk.push(a); sz[b]+=sz[a]; pr[a] = pr[b]; } void rollback(int x) { while (stk.size() > x) { int k = stk.top(); stk.pop(); sz[pr[k]] -= sz[k]; pr[k] = k; } } void solve() { cin >> n >> m; rep(i,1,m) cin >> u[i] >> v[i] >> w[i]; cin >> q; rep(i,1,q) cin >> t[i] >> x[i] >> y[i]; for (int l = 1; l <= q; l += B) { int r = min(q,l+B-1); reset(); vector<int> ask, upd, unmk; rep(i,l,r) { if (t[i] == 1) { mk[x[i]] = 1; upd.pb(i); } else { ask.pb(i); } } rep(i,1,m) if (!mk[i]) unmk.pb(i); rep(i,l,r) { if (t[i] == 1) { w[x[i]] = y[i]; } else { tj[i-l].clear(); for (int j : upd) { if (w[x[j]] >= y[i]) { tj[i - l].pb(x[j]); } } } } sort(all(ask), [&](int a, int b) { return y[a] > y[b]; }); sort(all(unmk), [&](int a, int b) { return w[a] > w[b]; }); int ptr = 0; for (int i : ask) { while (ptr < unmk.size() && w[unmk[ptr]] >= y[i]) { join(u[unmk[ptr]], v[unmk[ptr]]); ptr++; } int tmp = stk.size(); for (auto i : tj[i-l]) join(u[i], v[i]); ans[i] = sz[find(x[i])]; rollback(tmp); } } rep(i,1,q) if (t[i]==2) cout << ans[i] << '\n'; } int32_t main() { setIO(); int tt = 1; //cin >> tt; while (tt-- > 0) solve(); return 0; }

Compilation message (stderr)

bridges.cpp: In function 'void setIO(std::string)':
bridges.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen((name + ".out").c_str(), "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...