Submission #966053

#TimeUsernameProblemLanguageResultExecution timeMemory
966053shenfe1Jail (JOI22_jail)C++17
49 / 100
2304 ms1009772 KiB
#include <bits/stdc++.h> #pragma optimize("Ofast") #pragma target("avx2") using namespace std; #define ll long long #define ld long double #define pb push_back #define pf push_front #define pii pair<int,int> #define all(v) v.begin(),v.end() #define F first #define S second #define mem(a,i) memset(a,i,sizeof(a)) #define sz(s) (int)s.size() #define y1 yy #define ppb pop_back #define lb lower_bound #define ub upper_bound #define gcd(a,b) __gcd(a,b) #define in insert // #define int ll #define ull unsigned ll const int MAX=5e5+15; const int B=331; const int maxB=1000; const int N=104; const int block=450; const ll inf=1e13; const int mod=1e9+7; const int mod1=1e9+9; const ld eps=1e-9; int dx[8]={1,0,-1,0,1,-1,-1,1}; int dy[8]={0,1,0,-1,1,-1,1,-1}; int binpow(int a,int n){ if(!n)return 1; if(n%2==1)return a*binpow(a,n-1)%mod; int k=binpow(a,n/2); return k*k%mod; } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n,m; int cur; vector<int> g[MAX]; vector<int> g1[MAX*30]; int up[MAX][20]; int in[MAX][20],out[MAX][20]; int s[MAX],t[MAX]; vector<int> pos[MAX]; int tin[MAX],tout[MAX],timer; int d[MAX]; const int L=19; void add(int x,int y){ g1[x].pb(y); // cout<<x<<" "<<y<<"\n"; } void dfs(int v,int p=1){ tin[v]=++timer; up[v][0]=p; in[v][0]=++cur; out[v][0]=++cur; // cout<<"!!!! "<<v<<"\n"; // for(int x:pos[v]){ // if(x>0){ // add(in[v][0],x); // } // else{ // add(-x,out[v][0]); // } // } for(int i=1;i<=L;i++){ in[v][i]=++cur; out[v][i]=++cur; up[v][i]=up[up[v][i-1]][i-1]; add(out[v][i-1],out[v][i]); add(out[up[v][i-1]][i-1],out[v][i]); add(in[v][i],in[v][i-1]); add(in[v][i],in[up[v][i-1]][i-1]); } for(auto to:g[v]){ if(to==p)continue; d[to]=d[v]+1; dfs(to,v); } tout[v]=timer; } bool par(int u,int v){ return (tin[u]<=tin[v]&&tout[v]<=tout[u]); } void addin(int x,int y,int z){ // for(int i=L;i>=0;i--){ // if(d[up[x][i]]>d[y]){ // // cout<<x<<" "<<i<<" "<<in[x][i]<<"\n"; // add(z,in[x][i]); // x=up[x][i]; // } // } while(d[x]>=d[y]){ for(int f:pos[x]){ if(f>0&&f!=z)add(z,f); } if(x==1)break; x=up[x][0]; } } void addout(int x,int y,int z){ // for(int i=L;i>=0;i--){ // if(d[up[x][i]]>d[y]){ // add(out[x][i],z); // x=up[x][i]; // } // } while(d[x]>=d[y]){ for(int f:pos[x]){ if(f<0&&f!=-z)add(-f,z); } if(x==1)break; x=up[x][0]; } } int lca(int x,int y){ if(par(x,y))return x; if(par(y,x))return y; for(int i=L;i>=0;i--){ if(!par(up[x][i],y)){ x=up[x][i]; } } return up[x][0]; } bool bad; int use[MAX]; void dfs1(int v){ use[v]=1; for(auto to:g1[v]){ if(!use[to]){ // cout<<v<<" "<<to<<"\n"; dfs1(to); } else if(use[to]==1){ bad=1; // cout<<v<<" "<<to<<"\n"; } } use[v]=2; } void solve(){ cin>>n; bad=0; timer=0; for(int i=1;i<=cur;i++){ g1[i].clear(); use[i]=0; } for(int i=1;i<=n;i++){ g[i].clear(); pos[i].clear(); } for(int i=1;i<n;i++){ int x,y; cin>>x>>y; g[x].pb(y); g[y].pb(x); } cin>>m; for(int i=1;i<=m;i++){ cin>>s[i]>>t[i]; pos[s[i]].pb(i); pos[t[i]].pb(-i); } cur=m; dfs(1); // cout<<"\n"; for(int i=1;i<=m;i++){ int l=lca(s[i],t[i]); // cout<<l<<"\n"; addin(s[i],l,i); addin(t[i],l,i); addout(s[i],l,i); addout(t[i],l,i); } // return; for(int i=1;i<=cur;i++){ if(!use[i])dfs1(i); } if(bad)cout<<"No\n"; else cout<<"Yes\n"; } signed main(){ // freopen("triangles.in","r",stdin); // freopen("triangles.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // prec(); int t=1; cin>>t; while(t--)solve(); }

Compilation message (stderr)

jail.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
jail.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...