oj.uz

Submission #993489

# Submission time Handle Problem Language Result Execution time Memory
993489 2024-06-05T19:52:39 Z snpmrnhlol Jail (JOI22_jail) C++17
5 / 100
 322 ms 88976 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 12e4;
const int S = 5*N;
const int logN = 20;
vector <int> e[N];
vector <int> e2[S];
int deg[S];
int n,m;
int ls[S],rs[S];
queue <int> q;
int cnt = 0;
int root1;
int root2;
int sub[N];
int dpth[N];
int cnt2 = 0;
int st[N],st2[N];
int starts[N],endz[N];
int top[N];
int p1[N],p2[N];
int su[N],sw[N];
int pr[N];
int rmq[N][logN];
void build1(int l = 0,int r = n - 1,int node = 0){
    if(l != r){
        int mij = (l + r)/2;
        if(l != mij)ls[node] = cnt++;
        else ls[node] = p1[mij];
        if(mij + 1 != r)rs[node] = cnt++;
        else rs[node] = p1[mij + 1];
        e2[node].push_back(ls[node]);
        e2[node].push_back(rs[node]);
        build1(l,mij,ls[node]);
        build1(mij + 1,r,rs[node]);
    }
}
void build2(int l = 0,int r = n - 1,int node = 0){
    if(l != r){
        int mij = (l + r)/2;
        if(l != mij)ls[node] = cnt++;
        else ls[node] = p2[mij];
        if(mij + 1 != r)rs[node] = cnt++;
        else rs[node] = p2[mij + 1];
        e2[ls[node]].push_back(node);
        e2[rs[node]].push_back(node);
        build2(l,mij,ls[node]);
        build2(mij + 1,r,rs[node]);
    }
}
void dfs(int node, int p){
    pr[node] = p;
    sub[node] = 1;
    if(p == -1)dpth[node] = 0;
    else dpth[node] = dpth[p] + 1;
    for(auto i:e[node]){
        if(i == p)continue;
        dfs(i, node);
        sub[node]+=sub[i];
    }
    int mxid = -1;
    for(int i = 0;i < e[node].size();i++){
        if(e[node][i] == p)continue;
        if(mxid == -1 || sub[e[node][mxid]] < sub[e[node][i]]){
            mxid = i;
        }
    }
    if(mxid != -1){
        swap(e[node][mxid],e[node][0]);
    }
    for(int i = 0;i < e[node].size();i++){
        if(e[node][i] == p){
            swap(e[node][i],e[node].back());
            e[node].pop_back();
            break;
        }
    }
}
int last[N],first[N];
int laen[N],firen[N];
int rp1[N],rp2[N];
int cnt3 = 0,cnt4 = 0;
void dfs2(int node, int p){
    st[node] = cnt2++;
    st2[cnt2 - 1] = node;
    bool ok = 0;
    if(starts[node] != -1){
        rp1[node] = cnt3++;
        p1[cnt3 - 1] = starts[node];
    }
    if(endz[node] != -1){
        rp2[node] = cnt4++;
        p2[cnt4 - 1] = endz[node];
    }
    if(starts[node] != -1){
        first[node] = node;
    }else if(top[node] == node){
        first[node] = -1;
    }else{
        first[node] = first[p];
    }
    if(endz[node] != -1){
        firen[node] = node;
    }else if(top[node] == node){
        firen[node] = -1;
    }else{
        firen[node] = firen[p];
    }
    for(auto i:e[node]){
        if(i == p)continue;
        if(!ok){
            top[i] = top[node];
        }else{
            top[i] = i;
        }
        dfs2(i, node);
        ok = 1;
    }
    if(starts[node] != -1){
        last[node] = node;
    }else if(!e[node].empty()){
        last[node] = last[e[node][0]];
    }else{
        last[node] = -1;
    }
    if(endz[node] != -1){
        laen[node] = node;
    }else if(!e[node].empty()){
        laen[node] = laen[e[node][0]];
    }else{
        laen[node] = -1;
    }
}
void updstart(int ql,int qr,int id,int l = 0,int r = m - 1,int node = root1){
    assert(ql <= qr);
    if(ql <= l && r <= qr){
        e2[id].push_back(node);
    }else{
        int mij = (l + r)/2;
        if(qr <= mij){
            updstart(ql,qr,id,l,mij,ls[node]);
        }else if(mij + 1 <= ql){
            updstart(ql,qr,id,mij + 1,r,rs[node]);
        }else{
            updstart(ql,qr,id,l,mij,ls[node]);
            updstart(ql,qr,id,mij + 1,r,rs[node]);
        }
    }
}
void updends(int ql,int qr,int id,int l = 0,int r = m - 1,int node = root2){
    assert(ql <= qr);
    if(ql <= l && r <= qr){
        e2[node].push_back(id);
    }else{
        int mij = (l + r)/2;
        if(qr <= mij){
            updends(ql,qr,id,l,mij,ls[node]);
        }else if(mij + 1 <= ql){
            updends(ql,qr,id,mij + 1,r,rs[node]);
        }else{
            updends(ql,qr,id,l,mij,ls[node]);
            updends(ql,qr,id,mij + 1,r,rs[node]);
        }
    }
}
int prog(int u,int w){
    int df = dpth[w] - dpth[u] - 1;
    if(df < 0)return pr[u];
    for(int i = logN - 1;i >= 0;i--){
        if(df>>i&1){
            df-=(1<<i);
            w = rmq[w][i];
        }
    }
    if(pr[w] == u)return w;
    return u;
}
void addstarts(int u,int w,int id){
    u = prog(u,w);
    while(top[u] != top[w]){
        if(dpth[top[u]] > dpth[top[w]])swap(u,w);
        if(first[top[w]] != -1 && last[w] != -1){
            updstart(rp1[last[w]],rp1[first[top[w]]],id);
        }
        w = pr[top[w]];
    }
    if(dpth[u] > dpth[w])swap(u,w);
    if(first[w] != -1 && last[u] != -1 && rp1[last[u]] <= rp1[first[w]]){
        updstart(rp1[last[u]],rp1[first[w]],id);
    }
}
void addends(int u,int w,int id){
    w = prog(w,u);
    while(top[u] != top[w]){
        if(dpth[top[u]] > dpth[top[w]])swap(u,w);
        if(firen[top[w]] != -1 && laen[w] != -1){
            updends(rp2[laen[w]],rp2[firen[top[w]]],id);
        }
        w = pr[top[w]];
    }
    if(dpth[u] > dpth[w])swap(u,w);
    if(firen[w] != -1 && laen[u] != -1 && rp2[laen[u]] <= rp2[firen[w]]){
        updends(rp2[laen[u]],rp2[firen[w]],id);
    }
}
bool topsort(){
    int nr = 0;
    for(int i = 0;i < cnt;i++){
        deg[i] = 0;
    }
    for(int i = 0;i < cnt;i++){
        for(auto j:e2[i]){
            deg[j]++;
        }
    }
    for(int i = 0;i < cnt;i++){
        if(deg[i] == 0)q.push(i);
    }
    while(!q.empty()){
        int x = q.front();
        nr++;
        q.pop();
        for(auto i:e2[x]){
            deg[i]--;
            if(deg[i] == 0){
                q.push(i);
            }
        }
    }
    return nr == cnt;
}
void solve(){
    cnt3 = cnt4 = 0;
    cin>>n;
    for(int i = 0;i < n - 1;i++){
        int u,w;
        cin>>u>>w;
        u--;w--;
        e[w].push_back(u);
        e[u].push_back(w);
    }
    for(int i = 0;i < n;i++){
        last[i] = -1;
        starts[i] = -1;
        endz[i] = -1;
    }
    cin>>m;
    for(int i = 0;i < m;i++){
        int u,w;
        cin>>u>>w;
        u--;w--;
        starts[u] = i;
        endz[w] = i;
        su[i] = u;
        sw[i] = w;
    }
    cnt2 = 0;
    top[0] = 0;
    dfs(0, -1);
    dfs2(0, -1);
    cnt = m;
    root1 = cnt++;
    build1(0,m - 1,cnt - 1);
    root2 = cnt++;
    build2(0,m - 1,cnt - 1);
    for(int i = 0;i < n;i++){
        rmq[i][0] = pr[i];
    }
    for(int j = 1;j < logN;j++){
        for(int i = 0;i < n;i++){
            rmq[i][j] = rmq[rmq[i][j - 1]][j - 1];
        }
    }
    for(int i = 0;i < m;i++){
        int u = su[i];
        int w = sw[i];
        addstarts(u,w,i);
        addends(u,w,i);
    }
    bool ok = topsort();
    if(ok){
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
    for(int i = 0;i < n;i++){
        e[i].clear();
    }
    for(int i = 0;i < cnt;i++){
        e2[i].clear();
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

Compilation message

jail.cpp: In function 'void dfs(int, int)':
jail.cpp:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0;i < e[node].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~
jail.cpp:71:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 0;i < e[node].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33628 KB Output is correct
2 Correct 5 ms 33624 KB Output is correct
3 Correct 5 ms 33628 KB Output is correct
4 Correct 11 ms 34236 KB Output is correct
5 Correct 18 ms 34628 KB Output is correct
6 Correct 6 ms 33936 KB Output is correct
7 Correct 5 ms 33884 KB Output is correct
8 Correct 6 ms 33880 KB Output is correct
9 Correct 26 ms 35676 KB Output is correct
10 Correct 40 ms 54480 KB Output is correct
11 Correct 9 ms 33884 KB Output is correct
12 Correct 29 ms 34648 KB Output is correct
13 Correct 76 ms 64080 KB Output is correct
14 Correct 84 ms 64560 KB Output is correct
15 Correct 126 ms 69436 KB Output is correct
16 Correct 322 ms 88976 KB Output is correct
17 Correct 109 ms 66896 KB Output is correct
18 Correct 99 ms 69716 KB Output is correct
19 Correct 89 ms 68692 KB Output is correct
20 Correct 86 ms 68700 KB Output is correct
21 Correct 102 ms 72016 KB Output is correct
22 Correct 57 ms 63312 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33624 KB Output is correct
2 Correct 5 ms 33852 KB Output is correct
3 Correct 5 ms 33624 KB Output is correct
4 Correct 4 ms 33628 KB Output is correct
5 Correct 8 ms 33884 KB Output is correct
6 Correct 6 ms 33884 KB Output is correct
7 Incorrect 6 ms 33884 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33628 KB Output is correct
2 Correct 5 ms 33624 KB Output is correct
3 Correct 5 ms 33628 KB Output is correct
4 Correct 11 ms 34236 KB Output is correct
5 Correct 18 ms 34628 KB Output is correct
6 Correct 6 ms 33936 KB Output is correct
7 Correct 5 ms 33884 KB Output is correct
8 Correct 6 ms 33880 KB Output is correct
9 Correct 26 ms 35676 KB Output is correct
10 Correct 40 ms 54480 KB Output is correct
11 Correct 9 ms 33884 KB Output is correct
12 Correct 29 ms 34648 KB Output is correct
13 Correct 76 ms 64080 KB Output is correct
14 Correct 84 ms 64560 KB Output is correct
15 Correct 126 ms 69436 KB Output is correct
16 Correct 322 ms 88976 KB Output is correct
17 Correct 109 ms 66896 KB Output is correct
18 Correct 99 ms 69716 KB Output is correct
19 Correct 89 ms 68692 KB Output is correct
20 Correct 86 ms 68700 KB Output is correct
21 Correct 102 ms 72016 KB Output is correct
22 Correct 57 ms 63312 KB Output is correct
23 Correct 5 ms 33880 KB Output is correct
24 Correct 4 ms 33884 KB Output is correct
25 Correct 5 ms 33884 KB Output is correct
26 Correct 6 ms 33812 KB Output is correct
27 Incorrect 6 ms 33884 KB Output isn't correct
28 Halted 0 ms 0 KB -