oj.uz

Submission #582478

# Submission time Handle Problem Language Result Execution time Memory
582478 2022-06-23T22:21:22 Z Antekb Jail (JOI22_jail) C++14
0 / 100
 5000 ms 22264 KB 
#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];
int ile;
void ae2(int l, int r, int kto){
	ile+=r-l;
	//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){
	ile=-dep[u]-dep[v];
	//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;
		}
	}
	//cout<<ile<<" "<<min(dep[u], dep[v])<<endl;
	assert(ile+2*min(dep[u], dep[v])==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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19904 KB Output is correct
2 Correct 47 ms 21872 KB Output is correct
3 Correct 27 ms 19940 KB Output is correct
4 Incorrect 4187 ms 22140 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 19912 KB Output is correct
2 Correct 25 ms 19964 KB Output is correct
3 Incorrect 214 ms 21896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 19912 KB Output is correct
2 Correct 25 ms 19964 KB Output is correct
3 Incorrect 214 ms 21896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 19912 KB Output is correct
2 Correct 25 ms 19964 KB Output is correct
3 Incorrect 214 ms 21896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 19912 KB Output is correct
2 Correct 25 ms 19964 KB Output is correct
3 Incorrect 214 ms 21896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19912 KB Output is correct
2 Correct 33 ms 21796 KB Output is correct
3 Correct 42 ms 21860 KB Output is correct
4 Correct 29 ms 19912 KB Output is correct
5 Execution timed out 5061 ms 22264 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19904 KB Output is correct
2 Correct 47 ms 21872 KB Output is correct
3 Correct 27 ms 19940 KB Output is correct
4 Incorrect 4187 ms 22140 KB Output isn't correct
5 Halted 0 ms 0 KB -