Submission #257985

#TimeUsernameProblemLanguageResultExecution timeMemory
257985BamiTorabiBridges (APIO19_bridges)C++14
27 / 100
3061 ms14348 KiB
//Sasayego! Sasayego! Shinzou wo Sasageyo! #include <iostream> #include <iomanip> #include <algorithm> #include <cmath> #include <ctime> #include <cstring> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <deque> #include <numeric> #include <bitset> #include <ctime> #define debug(x) cerr << #x << " = " << x << endl #define lid (id << 1) #define rid (lid ^ 1) using namespace std; typedef long long ll; typedef long double ld; typedef pair <ll, ll> pll; typedef pair <int, int> pii; const int maxN = 1e5 + 5; const int SQ = 1000; const ll INF = 1e18; const ll MOD = 1e9 + 7; struct triple{ int first, second, third; } E[maxN], Q[maxN]; stack <int> st; int par[maxN], sz[maxN]; int change[maxN], wt[maxN], ans[maxN]; vector <int> vec, Eix[maxN], Qix[maxN], tmp; int getpar(int v, bool flag = false){ if (!flag) return (par[v] == v ? v : par[v] = getpar(par[v], flag)); while (par[v] != v) v = par[v]; return v; } void join(int u, int v, bool flag = false){ u = getpar(u, flag); v = getpar(v, flag); if (u == v){ if (flag) st.push(-1); return; } if (sz[u] < sz[v]) swap(u, v); if (flag) st.push(v); par[v] = u; sz[u] += sz[v]; return; } void undo(){ int v = st.top(); st.pop(); if (v == -1) return; int u = par[v]; sz[u] -= sz[v]; par[v] = v; return; } int main(){ time_t START = clock(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) scanf("%d%d%d", &E[i].second, &E[i].third, &E[i].first); int q; scanf("%d", &q); for (int i = 0; i < q; i++){ scanf("%d%d%d", &Q[i].first, &Q[i].second, &Q[i].third); vec.push_back(Q[i].third); } sort(vec.begin(), vec.end()); vec.resize(unique(vec.begin(), vec.end()) - vec.begin()); for (int i = 1; i <= m; i++) E[i].first = upper_bound(vec.begin(), vec.end(), E[i].first) - vec.begin() - 1; for (int i = 0; i < q; i++) Q[i].third = upper_bound(vec.begin(), vec.end(), Q[i].third) - vec.begin() - 1; for (int id = 0, ss = SQ; id < q; id += ss){ ss = min(ss, q - id); for (int i = 1; i <= m; i++) change[i] = false; for (int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; } for (int i = id; i < id + ss; i++){ if (Q[i].first == 1) change[Q[i].second] = true; else Qix[Q[i].third].push_back(i); } for (int i = 1; i <= m; i++) (change[i] ? tmp.push_back(i) : Eix[E[i].first].push_back(i)); sort(tmp.begin(), tmp.end()); for (int i = (int)vec.size(); i > -1; i--){ for (int e : Eix[i]) join(E[e].second, E[e].third); for (int x : Qix[i]){ for (int e : tmp) wt[e] = E[e].first; for (int i = id; i < x; i++) if (Q[i].first == 1) wt[Q[i].second] = Q[i].third; for (int e : tmp) if (wt[e] >= i) join(E[e].second, E[e].third, 1); ans[x] = sz[getpar(Q[x].second, 1)]; while (!st.empty()) undo(); } Eix[i].clear(); Qix[i].clear(); } for (int i = id; i < id + ss; i++) if (Q[i].first == 1) E[Q[i].second].first = Q[i].third; } for (int i = 0; i < q; i++) if (Q[i].first == 2) printf("%d\n", ans[i]); time_t FINISH = clock(); cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n"; return 0; }

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:79:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m; scanf("%d%d", &n, &m);
            ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &E[i].second, &E[i].third, &E[i].first);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int q; scanf("%d", &q);
         ~~~~~^~~~~~~~~~
bridges.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &Q[i].first, &Q[i].second, &Q[i].third);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...