Submission #994275

#	Time	Username	Problem	Language	Result	Execution time	Memory
994275		UVince	Jail (JOI22_jail)	C++17	0 / 100	803 ms	10892 KiB

jail

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

#define int ll
void solve();

signed 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 dolanc(){
    cin>>m;
    vector<int> lst(maxn,0);
    vector<int> rst(maxn,0);
    vector<pair<int,int>> srt;
    bool ans=true;
    for (int i = 1; i <= m; i++)
    {
        cin>>s[i]>>t[i];
        if (s[i]<t[i]) lst[t[i]]=i;
        else rst[t[i]]=i;
        if (s[i]<t[i]) srt.push_back({s[i], 0-t[i]});
        else srt.push_back({t[i], 0-s[i]});
    }
    sort(srt.begin(), srt.end());
    int mx=0;
    for (int i=1;i<=n;i++){
        if (lst[i]){
            if (mx>=i) ans=false;
        }
        else if (rst[i]){
            mx=max(mx, s[rst[i]]);
        }
    }

    stack<pair<int,int>> st;

    for (auto x: srt){
        int i=x.first;
        int j=0-x.second;
        while (!st.empty() && st.top().second<j) st.pop();
        if (!st.empty()) ans=false;
        st.push(make_pair(i,j));
    }

    if (ans){
        cout<<"Yes\n";
    }
    else {
        cout<<"No\n";
    }
}

void solve(){
    cin>>n;
    path.assign(maxn, {});
    num.assign(maxn,0);
    has.assign(maxn,false);
    g.assign(maxn,{});
    queue<int> q;
    bool lanc=true;
    for (int i = 1; i < n; i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
        if (a!=i || b!=i+1) lanc=false;
    }
    if (lanc){
        dolanc();
        return;
    }
    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
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23