oj.uz

Submission #951093

# Submission time Handle Problem Language Result Execution time Memory
951093 2024-03-21T06:35:03 Z hotboy2703 Jail (JOI22_jail) C++14
49 / 100
 894 ms 837024 KB 
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
ll n,m;
const ll MAXN = 1.2e5;
const ll MAXK = 17;
ll cur_node;
namespace CYC{
    vector <ll> g[MAXN*MAXK*2 + MAXN * 5 + 100];
    void add_edge(ll u,ll v){g[u].push_back(v);}
    bool in[MAXN+100];
    bool in_st[MAXN+100];
    bool detect_cycle;
    void init(){
        for (ll i = 1;i <= cur_node;i++){g[i].clear();in[i] = 0;in_st[i] = 0;}
        detect_cycle = 0;
    }
    void dfs(ll u){
        in_st[u] = 1;
        in[u] = 1;
        for (auto v:g[u]){
            if (in_st[v])detect_cycle = 1;
            if (in[v])continue;
            dfs(v);
        }
        in_st[u] = 0;
    }
    void solve(){
        for (ll i = 1;i <= cur_node;i++)if (!in[i])dfs(i);
    }
}
vector <ll> g[MAXN+100];
ll sp[MAXK][MAXN+100];
ll node[MAXK][MAXN+100];
ll path[MAXN+100][2];
ll depth[MAXN+100];
ll lca(ll u,ll v){
    if (depth[u] > depth[v])swap(u,v);
    for (ll j = MAXK-1;j>=0;j--){
        if (depth[sp[j][v]]>=depth[u])v=sp[j][v];
    }
    if (v==u)return u;
    for (ll j = MAXK-1;j>=0;j--){
        if (sp[j][v] != sp[j][u]){
            v=sp[j][v];
            u=sp[j][u];
        }
    }
    return sp[0][u];
}
void dfs(ll u,ll p){
    sp[0][u] = p;
    depth[u] = depth[p]+1;
    for (auto v:g[u]){
        if (v==p)continue;
        dfs(v,u);
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    ll t;
    cin>>t;
    while (t--){
        cin>>n;
        for (ll i = 1;i <= n; i++){
            g[i].clear();

        }
        for (ll i = 1;i < n;i ++){
            ll u,v;
            cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        cin>>m;
        for (ll i = 1;i <= m;i ++){
            ll s,t;
            cin>>s>>t;
            path[i][0] = s,path[i][1] = t;
        }
        dfs(1,1);
        for (ll j = 1;j < MAXK;j ++){
            for (ll i = 1;i <= n;i ++){
                sp[j][i] = sp[j-1][sp[j-1][i]];
//                cout<<sp[j][i]<<' ';
            }
//            cout<<'\n';
        }
        vector <pll> edge[2];
        cur_node = m + 1;
        for (ll k = 0;k < 2;k ++){
            for (ll i = 1;i <= n;i ++){
                node[0][i] = cur_node++;
            }
            for (ll j = 1;j < MAXK;j ++){
                for (ll i = 1;i <= n;i ++){
                    node[j][i] = cur_node++;
                    edge[k].push_back(MP(node[j][i],node[j-1][i]));
                    edge[k].push_back(MP(node[j][i],node[j-1][sp[j-1][i]]));
                }
            }
            for (ll i = 1;i <= m;i ++){
                edge[k].push_back(MP(node[0][path[i][k]],i));
            }
            for (ll i = 1;i <= m;i ++){
                ll u = path[i][0],v = path[i][1];
                ll x = lca(u,v);
//                cout<<u<<' '<<v<<' '<<x<<'\n';
                bool no_lca = 0;
                if (k==0){
                    if (u != x)u = sp[0][u];
                    else no_lca = 1;
                }
                if (k==1){
                    if (v != x)v = sp[0][v];
                    else no_lca = 1;
                }
                for (ll j = MAXK-1;j>=0;j--){
                    if (depth[u]-MASK(j) >= depth[x]){
//                        cout<<"U "<<i<<' '<<j<<'\n';
                        edge[k].push_back(MP(i,node[j][u]));
                        u = sp[j][u];
                    }
                    if (depth[v]-MASK(j) >= depth[x]){
//                        cout<<"V "<<i<<' '<<j<<'\n';
                        edge[k].push_back(MP(i,node[j][v]));
                        v = sp[j][v];
                    }
                }
                if (!no_lca)edge[k].push_back(MP(i,node[0][x]));
            }
        }
        CYC::init();
        for (ll j = 0;j < 2;j ++){
            for (auto x:edge[j]){
                if (j)swap(x.fi,x.se);
                CYC::add_edge(x.fi,x.se);
            }
        }
        CYC::solve();
        cout<<(CYC::detect_cycle?"No":"Yes")<<'\n';
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 137816 KB Output is correct
2 Correct 30 ms 139884 KB Output is correct
3 Correct 30 ms 137700 KB Output is correct
4 Correct 93 ms 138320 KB Output is correct
5 Correct 165 ms 138832 KB Output is correct
6 Correct 36 ms 138588 KB Output is correct
7 Correct 37 ms 138644 KB Output is correct
8 Correct 38 ms 138972 KB Output is correct
9 Runtime error 178 ms 306660 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 137680 KB Output is correct
2 Correct 29 ms 139820 KB Output is correct
3 Correct 36 ms 138580 KB Output is correct
4 Correct 38 ms 138600 KB Output is correct
5 Correct 41 ms 138592 KB Output is correct
6 Correct 40 ms 138568 KB Output is correct
7 Correct 38 ms 138580 KB Output is correct
8 Correct 36 ms 134556 KB Output is correct
9 Correct 37 ms 142700 KB Output is correct
10 Correct 37 ms 142680 KB Output is correct
11 Correct 37 ms 142676 KB Output is correct
12 Correct 35 ms 142544 KB Output is correct
13 Correct 35 ms 142556 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 137680 KB Output is correct
2 Correct 29 ms 139820 KB Output is correct
3 Correct 36 ms 138580 KB Output is correct
4 Correct 38 ms 138600 KB Output is correct
5 Correct 41 ms 138592 KB Output is correct
6 Correct 40 ms 138568 KB Output is correct
7 Correct 38 ms 138580 KB Output is correct
8 Correct 36 ms 134556 KB Output is correct
9 Correct 37 ms 142700 KB Output is correct
10 Correct 37 ms 142680 KB Output is correct
11 Correct 37 ms 142676 KB Output is correct
12 Correct 35 ms 142544 KB Output is correct
13 Correct 35 ms 142556 KB Output is correct
14 Correct 30 ms 141912 KB Output is correct
15 Correct 30 ms 141916 KB Output is correct
16 Correct 38 ms 142684 KB Output is correct
17 Correct 41 ms 142780 KB Output is correct
18 Correct 39 ms 142676 KB Output is correct
19 Correct 31 ms 141824 KB Output is correct
20 Correct 37 ms 142680 KB Output is correct
21 Correct 38 ms 142684 KB Output is correct
22 Correct 38 ms 142748 KB Output is correct
23 Correct 29 ms 141912 KB Output is correct
24 Correct 31 ms 142164 KB Output is correct
25 Correct 38 ms 142648 KB Output is correct
26 Correct 32 ms 142376 KB Output is correct
27 Correct 38 ms 142680 KB Output is correct
28 Correct 31 ms 141916 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 137680 KB Output is correct
2 Correct 29 ms 139820 KB Output is correct
3 Correct 36 ms 138580 KB Output is correct
4 Correct 38 ms 138600 KB Output is correct
5 Correct 41 ms 138592 KB Output is correct
6 Correct 40 ms 138568 KB Output is correct
7 Correct 38 ms 138580 KB Output is correct
8 Correct 36 ms 134556 KB Output is correct
9 Correct 37 ms 142700 KB Output is correct
10 Correct 37 ms 142680 KB Output is correct
11 Correct 37 ms 142676 KB Output is correct
12 Correct 35 ms 142544 KB Output is correct
13 Correct 35 ms 142556 KB Output is correct
14 Correct 30 ms 141912 KB Output is correct
15 Correct 30 ms 141916 KB Output is correct
16 Correct 38 ms 142684 KB Output is correct
17 Correct 41 ms 142780 KB Output is correct
18 Correct 39 ms 142676 KB Output is correct
19 Correct 31 ms 141824 KB Output is correct
20 Correct 37 ms 142680 KB Output is correct
21 Correct 38 ms 142684 KB Output is correct
22 Correct 38 ms 142748 KB Output is correct
23 Correct 29 ms 141912 KB Output is correct
24 Correct 31 ms 142164 KB Output is correct
25 Correct 38 ms 142648 KB Output is correct
26 Correct 32 ms 142376 KB Output is correct
27 Correct 38 ms 142680 KB Output is correct
28 Correct 31 ms 141916 KB Output is correct
29 Correct 40 ms 143300 KB Output is correct
30 Correct 40 ms 141440 KB Output is correct
31 Correct 40 ms 139068 KB Output is correct
32 Correct 38 ms 138876 KB Output is correct
33 Correct 37 ms 138612 KB Output is correct
34 Correct 40 ms 138608 KB Output is correct
35 Correct 38 ms 138624 KB Output is correct
36 Correct 36 ms 138696 KB Output is correct
37 Correct 35 ms 138568 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 137680 KB Output is correct
2 Correct 29 ms 139820 KB Output is correct
3 Correct 36 ms 138580 KB Output is correct
4 Correct 38 ms 138600 KB Output is correct
5 Correct 41 ms 138592 KB Output is correct
6 Correct 40 ms 138568 KB Output is correct
7 Correct 38 ms 138580 KB Output is correct
8 Correct 36 ms 134556 KB Output is correct
9 Correct 37 ms 142700 KB Output is correct
10 Correct 37 ms 142680 KB Output is correct
11 Correct 37 ms 142676 KB Output is correct
12 Correct 35 ms 142544 KB Output is correct
13 Correct 35 ms 142556 KB Output is correct
14 Correct 30 ms 141912 KB Output is correct
15 Correct 30 ms 141916 KB Output is correct
16 Correct 38 ms 142684 KB Output is correct
17 Correct 41 ms 142780 KB Output is correct
18 Correct 39 ms 142676 KB Output is correct
19 Correct 31 ms 141824 KB Output is correct
20 Correct 37 ms 142680 KB Output is correct
21 Correct 38 ms 142684 KB Output is correct
22 Correct 38 ms 142748 KB Output is correct
23 Correct 29 ms 141912 KB Output is correct
24 Correct 31 ms 142164 KB Output is correct
25 Correct 38 ms 142648 KB Output is correct
26 Correct 32 ms 142376 KB Output is correct
27 Correct 38 ms 142680 KB Output is correct
28 Correct 31 ms 141916 KB Output is correct
29 Correct 40 ms 143300 KB Output is correct
30 Correct 40 ms 141440 KB Output is correct
31 Correct 40 ms 139068 KB Output is correct
32 Correct 38 ms 138876 KB Output is correct
33 Correct 37 ms 138612 KB Output is correct
34 Correct 40 ms 138608 KB Output is correct
35 Correct 38 ms 138624 KB Output is correct
36 Correct 36 ms 138696 KB Output is correct
37 Correct 35 ms 138568 KB Output is correct
38 Runtime error 175 ms 310668 KB Execution killed with signal 11
39 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 137816 KB Output is correct
2 Correct 33 ms 137808 KB Output is correct
3 Correct 30 ms 137816 KB Output is correct
4 Correct 30 ms 137812 KB Output is correct
5 Correct 79 ms 139960 KB Output is correct
6 Correct 34 ms 138456 KB Output is correct
7 Correct 33 ms 138384 KB Output is correct
8 Correct 31 ms 139812 KB Output is correct
9 Correct 30 ms 135992 KB Output is correct
10 Correct 31 ms 137952 KB Output is correct
11 Correct 30 ms 137816 KB Output is correct
12 Correct 35 ms 138692 KB Output is correct
13 Correct 129 ms 141420 KB Output is correct
14 Correct 193 ms 139124 KB Output is correct
15 Correct 161 ms 138992 KB Output is correct
16 Runtime error 894 ms 837024 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 85 ms 137816 KB Output is correct
2 Correct 30 ms 139884 KB Output is correct
3 Correct 30 ms 137700 KB Output is correct
4 Correct 93 ms 138320 KB Output is correct
5 Correct 165 ms 138832 KB Output is correct
6 Correct 36 ms 138588 KB Output is correct
7 Correct 37 ms 138644 KB Output is correct
8 Correct 38 ms 138972 KB Output is correct
9 Runtime error 178 ms 306660 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -