Submission #523184

#TimeUsernameProblemLanguageResultExecution timeMemory
523184LptN21Bridges (APIO19_bridges)C++14
0 / 100
529 ms16352 KiB
#include <bits/stdc++.h> using namespace std; #define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL); #define PI acos(-1.0) #define eps 1e-9 #define FF first #define SS second // VECTOR (6) #define pb push_back #define lb lower_bound #define ub upper_bound #define sz(v) int((v).size()) #define all(v) (v).begin(), (v).end() #define uniq(v) sort(all( (v) )), (v).resize( unique(all( (v) )) - (v).begin() ); // BIT (6) #define CNTBIT(x) __builtin_popcountll(x) #define ODDBIT(x) __builtin_parityll(x) #define MASK(i) (1LL<<(i)) #define BIT(x, i) (((x)>>(i))&1) #define SUBSET(big, small) (((big)&(small))==(small)) #define MINBIT(x) (x)&(-x) #define FIRSTBIT(x) __builtin_ctzll(x) //typedef typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, int> ii; /* */ template<class T> bool minimize(T &a, const T &b) { if(a > b) {a = b; return 1;} return 0; } template<class T> bool maximize(T &a, const T &b) { if(a < b) {a = b; return 1;} return 0; } /* */ /* CODE BELOW */ const int N = 5e4 + 7, M = 1e5 + 7; const int oo = 1e9 + 7; const int MOD = 1e9 + 7; int n, m, q, t; const int B = 1000; // size block struct Edge{ int u, v, w; bool operator<(const Edge &e) const { if(w != e.w) return w < e.w; if(u != e.u) return u < e.u; return v < e.v; } } e[M]; struct Query{int t, u, w;} qry[M]; bool changedEdge[M]; vector<int> careEdge[B + 7]; int ans[M]; // int dsu[N]; vector<ii> rollback; int root(int u) { if(dsu[u] < 0) return u; rollback.pb(ii(u, dsu[u])); return dsu[u] = root(dsu[u]); } bool join(int u, int v) { if((u=root(u)) == (v=root(v))) return 0; if(dsu[u] > dsu[v]) swap(u, v); rollback.pb(ii(u, dsu[u])); rollback.pb(ii(v, dsu[v])); dsu[u]+= dsu[v], dsu[v] = u; return 1; } void goback(int time) { while(sz(rollback)>time) { ii event = rollback.back(); dsu[event.FF] = event.SS; rollback.pop_back(); } } // void init() { memset(dsu, -1, sizeof(int)*(n+1)); rollback.clear(); } signed main() { //freopen("test.inp", "r", stdin); //freopen("test.out", "w", stdout); //fastIO; scanf("%d%d", &n, &m); int u, v, w; for(int i=1;i<=m;i++) { scanf("%d%d%d", &u, &v, &w); e[i] = {u, v, w}; } scanf("%d", &q); for(int i=1;i<=q;i++) { scanf("%d%d%d", &t, &u, &w); qry[i] = {t, u, w}; } for(int r, l=1;l<=q;l = r+1) { r = min(q, l+B-1); init(); vector<int> ask, update, unchanged; for(int i=l;i<=r;i++) { if(qry[i].t == 1) { update.pb(i); changedEdge[qry[i].u] = 1; } } for(int i=l;i<=r;i++) { if(qry[i].t == 1) { e[qry[i].u].w = qry[i].w; } else { careEdge[i].clear(); for(int j:update) { if(e[qry[j].u].w>=qry[i].w) { careEdge[i].pb(qry[j].u); } } ask.pb(i); } } for(int i=1;i<=m;i++) if(!changedEdge[i]) unchanged.pb(i); sort(all(ask), [] (int x, int y) {return qry[x].w >= qry[y].w;}); sort(all(unchanged), [] (int x, int y) {return e[x].w >= e[y].w;}); int j = 0; for(int i:ask) { for(;j<sz(unchanged);j++) { int k = unchanged[j]; if(e[k].w>=qry[i].w) join(e[k].u, e[k].v); else break; } int prvSize = sz(rollback); for(int k:careEdge[i]) { //printf("%d | %d %d\n", k, e[k].u, e[k].v); join(e[k].u, e[k].v); } ans[i] = -dsu[root(qry[i].u)]; goback(prvSize); } for(int i:update) changedEdge[qry[i].u] = 0; } for(int i=1;i<=q;i++) { if(qry[i].t == 2) printf("%d\n", ans[i]); } return 0; }

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         scanf("%d%d%d", &u, &v, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
bridges.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         scanf("%d%d%d", &t, &u, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...