oj.uz

Submission #636217

# Submission time Handle Problem Language Result Execution time Memory
636217 2022-08-28T14:17:32 Z Yazan_Alattar Jail (JOI22_jail) C++14
0 / 100
 5000 ms 36912 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(x, 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;
        }
        timer = 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 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 13 ms 9704 KB Output is correct
5 Correct 24 ms 9788 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 43 ms 9828 KB Output is correct
9 Correct 1078 ms 13360 KB Output is correct
10 Correct 116 ms 36912 KB Output is correct
11 Correct 25 ms 9684 KB Output is correct
12 Correct 440 ms 9916 KB Output is correct
13 Execution timed out 5049 ms 36872 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 22 ms 9780 KB Output is correct
6 Incorrect 5 ms 9720 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 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 13 ms 9704 KB Output is correct
5 Correct 24 ms 9788 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 43 ms 9828 KB Output is correct
9 Correct 1078 ms 13360 KB Output is correct
10 Correct 116 ms 36912 KB Output is correct
11 Correct 25 ms 9684 KB Output is correct
12 Correct 440 ms 9916 KB Output is correct
13 Execution timed out 5049 ms 36872 KB Time limit exceeded
14 Halted 0 ms 0 KB -