Submission #584867

#TimeUsernameProblemLanguageResultExecution timeMemory
584867CodePlatinaJail (JOI22_jail)C++17
77 / 100
3804 ms1048576 KiB
#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()
{
    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] = 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 + 4 * n; ++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();

        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';
    }
}

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]);
      |                                   ~~~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...