Submission #1301739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301739		sitingfake	Jail (JOI22_jail)	C++20	5 / 100	116 ms	57400 KiB

jail

#include<bits/stdc++.h>
using namespace std;

// define

#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define ll long long
#define ii pair <int , int>
#define iii pair <int , ii>
#define se second
#define fi first
#define all(v) (v).begin() , (v).end()
#define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin())
#define bit(x,i) (((x) >> (i)) & 1LL)
#define flip(x,i) ((x) ^ (1LL << (i)))
#define ms(d,x) memset(d , x , sizeof(d))
#define exist __exist
#define ends __ends
#define visit visited
#define left __left
#define right __right
#define prev __prev
#define next __next
#define sitingfake 1
#define orz 1
//constant

const long long mod = 1e9 + 7;
const long long linf = 4557430888798830399LL;
const long long nlinf = -4485090715960753727LL;
const int LOG = 20;
const int inf = 1061109567;
const int ninf = -1044266559;
const int dx[] = {0 , -1 , 0 , 1};
const int dy[] = {-1 , 0 , 1 , 0};

template<typename T> bool maximize(T &a, const T &b)
{
    if(a < b) {a = b; return 1;}
    return 0;
}

template<typename T> bool minimize(T &a, const T &b)
{
    if(a > b) {a = b; return 1;}
    return 0;
}

void Plus(ll & a ,ll b)
{
    b %= mod;
    a += b;
    if(a < 0) a += mod;
    a %= mod;
    return;
}

void Mul(ll & a, ll b)
{
    (a *= (b % mod)) %= mod;
    return;
}

void debug()
{
    cerr << "can reach here" << endl;
}
//code
const int maxn = 120005;

vector <int> adj[maxn];
int n , m;
int s[maxn] , t[maxn];

ii val[maxn];

struct MergeSortTree
{
    vector <vector <int>> st;
    int n;
    vector <ii> val;

    void init(int Size)
    {
        n = Size;
        val.resize(n + 2);
        for(int i = 1; i <= n; i++) val[i] = {0 , 0};
        st.resize(4 * n + 2);
    }

    void build(int i , int l , int r)
    {
        if(l == r)
        {
            if(val[l].fi > val[l].se) swap(val[l].fi , val[l].se);
            if(val[l].fi != 0) st[i].push_back(val[l].fi);
            if(val[l].se != 0) st[i].push_back(val[l].se);
            return;
        }
        int mid = (r + l) >> 1;
        build(i * 2 , l , mid);
        build(i * 2 + 1 , mid + 1 , r);

        int itl = 0 , itr = 0;

        while (itl < st[i * 2].size() && itr <st[i * 2 + 1].size())
        {
            if (st[i * 2][itl] < st[i * 2 + 1][itr]) st[i].push_back(st[i * 2][itl++]);
            else st[i].push_back(st[i * 2 + 1][itr++]);
        }
        while (itl < st[i * 2].size()) st[i].push_back(st[i * 2][itl++]);
        while (itr < st[i * 2 + 1].size()) st[i].push_back(st[i * 2 + 1][itr++]);
    }

    bool get(int i , int l ,int r , int u , int v , int left , int right)
    {
        if(u > r || v < l) return 0;
        if(u <= l && r <= v)
        {
            if(st[i].empty()) return 0;
            auto it = lower_bound(all(st[i]) , left);
            if(it == st[i].end() || (*it) > right) return 0;
            return 1;
        }
        int mid = (r + l) >> 1;
        return get(i * 2 , l , mid , u , v , left , right) || get(i * 2 + 1 , mid + 1 , r , u , v , left , right);
    }
};
// HLD

int heavy[maxn] , head[maxn] , in[maxn] , out[maxn] , timer;

int depth[maxn] , par[maxn];

int dfscount(int u , int p)
{
    int cur = 1;
    int Max = 0;
    for(int v : adj[u])
    {
        if(v != p)
        {
            depth[v] = depth[u] + 1;
            par[v] = u;
            int sz = dfscount(v , u);
            if(maximize(Max , sz))
            {
                heavy[u] = v;
            }
            cur += sz;
        }
    }
    return cur;
}

void HLD(int u , int h , int p)
{
    head[u] = h;
    in[u] = ++timer;
    if(heavy[u]) HLD(heavy[u] , h , u);
    for(int v : adj[u])
    {
        if(v != p && v != heavy[u])
        {
            HLD(v , v , u);
        }
    }
    out[u] = timer;
}

int lca(int u , int v)
{
    for(;head[u] != head[v]; v = par[head[v]])
    {
        if(depth[head[u]] > depth[head[v]]) swap(u , v);
    }
    if(depth[u] > depth[v]) swap(u , v);
    return u;
}

struct Fenwick_RURQ
{
    vector <int> Mul;
    vector <int> Bit;

    int n;

    void init(int sz)
    {
        n = sz + 2;
        Mul = vector <int> (n + 2, 0);
        Bit = vector <int> (n + 2, 0);
    }

