Submission #584851

#	Time	Username	Problem	Language	Result	Execution time	Memory
584851		CodePlatina	Jail (JOI22_jail)	C++17	77 / 100	5077 ms	407804 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 dep[121212];
int up[121212];
int st[121212];
int ed[121212];
int cnt;

void dfs(int x, int p, int d)
{
    dep[x] = d;
    sub[x] = 1;
    par[x] = p;
    vector<int> tmp;
    for(auto y : gph[x]) if(y != p) dfs(y, x, d + 1), 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(y != sub[y] > sub[gph[x][0]]) swap(y, gph[x][0]);
    for(auto y : gph[x]) dfs2(y, x);
    out[x] = cnt;
}

void init(int ind, int s, int e)
{
    if(s + 1 == e)
    {
        if(st[s] != -1) ord[st[s]].push_back(2 * ind + 1 + m);
        if(ed[s] != -1) ord[2 * ind + m].push_back(ed[s]);
        return;
    }

    int mid = s + e >> 1;
    ord[2 * ind + m].push_back(4 * ind + m);
    ord[2 * ind + m].push_back(4 * ind + 2 + m);
    ord[4 * ind + 1 + m].push_back(2 * ind + 1 + m);
    ord[4 * ind + 3 + m].push_back(2 * ind + 1 + m);
    init(ind << 1, s, mid);
    init(ind << 1 | 1, mid, e);
}

void upd(int ind, int s, int e, int l, int r, int x)
{
    if(e <= l || r <= s) return;
    if(l <= s && e <= r)
    {
        ord[2 * ind + 1 + m].push_back(x);
        ord[x].push_back(2 * ind + m);
        return;
    }

    int mid = s + e >> 1;
    upd(ind << 1, s, mid, l, r, x);
    upd(ind << 1 | 1, mid, e, l, r, x);
}

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] = dep[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, 0);
        dfs2(0, 0);

        cin >> m;
        for(int i = 0; i < m + 8 * n + 10; ++i) ord[i].clear(), 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(1, 0, n);

        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(1, 0, n, 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(1, 0, n, in[x] + 1 - xx, in[y] + yy, i);
        }

        vector<int> V;
        for(int i = 0; i < m + 8 * n + 10; ++i) for(auto x : ord[i]) ++sz[x];
        for(int i = 0; i < m + 8 * n + 10; ++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 + 8 * n + 10 ? "Yes" : "No") << '\n';
    }
}

Compilation message (stderr)

jail.cpp: In function 'void dfs2(int, int)':
jail.cpp:49:42: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
   49 |     for(auto &y : gph[x]) if(y != sub[y] > sub[gph[x][0]]) swap(y, gph[x][0]);
      |                                   ~~~~~~~^~~~~~~~~~~~~~~~
jail.cpp: In function 'void init(int, int, int)':
jail.cpp:63:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int mid = s + e >> 1;
      |               ~~^~~
jail.cpp: In function 'void upd(int, int, int, int, int, int)':
jail.cpp:82:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int mid = s + e >> 1;
      |               ~~^~~

• 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: 0 / 23