oj.uz

Submission #660232

# Submission time Handle Problem Language Result Execution time Memory
660232 2022-11-21T09:15:02 Z fatemetmhr Jail (JOI22_jail) C++17
0 / 100
 16 ms 9900 KB 
// Lotfan komak


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define fi     first
#define se     second
#define pb     push_back

const int maxn5  = 2e5 + 10;
const int lg     = 20;
const int mod    = 1e9 + 7;

vector <int> adj[maxn5], ed[maxn5];
bool cy = false;
int mark[maxn5], par[lg + 1][maxn5];
int s[maxn5], t[maxn5], ti = 0, st[maxn5], ft[maxn5];
int h[maxn5];

void dfs_lca(int v){
    st[v] = ++ti;
    for(int i = 1; i < lg && par[i - 1][v] != -1; i++)
        par[i][v] = par[i - 1][par[i - 1][v]];
    for(auto u : adj[v]) if(u != par[0][v]){
        par[0][u] = v;
        h[u] = h[v] + 1;
        dfs_lca(u);
    }
    ft[v] = ti;
}

void dfs(int v){
    mark[v] = 1;
    for(auto u : ed[v]){
        if(mark[u] == 0)
            dfs(u);
        else if(mark[u] == 1)
            cy = true;
    }
    mark[v] = 2;
}

inline int lca(int a, int b){
    if(h[a] < h[b])
        swap(a, b);
    int d = h[a] - h[b];
    for(int i = 0; i < lg; i++) if((d >> i)&1)
        a = par[i][a];
    if(a == b)
        return a;
    for(int i = lg - 1; i >= 0; i--) if(par[i][a] != par[i][b]){
        a = par[i][a];
        b = par[i][b];
    }
    return par[0][a];
}

inline bool isinpath(int a, int b, int c){
    int x = lca(a, b);
    if(h[c] < h[x])
        return false;
    if(st[c] <= st[a] && ft[c] >= ft[a])
        return true;
    swap(a, b);
    return (st[c] <= st[a] && ft[c] >= ft[a]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    int tt; cin >> tt;
    while(tt--){
        int n; cin >> n;
        for(int i = 0; i < n; i++){
            adj[i].clear();
            for(int j = 0; j < lg; j++)
                par[j][i] = -1;
        }
        for(int i = 0; i < n - 1; i++){
            int a, b; cin >> a >> b;
            a--; b--;
            adj[a].pb(b);
            adj[b].pb(a);
        }
        h[0] = 0;
        ti = 0;
        dfs_lca(0);
        int m; cin >> m;
        cy = false;
        for(int i = 0; i < m; i++){
            ed[i].clear();
            mark[i] = 0;
        }
        for(int i = 0; i < m; i++){
            cin >> s[i] >> t[i];
            s[i]--; t[i]--;
            for(int j = 0; j < i; j++){
                if(isinpath(s[i], t[i], s[j]) && isinpath(s[i], t[i], t[j])){
                    cy = true;
                    break;
                }
                if(isinpath(s[j], t[j], s[i]) && isinpath(s[j], t[j], t[i])){
                    cy = true;
                    break;
                }
                if(isinpath(s[i], t[i], s[j])){
                    if(st[s[i]] <= st[t[j]] && ft[s[i]] >= ft[t[j]]){
                        cy = true;
                        break;
                    }
                    ed[j].pb(i);
                    continue;
                }
                if(isinpath(s[i], t[i], t[j])){
                    if(st[t[i]] <= st[s[j]] && ft[t[i]] >= ft[s[j]]){
                        cy = true;
                        break;
                    }
                    ed[i].pb(j);
                    continue;
                }
                swap(i, j);
                if(isinpath(s[i], t[i], s[j])){
                    if(st[s[i]] <= st[t[j]] && ft[s[i]] >= ft[t[j]]){
                        cy = true;
                        break;
                    }
                    ed[j].pb(i);
                    swap(i, j);
                    continue;
                }
                if(isinpath(s[i], t[i], t[j])){
                    if(st[t[i]] <= st[s[j]] && ft[t[i]] >= ft[s[j]]){
                        cy = true;
                        break;
                    }
                    ed[i].pb(j);
                    swap(i, j); 
                    continue;
                }
                swap(i, j);
            }
        }
        if(cy){
            cout << "No\n";
            continue;
        }
        for(int i = 0; i < m; i++) if(!mark[i])
            dfs(i);
        cout << (cy ? "No\n" : "Yes\n");
    }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9800 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 7 ms 9868 KB Output is correct
5 Incorrect 11 ms 9856 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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