oj.uz

Submission #1082458

# Submission time Handle Problem Language Result Execution time Memory
1082458 2024-08-31T11:29:08 Z underwaterkillerwhale Jail (JOI22_jail) C++17
49 / 100
 65 ms 53844 KB 
#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];
pii qr[N];

int high[N], nC[N], pa[N], time_dfs;

int ein[N], Head[N];

int num_Ver = 0;

vector<int> ke2[N << 3];

int num[N << 3], low[N << 3 ], del[N << 3], time_dfs2 = 0;///aware
stack<int> st;

bool Ans;

//pii rr[N << 3];

struct Segment_Tree_st {
    int m;
    int st[N << 2], lab[N << 2];

    void build (int id, int l, int r, int typ) {
        ++num_Ver;
        lab[id] = num_Ver;
//        cout << l <<","<<r<<","<<typ<<" "<<num_Ver<<"\n";
        if (l == r) {
            return;
        }
        int mid = l + r >> 1;
        build (id << 1, l, mid, typ);
        build (id << 1 | 1, mid + 1, r, typ);
        if (typ == 0)
            ke2[lab[id << 1]].pb(lab[id]), ke2[lab[id << 1 | 1]].pb(lab[id]);
        else
            ke2[lab[id]].pb(lab[id << 1]), ke2[lab[id]].pb(lab[id << 1 | 1]);
    }

    int get (int id, int l, int r, int pos) {
        if (l > pos || r < pos) return -1;
        if (l == r) return lab[id];
        int mid = l + r >> 1;
        return max(get (id << 1, l, mid, pos), get (id << 1 | 1, mid + 1, r, pos));
    }

    void add_edge (int id, int l, int r, int u, int v, int clab, int typ) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            if (typ == 0) {
                ke2[lab[id]].pb(clab);
//                cout << lab[id]<< " "<<clab<<" b\n";
            }
            else {
                ke2[clab].pb(lab[id]);
//                cout << clab<<" "<<lab[id]<<" c\n";
            }
            return;
        }
        int mid = l + r >> 1;
        add_edge (id << 1, l, mid, u, v, clab, typ);
        add_edge (id << 1 | 1, mid + 1, r, u, v, clab, typ);
    }

    void add_edge1 (int u, int v, int clab, int st, int ed, int typ) {
        if (typ == 0) {
            if (u == ein[st]) ++u;
            if (v == ein[st]) --v;
        }
        else {
            if (u == ein[ed]) ++u;
            if (v == ein[ed]) --v;
        }
//        cout << u <<" "<<v<<" "<<ein[st]<<" "<<typ<<" hihi\n";
        add_edge (1, 1, m, u, v, clab, typ);
    }

    int get (int pos) {
        return get (1, 1, m, pos);
    }

    void init (int n, int typ) {
        m = n;
        build (1, 1, m, typ);
    }
}STs, STe;

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

void hld (int u, int p) {
    ein[u] = ++time_dfs;
    Head[u] = p;
    int mxV = -1;
    iter (&v, ke[u]) if (v != pa[u] && (mxV == -1 || nC[v] > nC[mxV])) mxV = v;
    if (mxV != -1) hld(mxV, p);
    iter (&v, ke[u]) {
        if (v == pa[u] || v == mxV) continue;
        hld(v, v);
    }
}

void query (int st, int ed) {
    int u = st, v = ed, labs = STs.get(ein[st]), labe = STe.get(ein[ed]);
    ke2[labe].pb(labs);
//    cout << labe << " "<<labs<<" a\n";
//    return;
    for (; Head[u] != Head[v]; v = pa[Head[v]]) {
        if (high[Head[u]] > high[Head[v]]) swap(u, v);
        STs.add_edge1 (ein[Head[v]], ein[v], labe, st, ed, 0);
        STe.add_edge1 (ein[Head[v]], ein[v], labs, st, ed, 1);
    }
    if (high[u] > high[v]) swap(u, v);
    STs.add_edge1 (ein[u], ein[v], labe, st, ed, 0);
    STe.add_edge1 (ein[u], ein[v], labs, st, ed, 1);
}

void dfs (int u) {
    num[u] = low[u] = ++time_dfs2;
    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_del = 0;
        do {
            v = st.top();
            st.pop();
            del[v] = 1;
//            cout << v<<"\n";
            ++num_del;
        }while (v != u);
        if (num_del > 1) {
            Ans = 0;
//            exit(0);
        }
    }
}

