oj.uz

Submission #609660

# Submission time Handle Problem Language Result Execution time Memory
609660 2022-07-27T18:56:53 Z gagik_2007 Jail (JOI22_jail) C++17
5 / 100
 256 ms 14780 KB 
#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<=1){
        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[x].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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 3 ms 5844 KB Output is correct
3 Correct 3 ms 5844 KB Output is correct
4 Correct 22 ms 5844 KB Output is correct
5 Correct 45 ms 5972 KB Output is correct
6 Correct 5 ms 5972 KB Output is correct
7 Correct 6 ms 5844 KB Output is correct
8 Correct 6 ms 5972 KB Output is correct
9 Correct 99 ms 6144 KB Output is correct
10 Correct 74 ms 9664 KB Output is correct
11 Correct 34 ms 5848 KB Output is correct
12 Correct 56 ms 5972 KB Output is correct
13 Correct 118 ms 12092 KB Output is correct
14 Correct 116 ms 12128 KB Output is correct
15 Correct 109 ms 12104 KB Output is correct
16 Correct 256 ms 14780 KB Output is correct
17 Correct 183 ms 12300 KB Output is correct
18 Correct 143 ms 14716 KB Output is correct
19 Correct 124 ms 12200 KB Output is correct
20 Correct 118 ms 12236 KB Output is correct
21 Correct 148 ms 12216 KB Output is correct
22 Correct 107 ms 12268 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 3 ms 5844 KB Output is correct
3 Correct 5 ms 5972 KB Output is correct
4 Incorrect 6 ms 8276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 3 ms 5844 KB Output is correct
3 Correct 5 ms 5972 KB Output is correct
4 Incorrect 6 ms 8276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 3 ms 5844 KB Output is correct
3 Correct 5 ms 5972 KB Output is correct
4 Incorrect 6 ms 8276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 3 ms 5844 KB Output is correct
3 Correct 5 ms 5972 KB Output is correct
4 Incorrect 6 ms 8276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 4 ms 8276 KB Output is correct
3 Correct 3 ms 5844 KB Output is correct
4 Correct 3 ms 5844 KB Output is correct
5 Correct 13 ms 5844 KB Output is correct
6 Incorrect 6 ms 8276 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 3 ms 5844 KB Output is correct
3 Correct 3 ms 5844 KB Output is correct
4 Correct 22 ms 5844 KB Output is correct
5 Correct 45 ms 5972 KB Output is correct
6 Correct 5 ms 5972 KB Output is correct
7 Correct 6 ms 5844 KB Output is correct
8 Correct 6 ms 5972 KB Output is correct
9 Correct 99 ms 6144 KB Output is correct
10 Correct 74 ms 9664 KB Output is correct
11 Correct 34 ms 5848 KB Output is correct
12 Correct 56 ms 5972 KB Output is correct
13 Correct 118 ms 12092 KB Output is correct
14 Correct 116 ms 12128 KB Output is correct
15 Correct 109 ms 12104 KB Output is correct
16 Correct 256 ms 14780 KB Output is correct
17 Correct 183 ms 12300 KB Output is correct
18 Correct 143 ms 14716 KB Output is correct
19 Correct 124 ms 12200 KB Output is correct
20 Correct 118 ms 12236 KB Output is correct
21 Correct 148 ms 12216 KB Output is correct
22 Correct 107 ms 12268 KB Output is correct
23 Correct 3 ms 5844 KB Output is correct
24 Correct 3 ms 5844 KB Output is correct
25 Correct 5 ms 5972 KB Output is correct
26 Incorrect 6 ms 8276 KB Output isn't correct
27 Halted 0 ms 0 KB -