Submission #919681

#TimeUsernameProblemLanguageResultExecution timeMemory
919681NeltICC (CEOI16_icc)C++17
0 / 100
3 ms604 KiB
#include "icc.h" #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,avx2,fma,popcnt") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> /* DEFINES */ #define S second #define F first #define ll long long #define ull unsigned long long #define ld long double #define npos ULLONG_MAX #define INF LLONG_MAX #define vv(a) vector<a> #define ss(a) set<a> #define pp(a, b) pair<a, b> #define mm(a, b) map<a, b> #define qq(a) queue<a> #define pq(a) priority_queue<a> #define ump(a, b) unordered_map<a, b> #define ANDROID \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); #define allc(a) begin(a), end(a) #define all(a) a, a + sizeof(a) / sizeof(a[0]) #define elif else if #define endl "\n" #define pb push_back #define ins insert #define logi __lg #define sqrt sqrtl #define mpr make_pair using namespace std; using namespace __cxx11; using namespace __gnu_pbds; typedef char chr; typedef basic_string<chr> str; template <typename T, typename key = less<T>> using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); struct Dsu { ll n, ans; vv(ll) dsu; vv(vv(ll)) s; Dsu(ll sz = 1) { n = sz; ans = n; dsu.resize(n + 1, 0); s.resize(n + 1); init(); } void init() { for (ll i = 1; i <= n; i++) dsu[i] = -1, s[i] = {i}; } bool Union(ll x, ll y) { x = repr(x), y = repr(y); if (x == y) return false; if (dsu[x] < dsu[y]) swap(x, y); ans--; for (ll i : s[x]) s[y].pb(i); s[x].clear(); dsu[y] += dsu[x]; dsu[x] = y; return true; } ll repr(ll x) { if (dsu[x] < 0) return x; return dsu[x] = repr(dsu[x]); } ll query() { return ans; } ll size(ll x) { return -dsu[repr(x)]; } }; void run(int n) { Dsu dsu(n); ll p[n]; iota(all(p), 1); for (ll cnt = 1; cnt < n; cnt++) { vv(int) v[2]; shuffle(all(p), rng); for (ll bit = 0; bit <= logi(n); bit++) { v[0].clear(), v[1].clear(); for (ll i : p) if (dsu.repr(i) == i) for (ll j : dsu.s[i]) v[j >> bit & 1].pb(j); if (query(v[0].size(), v[1].size(), data(v[0]), data(v[1]))) break; } ll l = 1, r = v[1].size(), a, b; while (l <= r) { ll mid = (l + r) >> 1; if (query(v[0].size(), mid, data(v[0]), data(v[1]))) a = v[1][mid - 1], r = mid - 1; else l = mid + 1; } l = 1, r = v[0].size(); while (l <= r) { ll mid = (l + r) >> 1; if (query(mid, v[1].size(), data(v[0]), data(v[1]))) b = v[0][mid - 1], r = mid - 1; else l = mid + 1; } dsu.Union(a, b); setRoad(a, b); } }

Compilation message (stderr)

icc.cpp: In function 'void run(int)':
icc.cpp:80:18: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |         if (dsu[x] < 0)
      |                  ^
icc.cpp:113:39: note: 'b' was declared here
  113 |         ll l = 1, r = v[1].size(), a, b;
      |                                       ^
icc.cpp:80:18: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |         if (dsu[x] < 0)
      |                  ^
icc.cpp:113:36: note: 'a' was declared here
  113 |         ll l = 1, r = v[1].size(), a, b;
      |                                    ^
#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...