Submission #887155

#	Time	Username	Problem	Language	Result	Execution time	Memory
887155		MilosMilutinovic	Jail (JOI22_jail)	C++14	49 / 100	484 ms	412648 KiB

jail

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=120005;
const int M=25*N;

int _,n,m,s[N],t[N],sidx[N][20],tidx[N][20],dep[N],p[N][20],sa[N],ta[N],deg[M];
VI e[N],g[M];

void dfs(int u,int f){
	dep[u]=dep[f]+1;
	p[u][0]=f;
	rep(i,1,20) p[u][i]=p[p[u][i-1]][i-1];
	for (int v:e[u]) {
		if (v==f) continue;
		dfs(v,u);
	}
}

int lca(int u,int v) {
	if (dep[u]>dep[v]) swap(u,v);
	per(i,0,20) if (dep[p[v][i]]>=dep[u]) v=p[v][i];
	if (u==v) return u;
	per(i,0,20) if (p[u][i]!=p[v][i]) u=p[u][i],v=p[v][i];
	return p[u][0];
}

void adds(int x,int k,int i) {
	if (k<0) return;
	k++;
	per(j,0,20) {
		if (k>>j&1) {
			g[i].pb(sidx[x][j]);
			x=p[x][j];
		}
	}
}

void addt(int x,int k,int i) {
	if (k<0) return;
	k++;
	per(j,0,20) {
		if (k>>j&1) {
			g[tidx[x][j]].pb(i);
			x=p[x][j];
		}
	}
}

bool solve() {
	scanf("%d",&n);
	rep(i,1,n) {
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].pb(v); 
		e[v].pb(u);
	}
	scanf("%d",&m);
	rep(i,1,m+1) scanf("%d%d",&s[i],&t[i]);
	dfs(1,1);
	int idx=m;
	rep(i,1,n+1) {
		sidx[i][0]=++idx;
		tidx[i][0]=++idx;
	}
	rep(j,1,20) {
		rep(i,1,n+1) {
			sidx[i][j]=++idx;
			tidx[i][j]=++idx;
			g[sidx[i][j]].pb(sidx[i][j-1]);
			g[sidx[i][j]].pb(sidx[p[i][j-1]][j-1]);
			g[tidx[i][j-1]].pb(tidx[i][j]);
			g[tidx[p[i][j-1]][j-1]].pb(tidx[i][j]);
		}
	}
	rep(i,1,n+1) sa[i]=ta[i]=0;
	rep(i,1,m+1) sa[s[i]]=i,ta[t[i]]=i;
	rep(i,1,n+1) {
		if (sa[i]!=0) g[sidx[i][0]].pb(sa[i]);
		if (ta[i]!=0) g[ta[i]].pb(tidx[i][0]);
	}
	rep(i,1,m+1) {
		int l=lca(s[i],t[i]);
		adds(t[i],dep[t[i]]-dep[l]-(s[i]==l?1:0),i);
		if (s[i]!=l) {
			adds(p[s[i]][0],dep[s[i]]-dep[l]-1,i);
		}
	}
	rep(i,1,m+1) {
		int l=lca(s[i],t[i]);
		addt(s[i],dep[s[i]]-dep[l]-(t[i]==l?1:0),i);
		if (t[i]!=l) {
			addt(p[t[i]][0],dep[t[i]]-dep[l]-1,i);
		}
	}
	rep(i,1,idx+1) {
		for (int j:g[i]) {
			deg[j]+=1;
		}
	}
	VI que;
	rep(i,1,idx+1) if (deg[i]==0) que.pb(i);
	rep(b,0,SZ(que)) {
		int x=que[b];
		for (int y:g[x]) {
			deg[y]-=1;
			if (deg[y]==0) que.pb(y);
		}
	}
	bool ok=true;
	rep(i,1,idx+1) {
		if (deg[i]!=0) ok=false;
		g[i].clear();
		deg[i]=0;
	}
	rep(i,1,n+1) {
		dep[i]=0;
		rep(j,0,20) {
			p[i][j]=0;
			sidx[i][j]=0;
			tidx[i][j]=0;
		}
		e[i].clear();
	}
	return ok;
}

int main() {
	for (scanf("%d",&_);_;_--) {
		printf(solve()?"Yes\n":"No\n");
	}
}

Compilation message (stderr)

jail.cpp: In function 'bool solve()':
jail.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
jail.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~
jail.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  scanf("%d",&m);
      |  ~~~~~^~~~~~~~~
jail.cpp:79:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  rep(i,1,m+1) scanf("%d%d",&s[i],&t[i]);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:149:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |  for (scanf("%d",&_);_;_--) {
      |       ~~~~~^~~~~~~~~

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