Submission #609669

#	Time	Username	Problem	Language	Result	Execution time	Memory
609669		gagik_2007	Jail (JOI22_jail)	C++17	77 / 100	5052 ms	557692 KiB

jail

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

typedef long long ll;
typedef long double ld;
typedef ll itn;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 32768;
const ll N = 100007;
ll n, m, k;
vector<int>g[120007];
ll s[120007];
ll f[120007];
queue<int>q;

struct Point {
    int ind, val, tp;
    Point(int i, int vl, int tip) {
        ind = i;
        val = vl;
        tp = tip;
    }
    bool operator<(Point other)const {
        if (val < other.val)return true;
        else if (val > other.val)return false;
        else return tp < other.tp;
    }
};

vector<Point>d;
int tin[120007];
int tout[120007];
int timer = 0;
int up[120007][20];
int lg;

void dfs(int v, int par) {
    tin[v] = timer++;
    up[v][0] = par;
    for (int i = 0; i < g[v].size(); i++) {
        int to = g[v][i];
        if (to != par) {
            dfs(to, v);
        }
    }
    tout[v] = timer++;
}

void calc() {
    for (int i = 1; i <= lg; i++) {
        for (int v = 1; v <= n; v++) {
            up[v][i] = up[up[v][i - 1]][i - 1];
        }
    }
}

bool pap(int v, int u) {
    return tin[v]<=tin[u] && tout[v]>=tout[u];
}

int lca(int v, int u) {
    if (pap(v, u)) {
        return v;
    }
    if (pap(u, v)) {
        return u;
    }
    for (int i = lg; i >= 0; i--) {
        if (!pap(up[u][i], v)) {
            u = up[u][i];
        }
    }
    //cout << "lca of " << v << " and " << u << " is: " << up[u][0] << endl;
    return up[u][0];
}

bool votitak(int v, int u, int c) {
    return pap(lca(v, u), c) && (pap(c, u) || pap(c, v));
}

vector<int> champa(int v, int u){
    int papa = lca(v,u);
    vector<int>ans;
    while(v!=papa){
        ans.push_back(v);
        v=up[v][0];
    }
    while(u!=papa){
        ans.push_back(u);
        u=up[u][0];
    }
    ans.push_back(papa);
    return ans;
}

vector<int>g2[120007];
int color[120007];
int prc[120007];
int skz[120007];

bool is_cyclic(int v){
    color[v]=1;
    bool ans=false;
    for(int i=0;i<g2[v].size();i++){
        int to=g2[v][i];
        if(color[to]==1)ans=true;
        if(color[to]==0){
            if(is_cyclic(to)){
                ans=true;
            }
        }
    }
    color[v]=2;
    return ans;
}

void sax_jnjxel(){
    timer = 0;
    fill(tin, tin + 120007, 0);
    fill(tout, tout + 120007, 0);
    fill(color,color+120007,0);
    fill(prc,prc+120007,0);
    fill(skz,skz+120007,0);
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        g2[i].clear();
    }
}

void solve(){
    cin >> n;
    lg = ceil(log2(n));
    bool ent1 = true;
    for (int i = 0; i < n - 1; i++) {
        ll x, y;
        cin >> x >> y;
        if (x != i + 1 || y != i + 2) {
            ent1 = false;
        }
        g[x].push_back(y);
        g[y].push_back(x);
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> s[i] >> f[i];
    }
    //ent1 = false;
    if (ent1) {
        for (int i = 1; i <= m; i++) {
            Point x(i, s[i], 1), y(i, f[i], -1);
            d.push_back(x);
            d.push_back(y);
        }
        sort(d.begin(), d.end());
        bool aj = (d[0].tp == 1);
        bool ok = true;
        for (auto x : d) {
            //cout << x.ind << " " << x.tp << "  ";
            if (aj) {
                if (x.tp == 1) {
                    q.push(x.ind);
                }
                else {
                    if (q.empty()) {
                        aj = false;
                        q.push(x.ind);
                    }
                    else {
                        if (x.ind != q.front()) {
                            ok = false;
                            break;
                        }
                        else {
                            q.pop();
                        }
                    }
                }
            }
            else {
                if (x.tp == -1) {
                    q.push(x.ind);
                }
                else {
                    if (q.empty()) {
                        aj = true;
                        q.push(x.ind);
                    }
                    else {
                        if (x.ind != q.front()) {
                            ok = false;
                            break;
                        }
                        else {
                            q.pop();
                        }
                    }
                }
            }
        }
        cout << (ok ? "Yes" : "No") << endl;
        while (!q.empty()) {
            q.pop();
        }
        d.clear();
        for (int i = 1; i <= n; i++) {
            g[i].clear();
        }
    }
    else if(m<=500){
        dfs(1, 1);
        calc();
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++){
                if(j!=i){
                    bool skizb = votitak(f[i],s[i],f[j]);
                    bool verj = votitak(f[i],s[i],s[j]);
                    if(skizb&&verj){
                        //cout<<i<<" "<<j<<endl;
                        cout<<"No"<<endl;
                        sax_jnjxel();
                        return;
                    }
                    if(skizb){
                        g2[i].push_back(j);
                    }
                    else if(verj){
                        g2[j].push_back(i);
                    }
                }
            }
        }
        bool res=false;
        for(int i=1;i<=m;i++){
            if(color[i]==0){
                if(is_cyclic(i)){
                    res=true;
                    break;
                }
            }
        }
        if(!res){
            cout<<"Yes"<<endl;
        }
        else cout<<"No"<<endl;
        sax_jnjxel();
    }
    else{
        dfs(1, 1);
        calc();
        for(int i=1;i<=m;i++){
            prc[s[i]]=i;
            skz[f[i]]=i;
        }
        for(int i=1;i<=m;i++){
            vector<int>c=champa(f[i],s[i]);
            for(auto x:c){
                if(prc[x]!=0&&prc[x]!=i){
                    g2[prc[x]].push_back(i);
                }
                if(skz[x]!=0&&skz[x]!=i){
                    g2[i].push_back(skz[x]);
                }
            }
        }
        bool res=false;
        for(int i=1;i<=m;i++){
            if(color[i]==0){
                if(is_cyclic(i)){
                    res=true;
                    break;
                }
            }
        }
        if(!res){
            cout<<"Yes"<<endl;
        }
        else cout<<"No"<<endl;
        sax_jnjxel();
    }
}

int main() {
    cin >> ttt;
    while (ttt--) {
        solve();
    }
}

/*
4
7
1 2
1 3
2 4
2 5
3 6
3 7
2
4 3
2 7
7
1 2
1 3
2 4
2 5
3 6
3 7
2
4 3
7 2
7
1 2
1 3
2 4
2 5
3 6
3 7
2
4 7
3 2
7
1 2
1 3
2 4
2 5
3 6
3 7
2
4 7
3 4
*/

Compilation message (stderr)

jail.cpp: In function 'void dfs(int, int)':
jail.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i < g[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
jail.cpp: In function 'bool is_cyclic(int)':
jail.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i=0;i<g2[v].size();i++){
      |                 ~^~~~~~~~~~~~~

• 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