oj.uz

Submission #646054

# Submission time Handle Problem Language Result Execution time Memory
646054 2022-09-28T14:27:54 Z victor_gao Jail (JOI22_jail) C++17
72 / 100
 3734 ms 1048576 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 120015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,m,st[N],ed[N],fa[N],dep[N],dfn[N],dft=0,low[N],nscc=0;
bool ins[N];
stack<int>s;
pii pos[N];
vector<int>g[N],ng[N],scc[N];
void dfs(int p,int lp){
    fa[p]=lp;
    dep[p]=dep[lp]+1;
    for (auto i:g[p]){
        if (i!=lp) dfs(i,p);
    }
}
int LCA(int a,int b){
    while (a!=b){
        if (dep[a]>dep[b]) a=fa[a];
        else b=fa[b];
    }
    return a;
}
int find_first_start(int x,int lca){
    if (dep[x]<dep[lca]) return 0;
    while (x!=lca&&!st[x]) x=fa[x];
    if (st[x]) return st[x];
    else return 0;
}
int find_first_end(int x,int lca){
    if (dep[x]<dep[lca]) return 0;
    while (x!=lca&&!ed[x]) x=fa[x];
    if (ed[x]) return ed[x];
    else return 0;
}
void tarjan(int p){
    dfn[p]=low[p]=++dft;
    s.push(p); ins[p]=1;
    for (auto i:ng[p]){
        if (!dfn[i]){
            tarjan(i);
            low[p]=min(low[p],low[i]);
        }
        else if (ins[i]&&dfn[i]<dfn[p])
            low[p]=min(low[p],dfn[i]);
    }
    if (low[p]==dfn[p]){
        nscc++;
        for (int x=0;x!=p;s.pop()){
            x=s.top(); ins[x]=0;
            scc[nscc].push_back(x);
        }
    }
}
void reset(){
    nscc=0; dft=0;
    while (!s.empty()) s.pop();
    for (int i=0;i<=n+5;i++){
        fa[i]=0; dfn[i]=0; low[i]=0; st[i]=0; 
        dep[i]=0; ins[i]=0; ed[i]=0;
        ng[i].clear();
        scc[i].clear();
    }
    for (int i=0;i<=n+5;i++){
        g[i].clear();
    }
}
signed main(){
    fast
    int q; cin>>q;
    while (q--){
        reset();
        cin>>n;
        for (int i=1;i<n;i++){
            int a,b; cin>>a>>b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        dfs(1,0);
        cin>>m;
        for (int i=1;i<=m;i++){
            cin>>pos[i].x>>pos[i].y;
            st[pos[i].x]=i;
            ed[pos[i].y]=i;
        }
        for (int i=1;i<=m;i++){
            int lca=LCA(pos[i].x,pos[i].y);
            int x=pos[i].x;
            while (x!=lca){
                if (ed[x]&&ed[x]!=i) ng[i].push_back(ed[x]);
                if (st[x]&&st[x]!=i) ng[st[x]].push_back(i);
                x=fa[x];
            }
            x=pos[i].y;
            while (x!=lca){
                if (ed[x]&&ed[x]!=i) ng[i].push_back(ed[x]);
                if (st[x]&&st[x]!=i) ng[st[x]].push_back(i); 
                x=fa[x];
            }
            if (st[lca]&&st[lca]!=i) ng[st[lca]].push_back(i);
            if (ed[lca]&&ed[lca]!=i) ng[i].push_back(ed[lca]);
        }
        for (int i=1;i<=m;i++){
            if (!dfn[i]) tarjan(i);
        }
        if (nscc==m) cout<<"Yes\n";
        else cout<<"No\n";
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8788 KB Output is correct
2 Correct 6 ms 8788 KB Output is correct
3 Correct 5 ms 8800 KB Output is correct
4 Correct 14 ms 9200 KB Output is correct
5 Correct 20 ms 9576 KB Output is correct
6 Correct 5 ms 8892 KB Output is correct
7 Correct 6 ms 8816 KB Output is correct
8 Correct 6 ms 9044 KB Output is correct
9 Correct 98 ms 14772 KB Output is correct
10 Correct 282 ms 24200 KB Output is correct
11 Correct 9 ms 8916 KB Output is correct
12 Correct 38 ms 9988 KB Output is correct
13 Correct 149 ms 85752 KB Output is correct
14 Correct 215 ms 112952 KB Output is correct
15 Runtime error 3734 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8788 KB Output is correct
2 Correct 5 ms 8788 KB Output is correct
3 Correct 6 ms 8804 KB Output is correct
4 Correct 5 ms 8820 KB Output is correct
5 Correct 6 ms 8788 KB Output is correct
6 Correct 6 ms 8816 KB Output is correct
7 Correct 6 ms 8788 KB Output is correct
8 Correct 6 ms 8808 KB Output is correct
9 Correct 8 ms 8824 KB Output is correct
10 Correct 7 ms 8788 KB Output is correct
11 Correct 6 ms 8888 KB Output is correct
12 Correct 6 ms 8808 KB Output is correct
13 Correct 6 ms 8788 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8788 KB Output is correct
2 Correct 5 ms 8788 KB Output is correct
3 Correct 6 ms 8804 KB Output is correct
4 Correct 5 ms 8820 KB Output is correct
5 Correct 6 ms 8788 KB Output is correct
6 Correct 6 ms 8816 KB Output is correct
7 Correct 6 ms 8788 KB Output is correct
8 Correct 6 ms 8808 KB Output is correct
9 Correct 8 ms 8824 KB Output is correct
10 Correct 7 ms 8788 KB Output is correct
11 Correct 6 ms 8888 KB Output is correct
12 Correct 6 ms 8808 KB Output is correct
13 Correct 6 ms 8788 KB Output is correct
14 Correct 4 ms 8804 KB Output is correct
15 Correct 5 ms 8784 KB Output is correct
16 Correct 5 ms 8784 KB Output is correct
17 Correct 6 ms 8788 KB Output is correct
18 Correct 6 ms 8876 KB Output is correct
19 Correct 5 ms 8800 KB Output is correct
20 Correct 6 ms 8788 KB Output is correct
21 Correct 6 ms 8880 KB Output is correct
22 Correct 6 ms 8812 KB Output is correct
23 Correct 5 ms 8788 KB Output is correct
24 Correct 6 ms 8800 KB Output is correct
25 Correct 8 ms 8884 KB Output is correct
26 Correct 5 ms 8788 KB Output is correct
27 Correct 6 ms 8808 KB Output is correct
28 Correct 5 ms 8800 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8788 KB Output is correct
2 Correct 5 ms 8788 KB Output is correct
3 Correct 6 ms 8804 KB Output is correct
4 Correct 5 ms 8820 KB Output is correct
5 Correct 6 ms 8788 KB Output is correct
6 Correct 6 ms 8816 KB Output is correct
7 Correct 6 ms 8788 KB Output is correct
8 Correct 6 ms 8808 KB Output is correct
9 Correct 8 ms 8824 KB Output is correct
10 Correct 7 ms 8788 KB Output is correct
11 Correct 6 ms 8888 KB Output is correct
12 Correct 6 ms 8808 KB Output is correct
13 Correct 6 ms 8788 KB Output is correct
14 Correct 4 ms 8804 KB Output is correct
15 Correct 5 ms 8784 KB Output is correct
16 Correct 5 ms 8784 KB Output is correct
17 Correct 6 ms 8788 KB Output is correct
18 Correct 6 ms 8876 KB Output is correct
19 Correct 5 ms 8800 KB Output is correct
20 Correct 6 ms 8788 KB Output is correct
21 Correct 6 ms 8880 KB Output is correct
22 Correct 6 ms 8812 KB Output is correct
23 Correct 5 ms 8788 KB Output is correct
24 Correct 6 ms 8800 KB Output is correct
25 Correct 8 ms 8884 KB Output is correct
26 Correct 5 ms 8788 KB Output is correct
27 Correct 6 ms 8808 KB Output is correct
28 Correct 5 ms 8800 KB Output is correct
29 Correct 7 ms 9172 KB Output is correct
30 Correct 6 ms 8916 KB Output is correct
31 Correct 7 ms 8976 KB Output is correct
32 Correct 6 ms 8788 KB Output is correct
33 Correct 6 ms 8876 KB Output is correct
34 Correct 6 ms 8820 KB Output is correct
35 Correct 10 ms 8916 KB Output is correct
36 Correct 7 ms 8812 KB Output is correct
37 Correct 6 ms 8808 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8788 KB Output is correct
2 Correct 5 ms 8788 KB Output is correct
3 Correct 6 ms 8804 KB Output is correct
4 Correct 5 ms 8820 KB Output is correct
5 Correct 6 ms 8788 KB Output is correct
6 Correct 6 ms 8816 KB Output is correct
7 Correct 6 ms 8788 KB Output is correct
8 Correct 6 ms 8808 KB Output is correct
9 Correct 8 ms 8824 KB Output is correct
10 Correct 7 ms 8788 KB Output is correct
11 Correct 6 ms 8888 KB Output is correct
12 Correct 6 ms 8808 KB Output is correct
13 Correct 6 ms 8788 KB Output is correct
14 Correct 4 ms 8804 KB Output is correct
15 Correct 5 ms 8784 KB Output is correct
16 Correct 5 ms 8784 KB Output is correct
17 Correct 6 ms 8788 KB Output is correct
18 Correct 6 ms 8876 KB Output is correct
19 Correct 5 ms 8800 KB Output is correct
20 Correct 6 ms 8788 KB Output is correct
21 Correct 6 ms 8880 KB Output is correct
22 Correct 6 ms 8812 KB Output is correct
23 Correct 5 ms 8788 KB Output is correct
24 Correct 6 ms 8800 KB Output is correct
25 Correct 8 ms 8884 KB Output is correct
26 Correct 5 ms 8788 KB Output is correct
27 Correct 6 ms 8808 KB Output is correct
28 Correct 5 ms 8800 KB Output is correct
29 Correct 7 ms 9172 KB Output is correct
30 Correct 6 ms 8916 KB Output is correct
31 Correct 7 ms 8976 KB Output is correct
32 Correct 6 ms 8788 KB Output is correct
33 Correct 6 ms 8876 KB Output is correct
34 Correct 6 ms 8820 KB Output is correct
35 Correct 10 ms 8916 KB Output is correct
36 Correct 7 ms 8812 KB Output is correct
37 Correct 6 ms 8808 KB Output is correct
38 Correct 94 ms 14704 KB Output is correct
39 Correct 280 ms 24172 KB Output is correct
40 Correct 61 ms 12988 KB Output is correct
41 Correct 30 ms 10732 KB Output is correct
42 Correct 52 ms 12900 KB Output is correct
43 Correct 24 ms 10704 KB Output is correct
44 Correct 11 ms 9428 KB Output is correct
45 Correct 47 ms 17996 KB Output is correct
46 Correct 48 ms 18008 KB Output is correct
47 Correct 79 ms 20860 KB Output is correct
48 Correct 80 ms 20804 KB Output is correct
49 Correct 57 ms 18228 KB Output is correct
50 Correct 56 ms 18124 KB Output is correct
51 Correct 40 ms 18524 KB Output is correct
52 Correct 36 ms 18480 KB Output is correct
53 Correct 13 ms 9924 KB Output is correct
54 Correct 78 ms 18656 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8800 KB Output is correct
2 Correct 5 ms 8760 KB Output is correct
3 Correct 5 ms 8796 KB Output is correct
4 Correct 5 ms 8804 KB Output is correct
5 Correct 11 ms 8992 KB Output is correct
6 Correct 5 ms 8812 KB Output is correct
7 Correct 5 ms 8788 KB Output is correct
8 Correct 6 ms 8796 KB Output is correct
9 Correct 5 ms 8788 KB Output is correct
10 Correct 5 ms 8800 KB Output is correct
11 Correct 5 ms 8796 KB Output is correct
12 Correct 6 ms 8916 KB Output is correct
13 Correct 21 ms 9448 KB Output is correct
14 Correct 26 ms 9604 KB Output is correct
15 Correct 25 ms 9584 KB Output is correct
16 Correct 56 ms 19604 KB Output is correct
17 Correct 152 ms 33900 KB Output is correct
18 Correct 376 ms 81856 KB Output is correct
19 Correct 71 ms 20236 KB Output is correct
20 Correct 65 ms 20264 KB Output is correct
21 Correct 66 ms 20252 KB Output is correct
22 Correct 110 ms 32668 KB Output is correct
23 Correct 118 ms 32828 KB Output is correct
24 Correct 97 ms 32652 KB Output is correct
25 Correct 90 ms 32776 KB Output is correct
26 Correct 103 ms 32724 KB Output is correct
27 Correct 143 ms 34308 KB Output is correct
28 Correct 139 ms 41484 KB Output is correct
29 Correct 129 ms 35008 KB Output is correct
30 Correct 105 ms 29336 KB Output is correct
31 Correct 100 ms 29608 KB Output is correct
32 Correct 97 ms 27484 KB Output is correct
33 Correct 84 ms 29548 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8788 KB Output is correct
2 Correct 6 ms 8788 KB Output is correct
3 Correct 5 ms 8800 KB Output is correct
4 Correct 14 ms 9200 KB Output is correct
5 Correct 20 ms 9576 KB Output is correct
6 Correct 5 ms 8892 KB Output is correct
7 Correct 6 ms 8816 KB Output is correct
8 Correct 6 ms 9044 KB Output is correct
9 Correct 98 ms 14772 KB Output is correct
10 Correct 282 ms 24200 KB Output is correct
11 Correct 9 ms 8916 KB Output is correct
12 Correct 38 ms 9988 KB Output is correct
13 Correct 149 ms 85752 KB Output is correct
14 Correct 215 ms 112952 KB Output is correct
15 Runtime error 3734 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -