oj.uz

Submission #669272

# Submission time Handle Problem Language Result Execution time Memory
669272 2022-12-06T07:15:39 Z fatemetmhr Jail (JOI22_jail) C++17
0 / 100
 641 ms 487968 KB 
// ~ Be Name Khoda ~

#include<bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const int lg    =  18;
const ll  inf   =  1e18;

int mark[maxn5 * lg], s[maxn5], t[maxn5], h[maxn5];
int par[lg][maxn5], newnode = 0, in[lg][maxn5], out[lg][maxn5];
vector <int> adj[maxn5], ed[maxn5 * lg];
bool cy = false;


void dfs_lca(int v){
    if(!out[0][v])
        out[0][v] = newnode++;
    if(!in[0][v])
        in[0][v] = newnode++;
    for(int i = 1; i < lg && par[i - 1][v] != -1; i++){
        par[i][v] = par[i - 1][par[i - 1][v]];
        out[i][v] = newnode++;
        in[i][v] = newnode++;
        ed[out[i][v]].pb(out[i - 1][v]);
        ed[out[i][v]].pb(out[i - 1][par[i - 1][v]]);
        ed[in[i - 1][v]].pb(in[i][v]);
        ed[in[i - 1][par[i - 1][v]]].pb(in[i][v]);
    }
    for(auto u : adj[v]) if(u != par[0][v]){
        par[0][u] = v;
        h[u] = h[v] + 1;
        dfs_lca(u);
    }
}

void dfs(int v){
    mark[v] = 1;
    for(auto u : ed[v]){
        if(mark[u] == 0)
            dfs(u);
        else if(mark[u] == 1)
            cy = true;
    }
    mark[v] = 2;
}

inline int lca(int a, int b){
    if(h[a] < h[b])
        swap(a, b);
    int d = h[a] - h[b];
    for(int i = 0; i < lg; i++) if((d >> i)&1)
        a = par[i][a];
    if(a == b)
        return a;
    for(int i = lg - 1; i >= 0; i--) if(par[i][a] != par[i][b]){
        a = par[i][a];
        b = par[i][b];
    }
    return par[0][a];
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    int tt; cin >> tt;
    while(tt--){
        int n; cin >> n;
        for(int i = 0; i < n; i++){
            adj[i].clear(); 
            for(int j = 0; j < lg; j++){
                par[j][i] = -1;
                in[j][i] = out[j][i] = 0;
            }
        }
        for(int i = 0; i < n - 1; i++){
            int a, b; cin >> a >> b;
            a--; b--;
            adj[a].pb(b);
            adj[b].pb(a);
        }
        int m; cin >> m;
        newnode = m;
        for(int i = 0; i < m; i++){
            cin >> s[i] >> t[i];
            s[i]--; t[i]--;
            if(!in[0][s[i]])
                in[0][s[i]] = newnode++;
            if(!out[0][t[i]])
                out[0][t[i]] = newnode++;
            ed[i].pb(in[0][s[i]]);
            ed[out[0][t[i]]].pb(i);
        }
        h[0] = 0;
        dfs_lca(0);
        for(int i = 0; i < m; i++){
            int v = s[i], u = t[i];
            if(v == u)
                continue;
            ed[i].pb(out[0][v]);
            ed[in[0][u]].pb(i);
            if(h[v] < h[u])
                swap(u, v);
            int c = lca(u, v);
            if(c == u)
                v = par[0][v];
            else{
                u = par[0][u];
                v = par[0][v];
            }
            int d = h[v] - h[u];
            for(int j = 0; j < lg; j++) if((d >> j)&1){
                ed[i].pb(out[j][v]);
                ed[in[j][v]].pb(i);
                v = par[j][v];
            }
            if(u == v)
                continue;
            for(int j = lg - 1; j >= 0; j--) if(par[j][v] != par[j][u]){
                ed[i].pb(out[j][v]);
                ed[i].pb(out[j][u]);
                ed[in[j][v]].pb(i);
                ed[in[j][u]].pb(i);
                v = par[j][v];
                u = par[j][u];
            }
            ed[i].pb(out[0][v]);
            ed[i].pb(out[0][par[0][v]]);
            ed[in[0][v]].pb(i);
            ed[in[0][par[0][v]]].pb(i);
        }
        cy = false;
        for(int i = 0; i < newnode; i++) if(!mark[i])
            dfs(i);
        cout << (cy ? "No\n" : "Yes\n");
        for(int i = 0; i < newnode; i++){
            ed[i].clear();
            mark[i] = 0;
        }
    }
}