void solution () {
    rep (i, 1, num_Ver) vector<int> ().swap(ke[i]), vector<int> ().swap(ke2[i]), num[i] = low[i] = del[i] = 0;
    time_dfs = time_dfs2 = 0, Ans = 1, num_Ver = 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);
    hld (1, 1);
    STs.init(n, 0);
    STe.init(n, 1);
    cin >> m;
    rep (i, 1, m) {
        cin >> qr[i].fs >> qr[i].se;
        query (qr[i].fs, qr[i].se);
    }
    rep (i, 1, m) {
    }
//    cout << num_Ver<<"\n";
    rep (i, 1, num_Ver) {
//        cout << i <<" "<<SZ(ke2[i])<<"\n";
//        iter (&v, ke2[i]) cout <<i<<" "<<v<<"\n";
        if (!num[i]) dfs(i);
    }
    if (Ans) 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
*/

Compilation message

jail.cpp: In member function 'void Segment_Tree_st::build(int, int, int, int)':
jail.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int mid = l + r >> 1;
      |                   ~~^~~
jail.cpp: In member function 'int Segment_Tree_st::get(int, int, int, int)':
jail.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid = l + r >> 1;
      |                   ~~^~~
jail.cpp: In member function 'void Segment_Tree_st::add_edge(int, int, int, int, int, int, int)':
jail.cpp:86:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22872 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 5 ms 22856 KB Output is correct
4 Correct 25 ms 23128 KB Output is correct
5 Correct 38 ms 23640 KB Output is correct
6 Correct 6 ms 22872 KB Output is correct
7 Correct 6 ms 22872 KB Output is correct
8 Correct 7 ms 22872 KB Output is correct
9 Correct 57 ms 25632 KB Output is correct
10 Runtime error 40 ms 53572 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Correct 5 ms 22876 KB Output is correct
3 Correct 6 ms 22872 KB Output is correct
4 Correct 6 ms 22876 KB Output is correct
5 Correct 6 ms 22872 KB Output is correct
6 Correct 6 ms 22992 KB Output is correct
7 Correct 6 ms 22992 KB Output is correct
8 Correct 7 ms 22872 KB Output is correct
9 Correct 6 ms 22876 KB Output is correct
10 Correct 6 ms 23000 KB Output is correct
11 Correct 6 ms 22984 KB Output is correct
12 Correct 5 ms 22876 KB Output is correct
13 Correct 5 ms 22876 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Correct 5 ms 22876 KB Output is correct
3 Correct 6 ms 22872 KB Output is correct
4 Correct 6 ms 22876 KB Output is correct
5 Correct 6 ms 22872 KB Output is correct
6 Correct 6 ms 22992 KB Output is correct
7 Correct 6 ms 22992 KB Output is correct
8 Correct 7 ms 22872 KB Output is correct
9 Correct 6 ms 22876 KB Output is correct
10 Correct 6 ms 23000 KB Output is correct
11 Correct 6 ms 22984 KB Output is correct
12 Correct 5 ms 22876 KB Output is correct
13 Correct 5 ms 22876 KB Output is correct
14 Correct 4 ms 22856 KB Output is correct
15 Correct 5 ms 22876 KB Output is correct
16 Correct 6 ms 22876 KB Output is correct
17 Correct 6 ms 22876 KB Output is correct
18 Correct 7 ms 22876 KB Output is correct
19 Correct 5 ms 22876 KB Output is correct
20 Correct 6 ms 22876 KB Output is correct
21 Correct 6 ms 22756 KB Output is correct
22 Correct 7 ms 22876 KB Output is correct
23 Correct 5 ms 22876 KB Output is correct
24 Correct 5 ms 22876 KB Output is correct
25 Correct 6 ms 22876 KB Output is correct
26 Correct 5 ms 22860 KB Output is correct
27 Correct 6 ms 22876 KB Output is correct
28 Correct 4 ms 22876 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Correct 5 ms 22876 KB Output is correct
3 Correct 6 ms 22872 KB Output is correct
4 Correct 6 ms 22876 KB Output is correct
5 Correct 6 ms 22872 KB Output is correct
6 Correct 6 ms 22992 KB Output is correct
7 Correct 6 ms 22992 KB Output is correct
8 Correct 7 ms 22872 KB Output is correct
9 Correct 6 ms 22876 KB Output is correct
10 Correct 6 ms 23000 KB Output is correct
11 Correct 6 ms 22984 KB Output is correct
12 Correct 5 ms 22876 KB Output is correct
13 Correct 5 ms 22876 KB Output is correct
14 Correct 4 ms 22856 KB Output is correct
15 Correct 5 ms 22876 KB Output is correct
16 Correct 6 ms 22876 KB Output is correct
17 Correct 6 ms 22876 KB Output is correct
18 Correct 7 ms 22876 KB Output is correct
19 Correct 5 ms 22876 KB Output is correct
20 Correct 6 ms 22876 KB Output is correct
21 Correct 6 ms 22756 KB Output is correct
22 Correct 7 ms 22876 KB Output is correct
23 Correct 5 ms 22876 KB Output is correct
24 Correct 5 ms 22876 KB Output is correct
25 Correct 6 ms 22876 KB Output is correct
26 Correct 5 ms 22860 KB Output is correct
27 Correct 6 ms 22876 KB Output is correct
28 Correct 4 ms 22876 KB Output is correct
29 Correct 8 ms 22876 KB Output is correct
30 Correct 8 ms 22876 KB Output is correct
31 Correct 7 ms 22876 KB Output is correct
32 Correct 8 ms 22876 KB Output is correct
33 Correct 7 ms 22876 KB Output is correct
34 Correct 7 ms 22852 KB Output is correct
35 Correct 7 ms 22872 KB Output is correct
36 Correct 6 ms 22876 KB Output is correct
37 Correct 6 ms 22876 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Correct 5 ms 22876 KB Output is correct
3 Correct 6 ms 22872 KB Output is correct
4 Correct 6 ms 22876 KB Output is correct
5 Correct 6 ms 22872 KB Output is correct
6 Correct 6 ms 22992 KB Output is correct
7 Correct 6 ms 22992 KB Output is correct
8 Correct 7 ms 22872 KB Output is correct
9 Correct 6 ms 22876 KB Output is correct
10 Correct 6 ms 23000 KB Output is correct
11 Correct 6 ms 22984 KB Output is correct
12 Correct 5 ms 22876 KB Output is correct
13 Correct 5 ms 22876 KB Output is correct
14 Correct 4 ms 22856 KB Output is correct
15 Correct 5 ms 22876 KB Output is correct
16 Correct 6 ms 22876 KB Output is correct
17 Correct 6 ms 22876 KB Output is correct
18 Correct 7 ms 22876 KB Output is correct
19 Correct 5 ms 22876 KB Output is correct
20 Correct 6 ms 22876 KB Output is correct
21 Correct 6 ms 22756 KB Output is correct
22 Correct 7 ms 22876 KB Output is correct
23 Correct 5 ms 22876 KB Output is correct
24 Correct 5 ms 22876 KB Output is correct
25 Correct 6 ms 22876 KB Output is correct
26 Correct 5 ms 22860 KB Output is correct
27 Correct 6 ms 22876 KB Output is correct
28 Correct 4 ms 22876 KB Output is correct
29 Correct 8 ms 22876 KB Output is correct
30 Correct 8 ms 22876 KB Output is correct
31 Correct 7 ms 22876 KB Output is correct
32 Correct 8 ms 22876 KB Output is correct
33 Correct 7 ms 22876 KB Output is correct
34 Correct 7 ms 22852 KB Output is correct
35 Correct 7 ms 22872 KB Output is correct
36 Correct 6 ms 22876 KB Output is correct
37 Correct 6 ms 22876 KB Output is correct
38 Correct 59 ms 25768 KB Output is correct
39 Runtime error 40 ms 53584 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 22872 KB Output is correct
2 Correct 5 ms 22876 KB Output is correct
3 Correct 5 ms 22916 KB Output is correct
4 Correct 7 ms 22876 KB Output is correct
5 Correct 13 ms 23036 KB Output is correct
6 Correct 9 ms 22876 KB Output is correct
7 Correct 5 ms 22876 KB Output is correct
8 Correct 4 ms 22876 KB Output is correct
9 Correct 5 ms 22724 KB Output is correct
10 Correct 5 ms 22876 KB Output is correct
11 Correct 5 ms 22876 KB Output is correct
12 Correct 7 ms 22872 KB Output is correct
13 Correct 48 ms 23372 KB Output is correct
14 Correct 63 ms 23668 KB Output is correct
15 Correct 65 ms 23632 KB Output is correct
16 Runtime error 47 ms 53844 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22872 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 5 ms 22856 KB Output is correct
4 Correct 25 ms 23128 KB Output is correct
5 Correct 38 ms 23640 KB Output is correct
6 Correct 6 ms 22872 KB Output is correct
7 Correct 6 ms 22872 KB Output is correct
8 Correct 7 ms 22872 KB Output is correct
9 Correct 57 ms 25632 KB Output is correct
10 Runtime error 40 ms 53572 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -