Submission #561248

#	Time	Username	Problem	Language	Result	Execution time	Memory
561248		wiwiho	Jail (JOI22_jail)	C++14	61 / 100	5061 ms	263688 KiB

jail

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define pob pop_back()
#define mp make_pair
#define F first
#define S second
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

int n;
vector<vector<int>> g;
vector<vector<int>> pass;

void init(){
    g.clear();
    g.resize(n + 1);
    pass.clear();
    pass.resize(n + 1);
}

bool dfs(int now, int p, int to, int id){
    if(now == to){
        pass[now].eb(id);
        return true;
    }
    for(int i : g[now]){
        if(i == p) continue;
        if(dfs(i, now, to, id)){
            pass[now].eb(id);
            return true;
        }
    }
    return false;
}

void solve(){
    
    cin >> n;
    init();

    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        g[u].eb(v);
        g[v].eb(u);
    }

    int m;
    cin >> m;
    vector<int> s(m + 1), t(m + 1);
    for(int i = 1; i <= m; i++){
        cin >> s[i] >> t[i];
        dfs(s[i], s[i], t[i], i);
    }

    vector<vector<int>> tg(m + 1);
    vector<int> in(m + 1);
    for(int i = 1; i <= m; i++){
        for(int j : pass[s[i]]){
            if(i == j) continue;
            in[j]++;
            tg[i].eb(j);
        }
        for(int j : pass[t[i]]){
            if(i == j) continue;
            in[i]++;
            tg[j].eb(i);
        }
    }

    queue<int> q;
    for(int i = 1; i <= m; i++){
        if(in[i] == 0) q.push(i);
    }
    int cnt = 0;
    while(!q.empty()){
        int now = q.front();
        q.pop();
        cnt++;
        for(int i : tg[now]){
            in[i]--;
            if(in[i] == 0){
                q.push(i);
            }
        }
    }
    
    if(cnt == m) cout << "Yes\n";
    else cout << "No\n";

}

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

    int T;
    cin >> T;
    while(T--) solve();

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23