Submission #1110336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110336		8pete8	Jail (JOI22_jail)	C++17	77 / 100	5070 ms	127164 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];
int S[mxn+10],T[mxn+10],target,root;
int hvyp[mxn+10],sz[mxn+10],tin[mxn+10],tout[mxn+10],up[mxn+10][lg+1],h[mxn+10];
pii tmp;
struct segmx{
    pii v[2*mxn+10];
    priority_queue<pii>pq[mxn+10];
    void init(){for(int i=0;i<=2*n;i++)v[i]={minf,minf};}
    void update(int pos,pii val,int del){
        if(!del)pq[pos].push(val);
        else{
            if(pq[pos].top()==val)pq[pos].pop();
            else{
                tmp=pq[pos].top();
                pq[pos].pop();
                pq[pos].pop();
                pq[pos].push(tmp);
            }
        }
        if(!pq[pos].empty())v[pos+n]=pq[pos].top();
        else v[pos+n]={minf,minf};
        pos+=n;
        for(int i=pos;i>0;i>>=1)v[i>>1]=max(v[i],v[i^1]);
    }
    pii qry(int l,int r){
        pii ans={minf,minf};
        for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
            if(l&1)ans=max(ans,v[l++]);
            if(!(r&1))ans=max(ans,v[r--]);
        }
        return ans;
    }
}t;
struct segmn{
    pii v[2*mxn+10];
    priority_queue<pii,vector<pii>,greater<pii>>pq[mxn+10];
    void init(){for(int i=0;i<=2*n;i++)v[i]={inf,inf};}
    void update(int pos,pii val,int del){
        if(!del)pq[pos].push(val);
        else{
            if(pq[pos].top()==val)pq[pos].pop();
            else{
                tmp=pq[pos].top();
                pq[pos].pop();
                pq[pos].pop();
                pq[pos].push(tmp);
            }
        }
        if(!pq[pos].empty())v[pos+n]=pq[pos].top();
        else v[pos+n]={inf,inf};
        pos+=n;
        for(int i=pos;i>0;i>>=1)v[i>>1]=min(v[i],v[i^1]);
    }
    pii qry(int l,int r){
        pii ans={inf,inf};
        for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
            if(l&1)ans=min(ans,v[l++]);
            if(!(r&1))ans=min(ans,v[r--]);
        }
        return ans;
    }
}t2,t3;
int ct=0;
int lca(int x,int y){
    if(h[x]<h[y])swap(x,y);
    int k=h[x]-h[y];
    for(int i=0;i<=lg;i++)if(k&(1LL<<i))x=up[x][i];
    if(x==y)return x;
    for(int i=lg;i>=0;i--)if(up[x][i]!=up[y][i]){
        x=up[x][i],y=up[y][i];
    }
    return up[x][0];
}
void getsz(int cur,int p){sz[cur]=1;for(auto i:adj[cur])if(i!=p)getsz(i,cur),sz[cur]+=i;}
void dfs(int cur,int p){
    sz[cur]=1;
    tin[cur]=++ct;
    int hvy=0;
    for(auto i:adj[cur])if(i!=p&&sz[i]>sz[hvy])hvy=i;
    if(hvy){
        hvyp[hvy]=hvyp[cur];
        up[hvy][0]=cur,h[hvy]=h[cur]+1;
        sz[cur]+=sz[hvy];
        dfs(hvy,cur);
    }
    for(auto i:adj[cur])if(i!=p&&i!=hvy){
        up[i][0]=cur;
        h[i]=h[cur]+1;
        hvyp[i]=i;
        dfs(i,cur),sz[cur]+=sz[i];
    }
    tout[cur]=ct;
}
int on[mxn+10],vis[mxn+10];
void del(int i){
    t.update(tin[S[i]],{tin[T[i]],i},1);
    t.update(tin[T[i]],{tin[S[i]],i},1);
    t2.update(tin[S[i]],{tin[T[i]],i},1);
    t2.update(tin[T[i]],{tin[S[i]],i},1);
    t3.update(tin[T[i]],{i,i},1);
}
bool findcycle(int cur){
    if(on[cur])return 1;
    if(vis[cur])return 0;
    vis[cur]=on[cur]=1;
    pii go={inf,inf};
    int x=0;
    while(x<adj[S[cur]].size()){
        if(adj[S[cur]][x]==up[S[cur]][0]){
            x++;
            continue;
        }
        t.update(tin[T[cur]],{tin[S[cur]],cur},1);
        go=t.qry(tin[adj[S[cur]][x]],tout[adj[S[cur]][x]]);
        t.update(tin[T[cur]],{tin[S[cur]],cur},0);
       
        if(go.f!=inf&&go.f!=minf&&go.f>tout[adj[S[cur]][x]]){
            if(findcycle(go.s))return 1;
        }
        else x++;
    }
    x=0;
    while(x<adj[S[cur]].size()){
        if(adj[S[cur]][x]==up[S[cur]][0]){
            x++;
            continue;
        }
        t2.update(tin[T[cur]],{tin[S[cur]],cur},1);
        go=t2.qry(tin[adj[S[cur]][x]],tout[adj[S[cur]][x]]);
        t2.update(tin[T[cur]],{tin[S[cur]],cur},0);
        if(go.f!=inf&&go.f!=minf&&go.f<tin[adj[S[cur]][x]]){
            if(findcycle(go.s))return 1;
        }
        else x++;
    }
    int curhvy=S[cur],node=lca(S[cur],T[cur]);
    while(hvyp[curhvy]!=hvyp[node]){
        t3.update(tin[T[cur]],{cur,cur},1);
        go=t3.qry(tin[hvyp[curhvy]],tin[curhvy]);
        t3.update(tin[T[cur]],{cur,cur},0);
        if(go.f!=inf&&go.f!=minf){
            if(findcycle(go.s))return 1;
        }
        else curhvy=up[hvyp[curhvy]][0];
    }
    while(1){
        t3.update(tin[T[cur]],{cur,cur},1);
        go=t3.qry(tin[node],tin[curhvy]);
        t3.update(tin[T[cur]],{cur,cur},0);
        if(go.f!=inf&&go.f!=minf){
            if(findcycle(go.s))return 1;
        }
        else break;
    }
    curhvy=T[cur];
    while(hvyp[curhvy]!=hvyp[node]){
        t3.update(tin[T[cur]],{cur,cur},1);
        go=t3.qry(tin[hvyp[curhvy]],tin[curhvy]);
        t3.update(tin[T[cur]],{cur,cur},0);
        if(go.f!=inf&&go.f!=minf){
            if(findcycle(go.s))return 1;
        }
        else curhvy=up[hvyp[curhvy]][0];
    }
    while(1){
        t3.update(tin[T[cur]],{cur,cur},1);
        go=t3.qry(tin[node],tin[curhvy]);
        t3.update(tin[T[cur]],{cur,cur},0);
        if(go.f!=inf&&go.f!=minf){
            if(findcycle(go.s))return 1;
        }
        else break;
    }
    del(cur);
    on[cur]=0;
    return 0;
}
void solve(){
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    ct=0;
    cin>>m;
    for(int i=1;i<=m;i++)cin>>S[i]>>T[i];
    hvyp[1]=1;
    t.init();
    t2.init();
    t3.init();
    getsz(1,-1);
    dfs(1,-1);
    for(int i=1;i<=m;i++){
        t.update(tin[S[i]],{tin[T[i]],i},0);
        t.update(tin[T[i]],{tin[S[i]],i},0);
        t2.update(tin[S[i]],{tin[T[i]],i},0);
        t2.update(tin[T[i]],{tin[S[i]],i},0);
        t3.update(tin[T[i]],{i,i},0);
    }
    for(int j=0;j<=lg;j++)up[1][j]=1;
    for(int j=1;j<=lg;j++)for(int i=1;i<=n;i++)up[i][j]=up[up[i][j-1]][j-1];
    bool yes=0;
    for(int i=1;i<=m;i++)if(!vis[i]){
        yes|=findcycle(i);
    }
    if(yes)cout<<"No\n";
    else cout<<"Yes\n";
    for(int i=1;i<=n;i++){
        adj[i].clear(),on[i]=vis[i]=S[i]=T[i]=vis[i]=0;
        while(!t.pq[i].empty())t.pq[i].pop();
        while(!t2.pq[i].empty())t2.pq[i].pop();
        while(!t3.pq[i].empty())t3.pq[i].pop();
    }
}
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->how??{
    segtree on euler tour
    keep the counter part tin time
    when qry (l,r) just need to check if theres a node outside the range (l,r)
}
find all prisoner that has end point on path (start,end)->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:50:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   50 |     void init(){for(int i=0;i<=2*n;i++)v[i]={minf,minf};}
      |               ^
