Submission #1110296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110296		8pete8	Jail (JOI22_jail)	C++17	61 / 100	5073 ms	45032 KiB

jail

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5+5,inf=1e18,minf=-1e18,lg=30;
//#undef int
int n,k,m;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
vector<int>adj[mxn+10],adj2[mxn+10];
int S[mxn+10],T[mxn+10],SID[mxn+10],TID[mxn+10],target,root;
stack<int>st;
void addedge(int x,int y){
    if(x!=y)adj2[x].pb(y);
}
void dfs(int cur,int p){
    st.push(cur);
    if(cur==target){
        while(!st.empty()&&st.top()!=S[root]){
            if(SID[st.top()])addedge(SID[st.top()],root);
            if(TID[st.top()])addedge(root,TID[st.top()]);
            st.pop();
        }
        if(TID[st.top()])addedge(root,TID[st.top()]);
        return;
    }
    for(auto i:adj[cur])if(i!=p)dfs(i,cur);
    if(!st.empty())st.pop();
}
int vis[mxn+10],on[mxn+10];
bool findcycle(int cur){
    if(vis[cur])return 0;
    vis[cur]=on[cur]=1;
    for(auto i:adj2[cur]){
        if(on[i])return 1;
        if(!vis[i]&&findcycle(i))return 1;
    }
    on[cur]=0;
    return 0;
}
void solve(){
    //brute force
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    cin>>m;
    for(int i=1;i<=m;i++)cin>>S[i]>>T[i],SID[S[i]]=i,TID[T[i]]=i;
    for(int i=1;i<=m;i++){
        root=i;
        target=T[i];
        dfs(S[i],-1);
        while(!st.empty())st.pop();
    }
    bool yes=0;
    for(int i=1;i<=m;i++)yes|=findcycle(i);
    if(yes)cout<<"No\n";
    else cout<<"Yes\n";
    for(int i=1;i<=n;i++)adj[i].clear(),adj2[i].clear(),vis[i]=on[i]=S[i]=T[i]=SID[i]=TID[i]=0;
}
int32_t main(){
    fastio
    int t;cin>>t;
    while(t--)solve();
}
/*
let say the end point of prisoneri is on the path of prisonerj
then j has to move before i
j->i
if the start point of prisoner i is on the path of prisoner j
then i has to move before j
i->j
we can build a dag then see if theres a cycle

when dfs in dag to check for cycle a node is visited only once
we dont need to build the whole graph
just dfs and slowly check for adjacent node
if the adjacent node is not on the current path then just continue dfs
else if its on we found a cycle

after each dfs we can delete all visited node from the graph
will only use O(n*getnxt())
getnxt : 
find all prisoner that pass the start node
find all prisoner that has end point on path (start,end)->easy hld?
*/

Compilation message (stderr)

jail.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
jail.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void setIO(string name){
      |                       ^
jail.cpp:46:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   46 | void addedge(int x,int y){
      |                         ^
jail.cpp:49:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   49 | void dfs(int cur,int p){
      |                       ^
jail.cpp:64:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   64 | bool findcycle(int cur){
      |                       ^
jail.cpp:74:12: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   74 | void solve(){
      |            ^
jail.cpp:96:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   96 | int32_t main(){
      |              ^
jail.cpp: In function 'void setIO(std::string)':
jail.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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