oj.uz

Submission #636215

# Submission time Handle Problem Language Result Execution time Memory
636215 2022-08-28T14:15:31 Z Yazan_Alattar Jail (JOI22_jail) C++14
0 / 100
 5000 ms 38852 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 200007;
const ll inf = 1e9;
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;

vector <int> adj[M], to[M];
int n, m, s[M], t[M], dep[M], anc[M][30], in[M], st[M], out[M], timer;

bool con(int i, int j){
    return st[i] <= st[j] && out[i] >= out[j];
}

int lca(int x, int y){
    if(x == y) return x;
    if(dep[x] > dep[y]) swap(x, y);

    for(int i = 18; i >= 0; --i) if(dep[anc[y][i]] >= dep[x]) y = anc[y][i];
    if(x == y) return x;

    for(int i = 18; i >= 0; --i) if(anc[x][i] != anc[y][i]){
        x = anc[x][i];
        y = anc[y][i];
    }

    return anc[x][0];
}

bool check(int i, int j){
    int x = lca(s[i], t[i]);
    int y = lca(s[j], t[j]);

    if((x != s[i] && x != t[i]) && (y != s[j] && y != t[j])){
        if(!con(s[i], s[j]) && !con(t[i], s[j]) && con(lca(s[i], t[i]), s[j])) return 0;
        if(!con(s[j], t[i]) && !con(t[j], t[i]) && con(lca(s[j], t[j]), t[i])) return 0;
    }
    else{
        if(con(s[i], s[j]) && con(s[i], t[j]) && !con(t[i], s[j]) && !con(t[i], t[j])) return 0;
        if(con(t[i], s[j]) && con(t[i], t[j]) && !con(s[i], s[j]) && !con(s[i], t[j])) return 0;

        if(con(s[j], s[i]) && con(s[j], t[i]) && !con(t[j], s[i]) && !con(t[j], t[i])) return 0;
        if(con(t[j], s[i]) && con(t[j], t[i]) && !con(s[j], s[i]) && !con(s[j], t[i])) return 0;

        if(con(t[i], s[j]) && !con(s[i], s[j]) && con(s[i], t[j])) return 0;
        if(con(t[j], s[i]) && !con(s[j], s[i]) && con(s[j], t[i])) return 0;
    }

    return 1;
}

void dfs(int node, int par){
    st[node] = ++timer;
    for(auto i : adj[node]) if(i != par){
        dep[i] = dep[node] + 1;
        anc[i][0] = node;
        dfs(i, node);
    }
    out[node] = ++timer;
    return;
}


int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q;
    cin >> q;
    while(q--){
        cin >> n;
        for(int i = 1; i < n; ++i){
            int x, y;
            cin >> x >> y;
            adj[x].pb(y);
            adj[y].pb(x);
        }

        dep[1] = 1;
        dfs(1, 0);

        for(int j = 1; j < 19; ++j)
            for(int i = 1; i <= n; ++i)
                anc[i][j] = anc[anc[i][j - 1]][j - 1];

        cin >> m;
        for(int i = 1; i <= m; ++i) cin >> s[i] >> t[i];

        for(int i = 1; i <= m; ++i){
            for(int j = 1; j <= m; ++j){
                if(i != j && !check(i, j)) to[j].pb(i), ++in[i];
                if(i != j && con(s[i], s[j]) && con(t[j], t[i])) to[j].pb(i), to[i].pb(j), ++in[i], ++in[j];
            }
        }

        queue <int> q;
        for(int i = 1; i <= m; ++i) if(!in[i]) q.push(i);

        int cnt = 0;
        while(!q.empty()){
            int node = q.front();
            q.pop();
            ++cnt;

            for(auto i : to[node]){
                --in[i];
                if(!in[i]) q.push(i);
            }
        }

        cout << (cnt != m ? "No\n" : "Yes\n");

        for(int i = 1; i <= n; ++i){
            adj[i].clear();
            to[i].clear();
            in[i] = 0;
        }
    }

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 15 ms 9784 KB Output is correct
5 Correct 34 ms 10284 KB Output is correct
6 Correct 6 ms 9744 KB Output is correct
7 Correct 6 ms 9736 KB Output is correct
8 Correct 50 ms 9932 KB Output is correct
9 Correct 1155 ms 13908 KB Output is correct
10 Correct 124 ms 38324 KB Output is correct
11 Correct 25 ms 9904 KB Output is correct
12 Correct 497 ms 10880 KB Output is correct
13 Execution timed out 5084 ms 38852 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Incorrect 8 ms 9768 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Incorrect 8 ms 9768 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Incorrect 8 ms 9768 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 7 ms 9812 KB Output is correct
4 Incorrect 8 ms 9768 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9732 KB Output is correct
2 Correct 7 ms 9736 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9704 KB Output is correct
5 Correct 23 ms 9684 KB Output is correct
6 Incorrect 6 ms 9824 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 15 ms 9784 KB Output is correct
5 Correct 34 ms 10284 KB Output is correct
6 Correct 6 ms 9744 KB Output is correct
7 Correct 6 ms 9736 KB Output is correct
8 Correct 50 ms 9932 KB Output is correct
9 Correct 1155 ms 13908 KB Output is correct
10 Correct 124 ms 38324 KB Output is correct
11 Correct 25 ms 9904 KB Output is correct
12 Correct 497 ms 10880 KB Output is correct
13 Execution timed out 5084 ms 38852 KB Time limit exceeded
14 Halted 0 ms 0 KB -