oj.uz

답안 #636218

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
636218 2022-08-28T14:22:52 Z Yazan_Alattar Jail (JOI22_jail) C++14
0 / 100
 5000 ms 36876 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((x == s[i] || x == t[i]) && (y == s[j] || y == t[j])){
        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

# 결과 실행 시간 메모리 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 9684 KB Output is correct
5 Correct 23 ms 9784 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 7 ms 9816 KB Output is correct
8 Correct 45 ms 9812 KB Output is correct
9 Correct 1065 ms 13148 KB Output is correct
10 Correct 118 ms 36876 KB Output is correct
11 Correct 22 ms 9768 KB Output is correct
12 Correct 452 ms 9924 KB Output is correct
13 Execution timed out 5084 ms 36812 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 23 ms 9772 KB Output is correct
6 Incorrect 5 ms 9684 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 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 9684 KB Output is correct
5 Correct 23 ms 9784 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 7 ms 9816 KB Output is correct
8 Correct 45 ms 9812 KB Output is correct
9 Correct 1065 ms 13148 KB Output is correct
10 Correct 118 ms 36876 KB Output is correct
11 Correct 22 ms 9768 KB Output is correct
12 Correct 452 ms 9924 KB Output is correct
13 Execution timed out 5084 ms 36812 KB Time limit exceeded
14 Halted 0 ms 0 KB -