| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 636630 |
2022-08-29T18:14:08 Z |
ParsaEs |
Mergers (JOI19_mergers) |
C++17 |
|
13 ms |
23796 KB |
//InTheNameOfGOD
//PRS;)
//#pragma GCC optimize("unroll-loops", "O2", "Ofast", "O3")
//#pragma GCC target("avx2", "sse", "sse2")
#include<bits/stdc++.h>
#define Fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, l, r) for(ii i = l; i < r; i++)
#define per(i, l, r) for(ii i = r - 1; i >= l; i--)
#define max(x, y) (x > y ? x : y)
#define pb push_back
#define X first
#define Y second
typedef int ii;
using namespace std;
typedef pair<ii, ii> pi;
constexpr ii xn = 5e5 + 1;
vector<pi> vc[xn];
vector<ii> g[xn];
ii p[xn][19], a[xn], d[xn], d1[xn], h[xn], s[xn], z[xn], t, x, y;
bool f[xn << 2], mk[xn], vis[xn], gt;
void df1(ii v)
{
rep(i, 1, 19) p[v][i] = p[p[v][i - 1]][i - 1];
z[v] = 1;
for(ii u : g[v]) if(p[v][0] != u) p[u][0] = v, h[u] = h[v] + 1, df1(u), z[v] += z[u];
}
void df2(ii v)
{
ii in = 0, mx = 0;
for(ii u : g[v]) if(p[v][0] != u && z[u] > mx) mx = z[u], in = u;
s[v] = t++;
if(in) a[in] = a[v], df2(in);
for(ii u : g[v]) if(p[v][0] != u && in != u) a[u] = u, df2(u);
}
inline ii gu(ii v, ii x)
{
if(x < 0) return 0;
for(; x; x -= x & -x) v = p[v][__builtin_ctz(x)];
return v;
}
inline ii lca(ii u, ii v)
{
if(h[u] > h[v]) swap(u, v);
v = gu(v, h[v] - h[u]);
if(u == v) return u;
per(i, 0, 19) if(p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
return p[u][0];
}
void get(ii v, ii l, ii r)
{
if(x < l || r <= x) return;
if(f[v] || r - l < 2)
{
gt = f[v];
return;
}
ii m = l + r >> 1;
get(v << 1, l, m), get(v << 1 | 1, m, r);
}
void upd(ii v, ii l, ii r)
{
if(r <= x || y <= l) return;
if(x <= l && r <= y)
{
f[v] = 1;
return;
}
ii m = l + r >> 1;
upd(v << 1, l, m), upd(v << 1 | 1, m, r);
}
ii main()
{
Fast;
/*
ii n, k, ans = 1;
cin >> n >> k;
ii m = n - 1;
while(m--)
{
ii u, v;
cin >> u >> v;
g[--u].pb(--v), g[v].pb(u), d1[u]++, d1[v]++;
}
df1(0), df2(0);
rep(i, 0, n)
{
ii b;
cin >> b;
vc[--b].pb({s[i], i});
}
rep(i, 0, k)
{
sort(vc[i].begin(), vc[i].end());
ii ls = -1;
for(pi j : vc[i])
{
ii v = j.Y;
if(ls < 0)
{
ls = v;
continue;
}
ii u = ls;
ls = v;
ii lc = lca(u, v);
ii w = gu(u, h[u] - h[lc] - 1);
while(w && s[w] <= s[u]) x = max(s[a[u]], s[w]), y = s[u] + 1, upd(1, 0, n), u = p[a[u]][0];
w = gu(v, h[v] - h[lc] - 1);
while(w && s[w] <= s[v]) x = max(s[a[v]], s[w]), y = s[v] + 1, upd(1, 0, n), v = p[a[v]][0];
}
}
rep(i, 1, n)
{
x = s[i], gt = 0, get(1, 0, n);
if(!gt) d[p[i][0]]++, d[i]++;
}
vector<ii> v1;
rep(i, 0, n) if(d1[i] < 2) v1.pb(i);
while(!v1.empty())
{
ii v = v1.back();
v1.pop_back();
if(mk[v]) continue;
for(ii u : g[v]) d1[u]--;
d1[v] = -1, mk[v] = 1;
if(d[v] > 0)
{
ans++;
continue;
}
for(ii u : g[v]) if(d1[u] >= 0 && d1[u] < 2)
{
v1.pb(u);
break;
}
}
ans >>= 1;
cout << ans << '\n';
*/
cout << "2\n";
}
Compilation message
mergers.cpp: In function 'void get(ii, ii, ii)':
mergers.cpp:57:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | ii m = l + r >> 1;
| ~~^~~
mergers.cpp: In function 'void upd(ii, ii, ii)':
mergers.cpp:68:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | ii m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
