제출 #915683

#제출 시각아이디문제언어결과실행 시간메모리
915683coding_monk3다리 (APIO19_bridges)C++17
100 / 100
1810 ms9536 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; // Miscellanous #define gc getchar_unlocked #define ll long long #define ull unsigned long long #define si(x) scanf("%d",&x) #define si2(x,y) scanf("%d %d",&x,&y) #define sl(x) scanf("%lld",&x) #define sl2(x,y) scanf("%lld %lld",&x,&y) #define sstr(s) cin >> s #define pi(x) printf("%d\n",x) #define pi2(x,y) printf("%d %d\n",x,y) #define pl(x) printf("%lld\n",x) #define pl2(x,y) printf("%lld %lld\n",x,y) #define ps(s) cout << s << endl #define py printf("YES\n") #define pn printf("NO\n") #define pnl printf("\n") #define pb push_back #define ff first #define ss second #define sz(v) (int)v.size() #define all(v) v.begin(),v.end() #define sortv(v) sort(all(v)) #define revsort(v) sort(v.rbegin(),v.rend()) #define reverse(v) reverse(all(v)) #define alla(arr,sz) arr,arr+sz #define sorta(arr,sz) sort(alla(arr,sz)) #define reversea(arr,sz) reverse(alla(arr,sz)) #define cta(x,v) count(alla(arr,sz),x) #define ct(x,v) count(all(v),x) #define cto(v) count_if(all(v),[] (int a) {return a%2 == 1;}) #define cte(v) count_if(all(v),[] (int a) {return a%2 == 0;}) #define MAX(a,b) a = max(a,b) #define MIN(a,b) a = min(a,b) #define clr(x) memset(x, 0, sizeof(x)) // Loops #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i)) #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i)) #define forc(c,s,e) for (char (c)=(s);(c)<=(e);++(c)) #define forr(i,s,e) for (int (i)=(s);(i)>=(e);--(i)) #define foreach(val,cont) for (auto &(val) : (cont)) #define rep(i,n) loop(i,0,n) #define repn(i,n) loope(i,1,n) // Constants #define PI 3.1415926535897932384626 #define sqr(x) ((x) * 1ll * (x)) const int mod = 1000000007; // Containers typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vi> vvi; typedef vector<vl> vvl; typedef pair<string,string> pss; typedef map<int, int> mii; // Input Output struct edge { int u,v,wt; bool operator<(const edge &x) const {return wt < x.wt;} void read() {scanf("%d %d %d" , &u, &v, &wt);} }; #define takei(a) int a; si(a) #define takei2(a,b) int a,b; si2(a,b) #define takel(a) ll a; sl(a) #define takel2(a,b) ll a,b; sl2(a,b) #define takearri0(n,a) vi a(n); rep(i,n) si(a[i]) #define takearri1(n,a) vi a(n+1); a[0] = 0; repn(i,n) si(a[i]) #define takearrl0(n,a) vl a(n); rep(i,n) sl(a[i]) #define takearrl1(n,a) vl a(n+1); a[0] = 0ll; repn(i,n) sl(a[i]) // Debug void _print(int t) {cerr << t;} void _print(ll t) {cerr << t;} void _print(string t) {cerr << t;} void _print(char t) {cerr << t;} void _print(double t) {cerr << t;} void _print(ull t) {cerr << t;} void _print(edge t) {cerr << "[ " << '{' << t.u << ',' << t.v << "} " << t.wt << " ]";} template <class T, class V> void _print(pair <T, V> p); template <class T> void _print(vector <T> v); template <class T> void _print(unordered_set <T> v); template <class T> void _print(unordered_multiset <T> v); template <class T> void _print(set <T> v); template <class T> void _print(multiset <T> v); template <class T, class V> void _print(unordered_map <T, V> v); template <class T, class V> void _print(unordered_multimap <T, V> v); template <class T, class V> void _print(map <T, V> v); template <class T, class V> void _print(multimap <T, V> v); template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";} template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T> void _print(unordered_set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T> void _print(unordered_multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T, class V> void _print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T, class V> void _print(unordered_multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";} template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";} #ifndef ONLINE_JUDGE #define deb(x) cerr << #x << " = "; _print(x); cerr << endl; #else #define deb(x) #endif inline string inttostr(ll a){ char x[100]; sprintf(x,"%lld",a); string s = x; return s; } inline ll strtoint(string a){ char x[100]; ll res; strcpy(x,a.c_str()); sscanf(x,"%lld",&res); return res; } inline string getstr(void){ char x[1000005]; scanf("%s",x); string s = x; return s; } inline string uppercase(string s){ int n = sz(s); rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A'; return s; } inline string lowercase(string s){ int n = sz(s); rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a'; return s; } // --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- // Link --> https://oj.uz/problem/view/APIO19_bridges // Explanation --> https://codeforces.com/blog/entry/67129#:~:text=It%20is%20a,DSU%20with%20rollbacks. // USACO --> https://usaco.guide/problems/apio-2019bridges/solution // Divide the queries into sqrt(q) blocks. // For each block, AT MOST sqrt(q) edges have weights changed within the block. // Sort all the queries by decreasing weight in the block, and maintain a DSU while // adding edges that are ** UNCHANGED ** within the block one-by-one in // DECREASING order of WEIGHT // And to answer each query, just simply connect the ** EXTRA CHANGED ** // *** GOOD *** edges and store the answer, and after storing the answer // *** ROLLBACK THESE CHANGES i.e. REMOVE THESE GOOD EDGES *** const int MAXN = 5e4; // DSU ---------------------------------------------------------- int size_[MAXN+1] , parent[MAXN+1]; stack<int> ops; int comp_ct; void reset(int n) { repn(i,n) size_[i] = 1; repn(i,n) parent[i] = i; comp_ct = n; while(!ops.empty()) ops.pop(); } int find_par(int node) { while(node != parent[node]) node = parent[node]; return node; } void size_union(int x, int y) { x = find_par(x); y = find_par(y); if(x == y) return; if(size_[x] > size_[y]) swap(x,y); ops.push(x); parent[x] = y; size_[y] += size_[x]; comp_ct--; } bool connected(int x, int y) { return find_par(x) == find_par(y); } void roll_back(int prev_sz) { while(sz(ops) > prev_sz) { int x = ops.top(); ops.pop(); size_[parent[x]] -= size_[x]; parent[x] = x; comp_ct++; } } // -------------------------------------------------------------- int main() { const int B_SIZE = 1000; takei2(n,m); vector<edge> edges(m+1); repn(i,m) edges[i].read(); bool change[m+1]; bool chk[m+1]; vi to_add[B_SIZE]; int answer[B_SIZE]; takei(q); for (int l = 0; l < q; l += B_SIZE) { int r = min(q - 1 , l + B_SIZE - 1); vvi cur_q(r-l+1); vi ask, upd; clr(change); rep(i,r-l+1) { takei(t); takei2(id,wt); cur_q[i] = {t,id,wt}; if(t == 1) change[id] = 1, upd.pb(i); else ask.pb(i); } rep(i,r-l+1) { int &t = cur_q[i][0] , &id = cur_q[i][1] , &wt = cur_q[i][2]; if(t == 1) edges[id].wt = wt; else { to_add[i].clear(); for(auto &j : upd) chk[cur_q[j][1]] = 0; // For every CALCULATION query collecting GOOD edges // which are getting UPDATED inside the block for(auto &j : upd) { int id2 = cur_q[j][1]; if(edges[id2].wt >= wt and !chk[id2]) to_add[i].pb(id2) , chk[id2] = 1; } } } vi unchanged; repn(i,m) if(!change[i]) unchanged.pb(i); // Sorting UNCHANGED edges in DECREASING orrder of WEIGHT sort(all(unchanged) , [&] (int i, int j) {return edges[i].wt > edges[j].wt;}); // Sorting CALCULATION queries in DECREASING orrder of WEIGHT sort(all(ask) , [&] (int i, int j) {return cur_q[i][2] > cur_q[j][2];}); // We SORTED both these so that we can use 2-POINTER method reset(n); int j = 0, s = sz(unchanged); for(auto &i : ask) { int start = cur_q[i][1]; int car_wt = cur_q[i][2]; // Adding all FAVOURABLE UNCHANGED EDGES --> 2-Pointer Method while(j < s) { edge &ed = edges[unchanged[j]]; if(ed.wt >= car_wt) size_union(ed.u,ed.v) , j++; else break; } // Adding *** GOOD *** edges from the set of CHANGING edges int prev_sz = sz(ops); for(auto &id : to_add[i]) { edge &ed = edges[id]; size_union(ed.u,ed.v); } answer[i] = size_[find_par(start)]; // Removing *** GOOD *** edges since the set of "GOOD" edges // may differ from query to query roll_back(prev_sz); } rep(i,r-l+1) if(cur_q[i][0] == 2) pi(answer[i]); } return 0; } // ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'std::string uppercase(std::string)':
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
   50 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
