Submission #582476

#	Time	Username	Problem	Language	Result	Execution time	Memory
582476		Antekb	Jail (JOI22_jail)	C++14	0 / 100	5061 ms	22688 KiB

jail

#include<bits/stdc++.h>

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")

#define st first
#define nd second
#define pb(x) push_back(x)
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)

using namespace std;

///~~~~~~~~~~~~~~~~~~~~~~~~~~

template <typename H, typename T> 
ostream& operator<<(ostream& os, pair<H, T> m){
	return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H> 
ostream& operator<<(ostream& os, vector<H> V){
	os<<"{";
	for(int i=0; i<V.size(); i++){
		if(i)os<<" ";
		os<<V[i];
	}
	os<<"}";
	return os;
}

void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);

///~~~~~~~~~~~~~~~~~~~~~~~~~

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;

#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N=(1<<17), INF=1e9+5, mod=1e9+7, M=3<<17;
vector<int> E[N];
int par[N], dep[N], siz[N], pre[N], post[N], pocz[N];
int wsk;
void dfs(int v){
	siz[v]=1;
	for(int u:E[v])if(u!=par[v]){
		par[u]=v;
		dep[u]=dep[v]+1;
		dfs(u);
		siz[v]+=siz[u];
	}
	for(int &u:E[v])if(E[v][0]==par[v] || siz[E[v][0]]<siz[u])swap(u, E[v][0]);
}
void dfs2(int v){
	pre[v]=wsk++;
	for(int u:E[v]){
		if(u!=par[v]){
			if(u==E[v][0])pocz[u]=pocz[v];
			else pocz[u]=u;
			dfs2(u);
		}
	}
	post[v]=wsk;
}
vector<int> E2[N+N+N];
int d[N+N+N];
void ae2(int l, int r, int kto){
	//cout<<l<<" "<<r<<" "<<kto-N-N<<"a\n";
	for(l+=N, r+=N; l<r; l>>=1, r>>=1){
		if(l&1)E2[kto].push_back(l++);
		if(r&1)E2[kto].push_back(--r);
	}
}
void ae(int u, int v, int kto){
	//cout<<u<<" "<<v<<" "<<kto-N-N<<"\n";
	bool b=1;
	while(true){
		//cout<<u<<" "<<v<<endl;
		assert(u && v);
		//if(dep[u]>dep[v])swap(u, v);
		if(pre[pocz[u]]<pre[pocz[v]]){
			if(pocz[u]==pocz[v]){
				assert(false);
				ae2(pre[pocz[u]]+b, pre[pocz[v]]+1, kto);
				break;
			}
			else{
				ae2(pre[pocz[v]], pre[v]+1, kto);
				v=par[pocz[v]];
			}
		}
		else{
			if(pocz[u]==pocz[v]){
				//cout<<"\nw\n";
				if(pre[u]>pre[v])ae2(pre[v], pre[u]+1-b, kto);
				else ae2(pre[u]+b, pre[v]+1, kto);
				break;
			}
			else{
				ae2(pre[pocz[u]], pre[u], kto);
				u=par[pocz[u]];
			}
			b=0;
		}
	}
}
bool acyc(){
	for(int i=0; i<M; i++)for(int j:E2[i]){
		d[j]++;
		//if(i!=j/2)cout<<i/N<<","<<i%N<<" "<<j/N<<","<<j%N<<"e\n";
	}
	vector<int> V;
	for(int i=0; i<M; i++)if(d[i]==0)V.push_back(i);
	for(int i=0; i<V.size(); i++){
		int v=V[i];
		for(int u:E2[v]){
			if(!--d[u])V.push_back(u);
		}
	}
	return V.size()==M;
}
int main(){
	//BOOST;
	int q;
	cin>>q;
	pocz[1]=1;
	while(q--){
	for(int i=2; i<N+N; i++)E2[i/2].push_back(i);
	int n, m;
	cin>>n;
	for(int i=1; i<n; i++){
		int u, v;
		cin>>u>>v;
		E[u].push_back(v);
		E[v].push_back(u);
	}
	dfs(1);
	dfs2(1);
	for(int i=1; i<=n; i++)
	{
		//cout<<i<<" "<<dep[i]<<" "<<par[i]<<" "<<pre[i]<<" "<<pocz[i]<<"\n";
	}
	cin>>m;
	for(int i=0; i<m; i++){
		int u, v;
		cin>>u>>v;
		ae(u, v, N+N+i);
		E2[N+pre[u]].push_back(N+N+i);
	}
	if(acyc())cout<<"Yes\n";
	else cout<<"No\n";
	for(int i=0; i<M; i++)d[i]=0, E2[i].clear();
	for(int i=0; i<N; i++)E[i].clear();
	wsk=0;
	}
}

Compilation message (stderr)

jail.cpp: In function 'bool acyc()':
jail.cpp:131:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23