Submission #894936

#	Time	Username	Problem	Language	Result	Execution time	Memory
894936		alexander707070	Jail (JOI22_jail)	C++14	61 / 100	5040 ms	32464 KiB

jail

#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

int n,m,q,a,b;
int s[MAXN],t[MAXN];
int start[MAXN],fin[MAXN],vis[MAXN];
bool dali;

vector<int> v[MAXN],g[MAXN];

void reset(){
    for(int i=1;i<=n;i++){
        v[i].clear();
        start[i]=fin[i]=0;
    }
    for(int i=1;i<=m;i++){
        g[i].clear(); vis[i]=0;
    }
    dali=false;
}

bool dfs(int x,int p,int y,int root){
    if(x==y)return true;

    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p)continue;
        if(dfs(v[x][i],x,y,root)){
            if(start[x]!=0 and start[x]!=root){
                g[start[x]].push_back(root);
            }
            if(fin[x]!=0 and fin[x]!=root){
                g[root].push_back(fin[x]);
            }

            return true;
        }
    }

    return false;
}

bool topsort(int x){
    vis[x]=1;

    for(int i=0;i<g[x].size();i++){
        if(vis[g[x][i]]==0 and !topsort(g[x][i]))return false;
        else if(vis[g[x][i]]==1)return false;
    }

    vis[x]=2;
    return true;
}

void solve(){

    cin>>n;
    for(int i=1;i<=n-1;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>s[i]>>t[i];
        start[s[i]]=i;
        fin[t[i]]=i;
    }

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

    for(int i=1;i<=m;i++){
        if(vis[i]==2 or vis[i]==1)continue;
        if(!topsort(i))dali=true;
    }

    if(dali)cout<<"No\n";
    else cout<<"Yes\n";

    reset();
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>q;
    while(q>0){
        reset();
        solve();
        q--;
    }

    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'bool dfs(int, int, int, int)':
jail.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
jail.cpp: In function 'bool topsort(int)':
jail.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<g[x].size();i++){
      |                 ~^~~~~~~~~~~~

• 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