bridges.cpp:151:3: note: in expansion of macro 'rep'
  151 |   rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
      |   ^~~
bridges.cpp: In function 'std::string lowercase(std::string)':
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
   50 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
bridges.cpp:157:3: note: in expansion of macro 'rep'
  157 |   rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
      |   ^~~
bridges.cpp: In function 'void reset(int)':
bridges.cpp:46:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   46 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
bridges.cpp:51:19: note: in expansion of macro 'loope'
   51 | #define repn(i,n) loope(i,1,n)
      |                   ^~~~~
bridges.cpp:186:5: note: in expansion of macro 'repn'
  186 |     repn(i,n) size_[i] = 1;
      |     ^~~~
bridges.cpp:46:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   46 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
bridges.cpp:51:19: note: in expansion of macro 'loope'
   51 | #define repn(i,n) loope(i,1,n)
      |                   ^~~~~
bridges.cpp:187:5: note: in expansion of macro 'repn'
  187 |     repn(i,n) parent[i] = i;
      |     ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:46:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   46 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
bridges.cpp:51:19: note: in expansion of macro 'loope'
   51 | #define repn(i,n) loope(i,1,n)
      |                   ^~~~~
bridges.cpp:237:5: note: in expansion of macro 'repn'
  237 |     repn(i,m) edges[i].read();
      |     ^~~~
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
   50 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
