| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 919681 |
2024-02-01T11:59:47 Z |
Nelt |
ICC (CEOI16_icc) |
C++17 |
|
3 ms |
604 KB |
#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
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
600 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
