Submission #604147

#	Time	Username	Problem	Language	Result	Execution time	Memory
604147		SamAnd	Jail (JOI22_jail)	C++17	0 / 100	37 ms	46208 KiB

jail

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 150005;

int n;
vector<int> g[N];

int p0[N];
int q[N];
void dfs0(int x, int p)
{
    p0[x] = p;
    q[x] = 1;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        dfs0(h, x);
        q[x] += q[h];
    }

    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
        {
            swap(g[x][i], g[x].back());
            g[x].pop_back();
            break;
        }
    }
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (q[h] > q[g[x][0]])
            swap(g[x][i], g[x][0]);
    }
}

int tin[N], tout[N], ti;
int f[N];
void dfs1(int x)
{
    tin[x] = ++ti;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (i == 0)
        {
            f[h] = f[x];
            dfs1(h);
        }
        else
        {
            f[h] = h;
            dfs1(h);
        }
    }
    tout[x] = ti;
}

bool c[N];

int t[N * 4];
set<int> st[N * 4];
void ubd(int tl, int tr, int x, int y, int pos)
{
    if (tl == tr)
    {
        if (y > 0)
        {
            st[pos].insert(y);
        }
        else
        {
            y *= -1;
            assert(st[pos].find(y) != st[pos].end());
            st[pos].erase(y);
        }
        if (st[pos].empty())
            t[pos] = 0;
        else
            t[pos] = *st[pos].begin();
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, pos * 2);
    else
        ubd(m + 1, tr, x, y, pos * 2 + 1);
    t[pos] = max(t[pos * 2], t[pos * 2 + 1]);
}

int qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
        return t[pos];
    int m = (tl + tr) / 2;
    return max(qry(tl, m, l, min(m, r), pos * 2),
               qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

int qryy(int x, int y)
{
    while (f[x] != f[y])
    {
        if (tin[f[x]] < tin[f[y]])
            swap(x, y);
        int ans = qry(1, n, tin[f[x]], tin[x], 1);
        if (ans)
            return ans;
        x = p0[f[x]];
    }
    if (tin[x] < tin[y])
        swap(x, y);
    return qry(1, n, tin[y], tin[x], 1);
}

vector<int> t2[N * 4];
void ubd2(int tl, int tr, int l, int r, int y, int pos)
{
    if (l > r)
        return;
    if (tl == l && tr == r)
    {
        if (y > 0)
            t2[pos].push_back(y);
        else
        {
            assert(false);
            y *= -1;
            assert(!t2[pos].empty());
            assert(t2[pos].back() == y);
            t2[pos].pop_back();
        }
        return;
    }
    int m = (tl + tr) / 2;
    ubd2(tl, m, l, min(m, r), y, pos * 2);
    ubd2(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1);
}

void ubdd2(int x, int y, int z)
{
    while (f[x] != f[y])
    {
        if (tin[f[x]] < tin[f[y]])
            swap(x, y);
        ubd2(1, n, tin[f[x]], tin[x], z, 1);
        x = p0[f[x]];
    }
    if (tin[x] < tin[y])
        swap(x, y);
    return ubd2(1, n, tin[y], tin[x], z, 1);
}

int qry2(int tl, int tr, int x, int pos)
{
    while (!t2[pos].empty() && c[t2[pos].back()])
        t2[pos].pop_back();
    if (tl == tr)
    {
        if (!t2[pos].empty())
            return t2[pos].back();
        return 0;
    }
    int m = (tl + tr) / 2;
    if (!t2[pos].empty())
    {
        if (x <= m)
            return max(t2[pos].back(), qry2(tl, m, x, pos * 2));
        return max(t2[pos].back(), qry2(m + 1, tr, x, pos * 2 + 1));
    }
    if (x <= m)
        return qry2(tl, m, x, pos * 2);
    return qry2(m + 1, tr, x, pos * 2 + 1);
}

int m;
pair<int, int> b[N];

vector<int> v;
void dfs(int i)
{
    c[i] = true;
    ubd(1, n, tin[b[i].fi], -i, 1);
    while (1)
    {
        int h = qryy(b[i].fi, b[i].se);
        if (!h)
            break;
        dfs(h);
    }
    while (1)
    {
        int h = qry2(1, n, tin[b[i].se], 1);
        if (!h)
            break;
        dfs(h);
    }
    v.push_back(i);
}

int s[N * 4];
void ubds(int tl, int tr, int x, int y, int pos)
{
    if (tl == tr)
    {
        s[pos] += y;
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubds(tl, m, x, y, pos * 2);
    else
        ubds(m + 1, tr, x, y, pos * 2 + 1);
    s[pos] = s[pos * 2] + s[pos * 2 + 1];
}

int qrys(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
        return s[pos];
    int m = (tl + tr) / 2;
    return (qrys(tl, m, l, min(m, r), pos * 2) +
               qrys(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

int qryys(int x, int y)
{
    int ans = 0;
    while (f[x] != f[y])
    {
        if (tin[f[x]] < tin[f[y]])
            swap(x, y);
        ans += qrys(1, n, tin[f[x]], tin[x], 1);
        x = p0[f[x]];
    }
    if (tin[x] < tin[y])
        swap(x, y);
    ans += qrys(1, n, tin[y], tin[x], 1);
    return ans;
}

void solv()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        g[i].clear();
    }
    for (int i = 0; i < n - 1; ++i)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs0(1, 1);
    ti = 0;
    f[1] = 1;
    dfs1(1);

    cin >> m;
    for (int i = 1; i <= m; ++i)
        cin >> b[i].fi >> b[i].se;

    for (int i = 1; i <= m; ++i)
        c[i] = false;
    for (int i = 1; i <= m; ++i)
    {
        ubd(1, n, tin[b[i].fi], i, 1);
        ubdd2(b[i].fi, b[i].se, i);
    }
    v.clear();
    for (int i = 1; i <= m; ++i)
    {
        if (c[i])
            continue;
        dfs(i);
    }
    for (int i = 1; i <= n; ++i)
        qry2(1, n, i, 1);

    for (int i = 1; i <= m; ++i)
        ubds(1, n, tin[b[i].fi], 1, 1);
    for (int ii = 0; ii < sz(v); ++ii)
    {
        int i = v[ii];
        ubds(1, n, tin[b[i].fi], -1, 1);
        if (qryys(b[i].fi, b[i].se))
        {
            for (int jj = ii + 1; jj < sz(v); ++jj)
            {
                int i = v[jj];
                ubds(1, n, tin[b[i].fi], -1, 1);
            }
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'void dfs0(int, int)':
jail.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
jail.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
jail.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
jail.cpp: In function 'void dfs1(int)':
jail.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23