/*
Why so fast...? 
Hold on...
Hold your breath...
Need anything else?

Nein, Kein Problem...
Das Leben war schon immer so grausam :)
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 89868 KB Output is correct
2 Correct 55 ms 89864 KB Output is correct
3 Correct 46 ms 89788 KB Output is correct
4 Correct 68 ms 90340 KB Output is correct
5 Correct 99 ms 90700 KB Output is correct
6 Correct 48 ms 90112 KB Output is correct
7 Correct 51 ms 90096 KB Output is correct
8 Correct 48 ms 90020 KB Output is correct
9 Correct 311 ms 98544 KB Output is correct
10 Runtime error 641 ms 487968 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 89804 KB Output is correct
2 Correct 55 ms 89804 KB Output is correct
3 Correct 51 ms 90108 KB Output is correct
4 Correct 49 ms 90088 KB Output is correct
5 Correct 49 ms 90076 KB Output is correct
6 Correct 47 ms 90060 KB Output is correct
7 Correct 51 ms 89992 KB Output is correct
8 Correct 55 ms 90012 KB Output is correct
9 Correct 48 ms 89956 KB Output is correct
10 Correct 46 ms 89996 KB Output is correct
11 Correct 53 ms 89980 KB Output is correct
12 Incorrect 45 ms 89960 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 89804 KB Output is correct
2 Correct 55 ms 89804 KB Output is correct
3 Correct 51 ms 90108 KB Output is correct
4 Correct 49 ms 90088 KB Output is correct
5 Correct 49 ms 90076 KB Output is correct
6 Correct 47 ms 90060 KB Output is correct
7 Correct 51 ms 89992 KB Output is correct
8 Correct 55 ms 90012 KB Output is correct
9 Correct 48 ms 89956 KB Output is correct
10 Correct 46 ms 89996 KB Output is correct
11 Correct 53 ms 89980 KB Output is correct
12 Incorrect 45 ms 89960 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 89804 KB Output is correct
2 Correct 55 ms 89804 KB Output is correct
3 Correct 51 ms 90108 KB Output is correct
4 Correct 49 ms 90088 KB Output is correct
5 Correct 49 ms 90076 KB Output is correct
6 Correct 47 ms 90060 KB Output is correct
7 Correct 51 ms 89992 KB Output is correct
8 Correct 55 ms 90012 KB Output is correct
9 Correct 48 ms 89956 KB Output is correct
10 Correct 46 ms 89996 KB Output is correct
11 Correct 53 ms 89980 KB Output is correct
12 Incorrect 45 ms 89960 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 89804 KB Output is correct
2 Correct 55 ms 89804 KB Output is correct
3 Correct 51 ms 90108 KB Output is correct
4 Correct 49 ms 90088 KB Output is correct
5 Correct 49 ms 90076 KB Output is correct
6 Correct 47 ms 90060 KB Output is correct
7 Correct 51 ms 89992 KB Output is correct
8 Correct 55 ms 90012 KB Output is correct
9 Correct 48 ms 89956 KB Output is correct
10 Correct 46 ms 89996 KB Output is correct
11 Correct 53 ms 89980 KB Output is correct
12 Incorrect 45 ms 89960 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 89764 KB Output is correct
2 Correct 50 ms 89868 KB Output is correct
3 Correct 51 ms 89804 KB Output is correct
4 Correct 43 ms 89852 KB Output is correct
5 Correct 53 ms 89952 KB Output is correct
6 Incorrect 49 ms 89980 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 89868 KB Output is correct
2 Correct 55 ms 89864 KB Output is correct
3 Correct 46 ms 89788 KB Output is correct
4 Correct 68 ms 90340 KB Output is correct
5 Correct 99 ms 90700 KB Output is correct
6 Correct 48 ms 90112 KB Output is correct
7 Correct 51 ms 90096 KB Output is correct
8 Correct 48 ms 90020 KB Output is correct
9 Correct 311 ms 98544 KB Output is correct
10 Runtime error 641 ms 487968 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -