oj.uz

Submission #660238

# Submission time Handle Problem Language Result Execution time Memory
660238 2022-11-21T09:30:31 Z fatemetmhr Jail (JOI22_jail) C++17
5 / 100
 5000 ms 33988 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(lca(s[i], t[i]) == s[i]){
                        if(!(st[s[i]] <= st[t[j]] && ft[s[i]] >= ft[t[j]])){
                            cy = true;
                            break;
                        }
                    }
                    else{
                        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(lca(s[i], t[i]) == t[i]){
                        if(!(st[t[i]] <= st[s[j]] && ft[t[i]] >= ft[s[j]])){
                            cy = true;
                            break;
                        }
                    }
                    else{
                        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(lca(s[i], t[i]) == s[i]){
                        if(!(st[s[i]] <= st[t[j]] && ft[s[i]] >= ft[t[j]])){
                            cy = true;
                            swap(i, j);
                            break;
                        }
                    }
                    else{
                        if(st[s[i]] <= st[t[j]] && ft[s[i]] >= ft[t[j]]){
                            cy = true;
                            swap(i, j);
                            break;
                        }
                    }
                    ed[j].pb(i);
                    swap(i, j);
                    continue;
                }
                if(isinpath(s[i], t[i], t[j])){
                    if(lca(s[i], t[i]) == t[i]){
                        if(!(st[t[i]] <= st[s[j]] && ft[t[i]] >= ft[s[j]])){
                            cy = true;
                            swap(i, j);
                            break;
                        }
                    }
                    else{
                        if(st[t[i]] <= st[s[j]] && ft[t[i]] >= ft[s[j]]){
                            cy = true;
                            swap(i, j);
                            break;
                        }
                    }
                    ed[i].pb(j);
                    swap(i, j);
                    continue;
                }
                swap(i, j);
            }
        }
        if(cy){
            cout << "No\n";
            continue;
        }
        else{
            cout << "Yes\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 5 ms 9812 KB Output is correct
4 Correct 13 ms 9880 KB Output is correct
5 Correct 22 ms 9888 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9792 KB Output is correct
8 Correct 15 ms 9900 KB Output is correct
9 Correct 262 ms 11524 KB Output is correct
10 Correct 66 ms 32556 KB Output is correct
11 Correct 11 ms 9752 KB Output is correct
12 Correct 83 ms 9812 KB Output is correct
13 Execution timed out 5068 ms 33988 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
5.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 9904 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9896 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 7 ms 9812 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 6 ms 9940 KB Output is correct

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 Correct 6 ms 9904 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9896 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 7 ms 9812 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 6 ms 9940 KB Output is correct
14 Incorrect 5 ms 9812 KB Output isn't correct
15 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 Correct 6 ms 9904 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9896 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 7 ms 9812 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 6 ms 9940 KB Output is correct
14 Incorrect 5 ms 9812 KB Output isn't correct
15 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 Correct 6 ms 9904 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9896 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 7 ms 9812 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 6 ms 9940 KB Output is correct
14 Incorrect 5 ms 9812 KB Output isn't correct
15 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 Incorrect 5 ms 9844 KB Output isn't correct
3 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 5 ms 9812 KB Output is correct
4 Correct 13 ms 9880 KB Output is correct
5 Correct 22 ms 9888 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9792 KB Output is correct
8 Correct 15 ms 9900 KB Output is correct
9 Correct 262 ms 11524 KB Output is correct
10 Correct 66 ms 32556 KB Output is correct
11 Correct 11 ms 9752 KB Output is correct
12 Correct 83 ms 9812 KB Output is correct
13 Execution timed out 5068 ms 33988 KB Time limit exceeded
14 Halted 0 ms 0 KB -