제출 #1081118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081118		underwaterkillerwhale	Jail (JOI22_jail)	C++17	49 / 100	57 ms	20572 KiB

jail

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e5 + 7;
const int Mod = 1e9 + 7;
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 320;

int n, m, Q;
vector<int> ke[N], ke2[N];
int high[N], pa[N];
int S[N], E[N];
pii qr[N];

void pdfs (int u, int p) {
    high[u] = high[p] + 1;
    pa[u] = p;
    iter (&v, ke[u]) {
        if (v != p) pdfs(v, u);
    }
}

int num[N], low[N], del[N];
int time_dfs = 0;
bool ok = 1;
stack<int> st;

void dfs (int u) {
    num[u] = low[u] = ++time_dfs;
    st.push(u);
    iter (&v, ke2[u]) {
        if (del[v]) continue;
        if (!num[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], num[v]);
    }
    if (num[u] == low[u]) {
        int v;
        int num = 0;
        do {
           v = st.top();
           st.pop();
           num ++;
           del[v] = 1;
        }while (v != u);
        if (num > 1) ok = 0;
    }
}

void solution () {
    time_dfs = 0;
    ok = 1;
    rep (i, 1, n) vector<int> ().swap(ke[i]), vector<int> ().swap(ke2[i]), E[i] = S[i] = num[i] = low[i] = del[i] = 0;
    cin >> n;
    rep (i, 1, n - 1) {
        int u, v;
        cin >> u>> v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    pdfs(1, 0);
    cin >> m;
    rep (i, 1, m) {
        cin >> qr[i].fs >> qr[i].se;
        S[qr[i].fs] = i;
        E[qr[i].se] = i;
    }
    rep (i, 1, m) {
        int u = qr[i].fs, v = qr[i].se;
        while (u != v) {
            if (high[u] > high[v]) swap(u, v);
            if (E[v]) ke2[i].pb(E[v]);
            if (S[v]) ke2[S[v]].pb(i);
            v = pa[v];
        }
        if (E[v]) ke2[i].pb(E[v]);
        if (S[v]) ke2[S[v]].pb(i);
    }
    rep (i, 1, m) if (!num[i]) dfs(i);
    if (ok) cout <<"Yes\n";
    else cout<<"No\n";

}


#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +4
mình có muốn dùng mảng này không?
4 5
1 3
4 1
1 2
3 2
2 1
return->break
*/

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23