jail.cpp:51:40: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   51 |     void update(int pos,pii val,int del){
      |                                        ^
jail.cpp:67:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   67 |     pii qry(int l,int r){
      |                        ^
jail.cpp:79:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   79 |     void init(){for(int i=0;i<=2*n;i++)v[i]={inf,inf};}
      |               ^
jail.cpp:80:40: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   80 |     void update(int pos,pii val,int del){
      |                                        ^
jail.cpp:96:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   96 |     pii qry(int l,int r){
      |                        ^
jail.cpp:106:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  106 | int lca(int x,int y){
      |                    ^
jail.cpp:116:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  116 | void getsz(int cur,int p){sz[cur]=1;for(auto i:adj[cur])if(i!=p)getsz(i,cur),sz[cur]+=i;}
      |                         ^
jail.cpp:117:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  117 | void dfs(int cur,int p){
      |                       ^
jail.cpp:137:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  137 | void del(int i){
      |               ^
jail.cpp:144:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  144 | bool findcycle(int cur){
      |                       ^
jail.cpp: In function 'bool findcycle(long long int)':
jail.cpp:150:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     while(x<adj[S[cur]].size()){
      |           ~^~~~~~~~~~~~~~~~~~~
jail.cpp:165:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |     while(x<adj[S[cur]].size()){
      |           ~^~~~~~~~~~~~~~~~~~~
jail.cpp: At global scope:
jail.cpp:220:12: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  220 | void solve(){
      |            ^
jail.cpp: In function 'void solve()':
jail.cpp:252:36: warning: operation on 'vis[i]' may be undefined [-Wsequence-point]
  252 |         adj[i].clear(),on[i]=vis[i]=S[i]=T[i]=vis[i]=0;
      |                              ~~~~~~^~~~~~~~~~~~~~~~~~~
jail.cpp: At global scope:
jail.cpp:258:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  258 | 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: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23