제출 #660238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660238		fatemetmhr	Jail (JOI22_jail)	C++17	5 / 100	5068 ms	33988 KiB

jail

// 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
• Subtask 2: 5 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23