oj.uz

Submission #994183

# Submission time Handle Problem Language Result Execution time Memory
994183 2024-06-07T08:26:35 Z vjudge1 Jail (JOI22_jail) C++17
0 / 100
 5000 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

void solve();

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);

    int t=1;
    cin>>t;
    while (t--) solve();
    return 0;
}

const int maxn = 120'000;


vector<vector<int>> g(maxn);
vector<int> num(maxn);
int n,m;
vector<int> s(maxn),t(maxn);
vector<vector<int>> path(maxn);
vector<bool> has(maxn,false);

bool dfs (int v, int start, int par=-1){
    bool ret=false;
    if (v==t[start]) return true;
    for (int to : g[v]){
        if (to==par) continue;
        ret = ret || dfs(to, start, v);
        if (ret){
            num[to]++;
            path[start].push_back(to);
            break;
        }
    }
    return ret;
}

void solve(){
    cin>>n;
    path.assign(maxn, {});
    num.assign(maxn,0);
    has.assign(maxn,false);
    queue<int> q;
    for (int i = 1; i < n; i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cin>>m;
    for (int i = 1; i <= m; i++)
    {
        cin>>s[i]>>t[i];
        dfs(s[i], i);
        num[s[i]]++;
        q.push(i);
        has[s[i]]=true;
    }
    bool change=true;
    while (change){
        change=false;
        int sz=q.size();
        for (int i=0;i<sz;i++){
            int cur=q.front();
            q.pop();
            bool rem=num[t[cur]]-1;

            for (int j : path[cur]){
                if (has[j]) rem=true;
            }
            if (rem) {
                q.push(cur);
                continue;
            }
            change=true;
            has[s[cur]]=false;
            num[s[cur]]--;
            for (int j : path[cur]){
                num[j]--;
            }
        }
    }
    if (q.empty()){
        cout<<"Yes\n";
    }
    else {
        cout<<"No\n";
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 5 ms 7512 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Execution timed out 5094 ms 7516 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 2 ms 7456 KB Output is correct
3 Execution timed out 5069 ms 7516 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 2 ms 7456 KB Output is correct
3 Execution timed out 5069 ms 7516 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 2 ms 7456 KB Output is correct
3 Execution timed out 5069 ms 7516 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 2 ms 7456 KB Output is correct
3 Execution timed out 5069 ms 7516 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7516 KB Output is correct
2 Runtime error 560 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 5 ms 7512 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Execution timed out 5094 ms 7516 KB Time limit exceeded
5 Halted 0 ms 0 KB -