Submission #584871

#	Time	Username	Problem	Language	Result	Execution time	Memory
584871		CodePlatina	Jail (JOI22_jail)	C++17	100 / 100	555 ms	97668 KiB

jail

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
const int INF = (int)1e9 + 7;

using namespace std;

int n, m;
vector<int> gph[121212];
vector<int> ord[1212121];
int par[121212];
int sub[121212];
int sz[1212121];
int in[121212];
int out[121212];
int up[121212];
int st[121212];
int ed[121212];
int cnt;

void dfs(int x, int p)
{
    sub[x] = 1;
    par[x] = p;
    vector<int> tmp;
    for(auto y : gph[x]) if(y != p) dfs(y, x), sub[x] += sub[y], tmp.push_back(y);
    gph[x] = tmp;
}

void dfs2(int x, int p)
{
    in[x] = cnt++;
    up[x] = (gph[p][0] == x ? up[p] : x);
    for(auto &y : gph[x]) if(sub[y] > sub[gph[x][0]]) swap(y, gph[x][0]);
    for(auto y : gph[x]) dfs2(y, x);
    out[x] = cnt;
}

void init()
{
    for(int i = 0; i < n; ++i)
    {
        if(st[i] != -1) ord[st[i]].push_back(i + n + m);
        if(ed[i] != -1) ord[i + 3 * n + m].push_back(ed[i]);
    }
    for(int i = n - 1; i >= 1; --i)
    {
        ord[2 * i + m].push_back(i + m);
        ord[2 * i + 1 + m].push_back(i + m);
        ord[i + 2 * n + m].push_back(2 * i + 2 * n + m);
        ord[i + 2 * n + m].push_back(2 * i + 1 + 2 * n + m);
    }
}

void upd(int l, int r, int i)
{
    for(int x = l + n, y = r + n; x != y; x >>= 1, y >>= 1)
    {
        if(x & 1)
        {
            ord[x + m].push_back(i);
            ord[i].push_back(x + 2 * n + m);
            ++x;
        }
        if(y & 1)
        {
            --y;
            ord[y + m].push_back(i);
            ord[i].push_back(y + 2 * n + m);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while(T--)
    {
        cin >> n;
        for(int i = 0; i < n; ++i) gph[i].clear(), par[i] = in[i] = out[i] = sub[i] = up[i] = 0, st[i] = ed[i] = -1;
        cnt = 0;

        for(int i = 1; i < n; ++i)
        {
            int x, y; cin >> x >> y; --x; --y;
            gph[x].push_back(y);
            gph[y].push_back(x);
        }
        dfs(0, 0);
        dfs2(0, 0);

        cin >> m;
        for(int i = 0; i < m + 4 * n; ++i) ord[i].clear(), ord[i].shrink_to_fit(), sz[i] = 0;
        pii qry[m];
        for(auto &[x, y] : qry) cin >> x >> y, --x, --y;

        for(int i = 0; i < m; ++i) st[in[qry[i].ff]] = i, ed[in[qry[i].ss]] = i;
        init();

        for(int i = 0; i < m; ++i)
        {
            auto [x, y] = qry[i];
            if(st[in[y]] != -1) ord[st[in[y]]].push_back(i);
            if(ed[in[x]] != -1) ord[i].push_back(ed[in[x]]);
            int xx = 0, yy = 0;
            while(up[x] != up[y])
            {
                if(in[x] < in[y]) swap(x, y), swap(xx, yy);
                upd(in[up[x]], in[x] + xx, i);
                xx = 1;
                x = par[up[x]];
            }
            if(in[x] > in[y]) swap(x, y), swap(xx, yy);
            upd(in[x] + 1 - xx, in[y] + yy, i);
        }

        vector<int> V;
        for(int i = 0; i < m + 4 * n; ++i) for(auto x : ord[i]) ++sz[x];
        for(int i = 0; i < m + 4 * n; ++i) if(!sz[i]) V.push_back(i);
        int c = 0;
        while(V.size())
        {
            int x = V.back(); V.pop_back(); ++c;
            for(auto y : ord[x]) if(!--sz[y]) V.push_back(y);
        }

        cout << (c == m + 4 * n ? "Yes" : "No") << '\n';
    }
}

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