Submission #523218

#TimeUsernameProblemLanguageResultExecution timeMemory
523218LptN21Bridges (APIO19_bridges)C++14
13 / 100
3039 ms2856 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]; int dsu[N]; int root(int u) { return (dsu[u]<0?u: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); dsu[u]+= dsu[v], dsu[v] = u; return 1; } 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); if(t == 1) e[u].w = w; if(t == 2) { memset(dsu, -1, sizeof(int)*(n+1)); for(int j=1;j<=m;j++) if(e[j].w>=w) { join(e[j].u, e[j].v); } printf("%d\n", -dsu[root(u)]); } } return 0; }

Compilation message (stderr)

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