bridges.cpp:251:9: note: in expansion of macro 'rep'
  251 |         rep(i,r-l+1)
      |         ^~~
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
   50 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
bridges.cpp:260:9: note: in expansion of macro 'rep'
  260 |         rep(i,r-l+1)
      |         ^~~
bridges.cpp:46:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   46 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
      |                               ^
bridges.cpp:51:19: note: in expansion of macro 'loope'
   51 | #define repn(i,n) loope(i,1,n)
      |                   ^~~~~
bridges.cpp:281:9: note: in expansion of macro 'repn'
  281 |         repn(i,m) if(!change[i]) unchanged.pb(i);
      |         ^~~~
bridges.cpp:45:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   45 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
      |                              ^
bridges.cpp:50:18: note: in expansion of macro 'loop'
   50 | #define rep(i,n) loop(i,0,n)
      |                  ^~~~
bridges.cpp:318:9: note: in expansion of macro 'rep'
  318 |         rep(i,r-l+1) if(cur_q[i][0] == 2) pi(answer[i]);
      |         ^~~
bridges.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define si2(x,y) scanf("%d %d",&x,&y)
      |                  ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:81:30: note: in expansion of macro 'si2'
   81 | #define takei2(a,b) int a,b; si2(a,b)
      |                              ^~~
bridges.cpp:235:5: note: in expansion of macro 'takei2'
  235 |     takei2(n,m);
      |     ^~~~~~
bridges.cpp:11:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define si(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
bridges.cpp:80:25: note: in expansion of macro 'si'
   80 | #define takei(a) int a; si(a)
      |                         ^~
bridges.cpp:244:5: note: in expansion of macro 'takei'
  244 |     takei(q);
      |     ^~~~~
bridges.cpp:11:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define si(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
bridges.cpp:80:25: note: in expansion of macro 'si'
   80 | #define takei(a) int a; si(a)
      |                         ^~
bridges.cpp:253:13: note: in expansion of macro 'takei'
  253 |             takei(t);
      |             ^~~~~
bridges.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define si2(x,y) scanf("%d %d",&x,&y)
      |                  ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:81:30: note: in expansion of macro 'si2'
   81 | #define takei2(a,b) int a,b; si2(a,b)
      |                              ^~~
bridges.cpp:254:13: note: in expansion of macro 'takei2'
  254 |             takei2(id,wt);
      |             ^~~~~~
bridges.cpp: In member function 'void edge::read()':
bridges.cpp:77:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     void read() {scanf("%d %d %d" , &u, &v, &wt);}
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#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...