    void Update(vector<int> & B, int x ,int val)
    {
        for(;x <= n ;x += (x & -x))
        {
            B[x] += val;
        }
    }
    int Get(vector<int> &B, int x)
    {
        int val = 0;

        for(;x > 0;x -=(x & -x))
        {
            val += B[x];
        }

        return val;
    }
    int Pre(int x)
    {
        return Get(Bit , x) * x - Get(Mul , x);
    }
    int get(int l , int r)
    {
        if(l > r) return 0;
        return Pre(r) - Pre(l - 1);
    }
    void up(int l, int r, int val)
    {
        if(l > r) return;
        Update(Bit, l , val);
        Update(Bit, r + 1 ,-val);
        Update(Mul, l , val * (l - 1));
        Update(Mul, r + 1,-val * r);
        return;
    }
}Up , Down;


bool QueryUp(int u , int v)
{
    //debug();
    for(;head[u] != head[v]; v = par[head[v]])
    {
        if(depth[head[u]] > depth[head[v]]) swap(u , v);
        int val = Down.get(in[head[v]] , in[v]);
        if(val > 0) return 0;
    }
    if(depth[u] > depth[v]) swap(u , v);
    int val = Down.get(in[u] + 1 , in[v]);
    if(val > 0) return 0;
    return 1;
}

bool QueryDown(int u , int v)
{
    //debug();
    for(;head[u] != head[v]; v = par[head[v]])
    {
        if(depth[head[u]] > depth[head[v]]) swap(u , v);
        int val = Up.get(in[head[v]] , in[v]);
        if(val > 0) return 0;
    }
    if(depth[u] > depth[v]) swap(u , v);
    int val = Up.get(in[u] + 1 , in[v]);
    if(val > 0) return 0;
    return 1;
}

void UpdateUp(int u , int v)
{
    for(;head[u] != head[v]; v = par[head[v]])
    {
        if(depth[head[u]] > depth[head[v]]) swap(u , v);
        Up.up(in[head[v]] , in[v] , 1);
    }
    if(depth[u] > depth[v]) swap(u , v);
    Up.up(in[u] + 1 , in[v] , 1);
}

void UpdateDown(int u , int v)
{
    for(;head[u] != head[v]; v = par[head[v]])
    {
        if(depth[head[u]] > depth[head[v]]) swap(u , v);
        Down.up(in[head[v]] , in[v] , 1);
    }
    if(depth[u] > depth[v]) swap(u , v);
    Down.up(in[u] + 1 , in[v] , 1);
}


bool Valid(int u , int v)
{
    int lc = lca(u , v);
    if(lc == v)
    {
        if(QueryUp(u , lc))
        {
            UpdateUp(u , lc);
            return 1;
        }
        return 0;
    }
    else if(lc == u)
    {
        if(QueryDown(v , lc))
        {
            UpdateDown(v , lc);
            return 1;
        }
        return 0;
    }
    else
    {
        if(QueryUp(u , lc) && QueryDown(v , lc))
        {
            UpdateUp(u , lc);
            UpdateDown(v , lc);
            return 1;
        }
        return 0;
    }
}

bool checkPath()
{
    //debug();
    Up.init(n);
    Down.init(n);
    for(int i = 1; i <= m; i++) {
        if(!Valid(s[i] , t[i])) return 0;
    }
    //debug();
    return 1;
}

bool PathNested ()
{
    MergeSortTree st;
    st.init(n);
    for(int i = 1; i <= m; i++)
    {
        int u = s[i] , v = t[i];
        if(st.val[in[u]].fi == 0)
        {
            st.val[in[u]].fi = in[v];
        }
        else st.val[in[u]].se = in[v];
        if(st.val[in[v]].fi == 0)
        {
            st.val[in[v]].fi = in[u];
        }
        else st.val[in[v]].se = in[u];
    }
    st.build(1 , 1 , n);

    for(int i = 1; i <= m; i++)
    {
        int u = s[i] , v = t[i];

        int lc = lca(u , v);

        if(lc == u)
        {
            if(st.get(1 , 1 , n, 1 , in[lc] - 1 , in[v] , out[v]) || st.get(1 , 1 , n , out[lc] + 1 , n , in[v] , out[v]))
            {
                return 1;
            }
        }
        else if(lc == v)
        {
            if(st.get(1 , 1 , n, 1 , in[lc] - 1 , in[u] , out[u]) || st.get(1 , 1 , n , out[lc] + 1 , n , in[u] , out[u]))
            {
                return 1;
            }
        }
        else
        {
            if(st.get(1 , 1 , n , in[v] + 1 , out[v] , in[u] , out[u])) return 1;
        }
    }
    return 0;
}

void reset()
{
    for(int i = 1; i <= n; i++) adj[i].clear() , heavy[i] = par[i] = depth[i] = 0;
    timer = 0;
}
void solve(void)
{
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int u , v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> s[i] >> t[i];
    }
    //debug();
    dfscount(1 , -1);
    //debug();
    HLD(1 , 1 , -1);
    //debug();
    if(!checkPath())
    {
        cout << "No\n";
    }
    else if(PathNested())
    {
        cout << "No\n";
    }
    else
    {
        cout << "Yes\n";
    }
    reset();
}
/**
2
7
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7
4
1 2
1 3
1 4
3
2 3
3 4
4 2
**/
signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   #define task ""

   if(fopen(task".inp","r"))
   {
       freopen(task".inp","r",stdin);
       freopen(task".out","w",stdout);
   }

   int tc = 1;
   cin >> tc;
   while(tc--) solve();

//   execute;
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:450:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  450 |        freopen(task".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jail.cpp:451:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  451 |        freopen(task".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 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