oj.uz

Submission #1110343

# Submission time Handle Problem Language Result Execution time Memory
1110343 2024-11-09T09:44:17 Z 8pete8 Jail (JOI22_jail) C++17
5 / 100
 21 ms 26616 KB 
#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=1e5+20000,inf=1e9,minf=-1e9,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,int x){
    t.update(tin[S[i]],{tin[T[i]],i},x);
    t.update(tin[T[i]],{tin[S[i]],i},x);
    t2.update(tin[S[i]],{tin[T[i]],i},x);
    t2.update(tin[T[i]],{tin[S[i]],i},x);
    t3.update(tin[T[i]],{i,i},x);
}
bool findcycle(int cur){
    if(on[cur])return 1;
    if(vis[cur])return 0;
    vis[cur]=on[cur]=1;
    vector<int>move;
    del(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;
        }
        go=t.qry(tin[adj[S[cur]][x]],tout[adj[S[cur]][x]]);
        if(go.f!=inf&&go.f!=minf&&go.f>tout[adj[S[cur]][x]]){
            if(on[go.s])return 1;
            move.pb(go.s);
            del(go.s,1);
        }
        else x++;
    }
    x=0;
    while(x<adj[S[cur]].size()){
        if(adj[S[cur]][x]==up[S[cur]][0]){
            x++;
            continue;
        }
        go=t2.qry(tin[adj[S[cur]][x]],tout[adj[S[cur]][x]]);
        
        if(go.f!=inf&&go.f!=minf&&go.f<tin[adj[S[cur]][x]]){
            if(on[go.s])return 1;
            move.pb(go.s);
            del(go.s,1);
        }
        else x++;
    }
    int curhvy=S[cur],node=lca(S[cur],T[cur]);
    while(hvyp[curhvy]!=hvyp[node]){
        go=t3.qry(tin[hvyp[curhvy]],tin[curhvy]);
        if(go.f!=inf&&go.f!=minf){
            if(on[go.s])return 1;
            move.pb(go.s);
            del(go.s,1);
        }
        
        else curhvy=up[hvyp[curhvy]][0];
    }
    while(1){
        go=t3.qry(tin[node],tin[curhvy]);
        if(go.f!=inf&&go.f!=minf){
            if(on[go.s])return 1;
            move.pb(go.s);
            del(go.s,1);
        }
        else break;
    }
    curhvy=T[cur];
    while(hvyp[curhvy]!=hvyp[node]){
        go=t3.qry(tin[hvyp[curhvy]],tin[curhvy]);
        if(go.f!=inf&&go.f!=minf){
            if(on[go.s])return 1;
            move.pb(go.s);
            del(go.s,1);
        }
        else curhvy=up[hvyp[curhvy]][0];
    }
    while(1){
        go=t3.qry(tin[node],tin[curhvy]);
        if(go.f!=inf&&go.f!=minf){
            if(on[go.s])return 1;
            move.pb(go.s);
            del(go.s,1);
        }
        else break;
    }
    del(cur,0);
    for(auto j:move){
        if(vis[j])continue;
        if(on[j])return 1;
        del(j,0);
        if(findcycle(j))return 1;
    }
    del(cur,1);
    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++)del(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)break;
    }
    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

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:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  137 | void del(int i,int x){
      |                     ^
jail.cpp:144:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  144 | bool findcycle(int cur){
      |                       ^
jail.cpp: In function 'bool findcycle(int)':
jail.cpp:152:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     while(x<adj[S[cur]].size()){
      |           ~^~~~~~~~~~~~~~~~~~~
jail.cpp:166:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     while(x<adj[S[cur]].size()){
      |           ~^~~~~~~~~~~~~~~~~~~
jail.cpp: At global scope:
jail.cpp:230:12: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  230 | void solve(){
      |            ^
jail.cpp: In function 'void solve()':
jail.cpp:257:36: warning: operation on 'vis[i]' may be undefined [-Wsequence-point]
  257 |         adj[i].clear(),on[i]=vis[i]=S[i]=T[i]=vis[i]=0;
      |                              ~~~~~~^~~~~~~~~~~~~~~~~~~
jail.cpp: At global scope:
jail.cpp:263:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  263 | 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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26448 KB Output is correct
2 Correct 5 ms 26420 KB Output is correct
3 Correct 5 ms 26448 KB Output is correct
4 Correct 13 ms 26448 KB Output is correct
5 Incorrect 21 ms 26520 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26448 KB Output is correct
2 Correct 6 ms 26448 KB Output is correct
3 Correct 6 ms 26448 KB Output is correct
4 Correct 7 ms 26448 KB Output is correct
5 Correct 6 ms 26448 KB Output is correct
6 Correct 6 ms 26448 KB Output is correct
7 Correct 6 ms 26464 KB Output is correct
8 Correct 6 ms 26448 KB Output is correct
9 Correct 8 ms 26448 KB Output is correct
10 Correct 5 ms 26448 KB Output is correct
11 Correct 5 ms 26448 KB Output is correct
12 Correct 5 ms 26456 KB Output is correct
13 Correct 5 ms 26448 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26448 KB Output is correct
2 Correct 6 ms 26448 KB Output is correct
3 Correct 6 ms 26448 KB Output is correct
4 Correct 7 ms 26448 KB Output is correct
5 Correct 6 ms 26448 KB Output is correct
6 Correct 6 ms 26448 KB Output is correct
7 Correct 6 ms 26464 KB Output is correct
8 Correct 6 ms 26448 KB Output is correct
9 Correct 8 ms 26448 KB Output is correct
10 Correct 5 ms 26448 KB Output is correct
11 Correct 5 ms 26448 KB Output is correct
12 Correct 5 ms 26456 KB Output is correct
13 Correct 5 ms 26448 KB Output is correct
14 Correct 5 ms 26448 KB Output is correct
15 Correct 5 ms 26448 KB Output is correct
16 Correct 6 ms 26448 KB Output is correct
17 Correct 5 ms 26448 KB Output is correct
18 Incorrect 6 ms 26448 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26448 KB Output is correct
2 Correct 6 ms 26448 KB Output is correct
3 Correct 6 ms 26448 KB Output is correct
4 Correct 7 ms 26448 KB Output is correct
5 Correct 6 ms 26448 KB Output is correct
6 Correct 6 ms 26448 KB Output is correct
7 Correct 6 ms 26464 KB Output is correct
8 Correct 6 ms 26448 KB Output is correct
9 Correct 8 ms 26448 KB Output is correct
10 Correct 5 ms 26448 KB Output is correct
11 Correct 5 ms 26448 KB Output is correct
12 Correct 5 ms 26456 KB Output is correct
13 Correct 5 ms 26448 KB Output is correct
14 Correct 5 ms 26448 KB Output is correct
15 Correct 5 ms 26448 KB Output is correct
16 Correct 6 ms 26448 KB Output is correct
17 Correct 5 ms 26448 KB Output is correct
18 Incorrect 6 ms 26448 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26448 KB Output is correct
2 Correct 6 ms 26448 KB Output is correct
3 Correct 6 ms 26448 KB Output is correct
4 Correct 7 ms 26448 KB Output is correct
5 Correct 6 ms 26448 KB Output is correct
6 Correct 6 ms 26448 KB Output is correct
7 Correct 6 ms 26464 KB Output is correct
8 Correct 6 ms 26448 KB Output is correct
9 Correct 8 ms 26448 KB Output is correct
10 Correct 5 ms 26448 KB Output is correct
11 Correct 5 ms 26448 KB Output is correct
12 Correct 5 ms 26456 KB Output is correct
13 Correct 5 ms 26448 KB Output is correct
14 Correct 5 ms 26448 KB Output is correct
15 Correct 5 ms 26448 KB Output is correct
16 Correct 6 ms 26448 KB Output is correct
17 Correct 5 ms 26448 KB Output is correct
18 Incorrect 6 ms 26448 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26448 KB Output is correct
2 Correct 5 ms 26292 KB Output is correct
3 Correct 5 ms 26448 KB Output is correct
4 Correct 5 ms 26460 KB Output is correct
5 Correct 13 ms 26504 KB Output is correct
6 Correct 5 ms 26448 KB Output is correct
7 Correct 5 ms 26616 KB Output is correct
8 Correct 5 ms 26448 KB Output is correct
9 Incorrect 5 ms 26464 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26448 KB Output is correct
2 Correct 5 ms 26420 KB Output is correct
3 Correct 5 ms 26448 KB Output is correct
4 Correct 13 ms 26448 KB Output is correct
5 Incorrect 21 ms 26520 KB Output isn't correct
6 Halted 0 ms 0 KB -