| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 631542 |
2022-08-18T08:20:27 Z |
LittleCube |
Jail (JOI22_jail) |
C++14 |
|
0 ms |
0 KB |
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
int T, N, M, pre[1200005], dis[1200005], s[1200005], e[1200005], deg[8000005], fr[1200005], to[1200005], Hhead[1200005], Hsz[1200005], Hpos[1200005], idx, ts;
pii io[1200005];
vector<int> E[1200005], topo[8000005];
struct HLD
{
// 0: start, 1: end
int root[1600005][2] = {};
int l[8000005] = {};
int r[8000005] = {};
void init()
{
for(int i = 1; i <= 6 * N; i++)
l[i] = r[i] = 0;
for(int i = 1; i <= N; i++)
root[i][0] = root[i][1] = 0;
for(int i = 1; i <= N; i++)
if(Hsz[i])
{
// cout << "HLD: " << i << '\n';
root[i][0] = ++idx;
segInit(idx, 1, Hsz[i], 0);
root[i][1] = ++idx;
segInit(idx, 1, Hsz[i], 1);
}
}
void segInit(int i, int L, int R, int type)
{
// cout << i << ' ' << L << ' ' << R << ' ' << type << '\n';
if(L == R)
return;
int mid = (L + R) / 2;
l[i] = ++idx;
segInit(l[i], L, mid, type);
r[i] = ++idx;
segInit(r[i], mid + 1, R, type);
if(type == 0)
{
topo[l[i]].emplace_back(i);
topo[r[i]].emplace_back(i);
}
else
{
topo[i].emplace_back(l[i]);
topo[i].emplace_back(r[i]);
}
}
void segInsert(int i, int L, int R, int pos, int j, int type)
{
if(L == R)
{
// cout << i << ' ' << j << ' ' << type << '\n';
if(type == 0)
topo[j].emplace_back(i);
else
topo[i].emplace_back(j);
}
else
{
int mid = (L + R) / 2;
if(pos <= mid)
segInsert(l[i], L, mid, pos, j, type);
else
segInsert(r[i], mid + 1, R, pos, j, type);
}
}
void segEdge(int r1, int r2, int L, int R, int j, int mL, int mR)
{
if(mL <= L && R <= mR)
{
topo[r1].emplace_back(j);
topo[j].emplace_back(r2);
}
else if(R < mL || mR < L)
return;
else
{
int mid = (L + R) / 2;
segEdge(l[r1], l[r2], L, mid, j, mL, mR);
segEdge(r[r1], r[r2], mid + 1, R, j, mL, mR);
}
}
}hld;
void dfs(int u)
{
io[u].F = ++ts;
for(int v : E[u])
if(pre[u] != v)
{
pre[v] = u;
dis[v] = dis[u] + 1;
dfs(v);
}
io[u].S = ts;
}
void decompose(int u, int h)
{
int deep = 0;
Hhead[u] = h;
for(int v : E[u])
if(pre[u] != v)
{
if(dis[v] > dis[deep])
deep = v;
}
for(int v : E[u])
if(pre[u] != v)
{
Hpos[v] = (v == deep ? Hpos[u] + 1 : 1);
decompose(v, (v == deep ? h : v));
}
}
void addedge(int pos, int i)
{
if(s[pos] && s[pos] != i)
topo[s[pos]].emplace_back(i);
if(e[pos] && e[pos] != i)
topo[i].emplace_back(e[pos]);
}
bool isSubtree(int r, int c)
{
return io[r].F <= io[c].F && io[c].S <= io[r].S;
}
void solve()
{
ts = 0, idx = 0;
cin >> N;
for(int i = 1; i <= N; i++)
{
pre[i] = dis[i] = s[i] = e[i] = Hhead[i] = Hsz[i] = Hpos[i] = 0;
E[i].clear();
}
for(int i = 1; i < N; i++)
{
int u, v;
cin >> u >> v;
E[u].emplace_back(v);
E[v].emplace_back(u);
}
dfs(1);
Hpos[1] = 1;
decompose(1, 1);
cin >> M;
idx = M;
for(int i = 1; i <= 6 * N; i++)
{
deg[i] = 0;
topo[i].clear();
}
for(int i = 1; i <= N; i++)
Hsz[Hhead[i]] = max(Hsz[Hhead[i]], Hpos[i]);
hld.init();
for(int i = 1; i <= M; i++)
{
cin >> fr[i] >> to[i];
s[fr[i]] = i;
e[to[i]] = i;
hld.segInsert(hld.root[Hhead[fr[i]]][0], 1, Hsz[Hhead[fr[i]]], Hpos[fr[i]], i, 0);
hld.segInsert(hld.root[Hhead[to[i]]][1], 1, Hsz[Hhead[to[i]]], Hpos[to[i]], i, 1);
}
for(int i = 1; i <= M; i++)
{
int u = fr[i], v = to[i];
addedge(u, i);
addedge(v, i);
if(pre[u] == v || pre[v] == u) continue;
int cancelUp = 1;
if(isSubtree(u, v))
v = pre[v];
else if(isSubtree(v, u))
u = pre[u];
else
u = pre[u], v = pre[v], cancelUp = 0;
while(Hhead[u] != Hhead[v])
{
if(dis[Hhead[u]] < dis[Hhead[v]])
swap(u, v);
hld.segEdge(hld.root[Hhead[u]][0], hld.root[Hhead[u]][1], 1, Hsz[Hhead[u]], i, 1, Hpos[u], 0);
u = pre[Hhead[u]];
}
if(dis[u] > dis[v]) swap(u, v);
hld.segEdge(hld.root[Hhead[u]][0], hld.root[Hhead[u]][1], 1, Hsz[Hhead[u]], i, Hpos[u] + cancelUp, Hpos[v], 0);
}
for(int i = 1; i <= idx; i++)
for(int j : topo[i])
{
// cout << i << "->" << j << '\n';
deg[j]++;
}
queue<int> q;
for(int i = 1; i <= idx; i++)
if(deg[i] == 0)
q.emplace(i);
for(int t = 1; t <= idx; t++)
{
if(q.empty())
{
cout << "No\n";
return;
}
int u = q.front();
q.pop();
for(int v : topo[u])
{
deg[v]--;
if(deg[v] == 0)
q.emplace(v);
}
}
cout << "Yes\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> T;
while(T--)
{
solve();
}
}
Compilation message
jail.cpp: In function 'void solve()':
jail.cpp:207:96: error: no matching function for call to 'HLD::segEdge(int&, int&, int, int&, int&, int, int&, int)'
207 | hld.segEdge(hld.root[Hhead[u]][0], hld.root[Hhead[u]][1], 1, Hsz[Hhead[u]], i, 1, Hpos[u], 0);
| ^
jail.cpp:81:7: note: candidate: 'void HLD::segEdge(int, int, int, int, int, int, int)'
81 | void segEdge(int r1, int r2, int L, int R, int j, int mL, int mR)
| ^~~~~~~
jail.cpp:81:7: note: candidate expects 7 arguments, 8 provided
jail.cpp:213:112: error: no matching function for call to 'HLD::segEdge(int&, int&, int, int&, int&, int, int&, int)'
213 | hld.segEdge(hld.root[Hhead[u]][0], hld.root[Hhead[u]][1], 1, Hsz[Hhead[u]], i, Hpos[u] + cancelUp, Hpos[v], 0);
| ^
jail.cpp:81:7: note: candidate: 'void HLD::segEdge(int, int, int, int, int, int, int)'
81 | void segEdge(int r1, int r2, int L, int R, int j, int mL, int mR)
| ^~~~~~~
jail.cpp:81:7: note: candidate expects 7 arguments, 8 provided
