oj.uz

Submission #887155

# Submission time Handle Problem Language Result Execution time Memory
887155 2023-12-13T22:56:32 Z MilosMilutinovic Jail (JOI22_jail) C++14
49 / 100
 484 ms 412648 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 80464 KB Output is correct
2 Correct 17 ms 80476 KB Output is correct
3 Correct 18 ms 80604 KB Output is correct
4 Correct 55 ms 80988 KB Output is correct
5 Correct 97 ms 81488 KB Output is correct
6 Correct 21 ms 80988 KB Output is correct
7 Correct 22 ms 81028 KB Output is correct
8 Correct 26 ms 80988 KB Output is correct
9 Correct 172 ms 96212 KB Output is correct
10 Runtime error 484 ms 412568 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 80476 KB Output is correct
2 Correct 16 ms 80472 KB Output is correct
3 Correct 20 ms 81060 KB Output is correct
4 Correct 21 ms 81168 KB Output is correct
5 Correct 22 ms 81188 KB Output is correct
6 Correct 22 ms 81084 KB Output is correct
7 Correct 21 ms 80988 KB Output is correct
8 Correct 23 ms 81412 KB Output is correct
9 Correct 21 ms 80988 KB Output is correct
10 Correct 21 ms 81128 KB Output is correct
11 Correct 20 ms 80988 KB Output is correct
12 Correct 19 ms 80988 KB Output is correct
13 Correct 20 ms 80984 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 80476 KB Output is correct
2 Correct 16 ms 80472 KB Output is correct
3 Correct 20 ms 81060 KB Output is correct
4 Correct 21 ms 81168 KB Output is correct
5 Correct 22 ms 81188 KB Output is correct
6 Correct 22 ms 81084 KB Output is correct
7 Correct 21 ms 80988 KB Output is correct
8 Correct 23 ms 81412 KB Output is correct
9 Correct 21 ms 80988 KB Output is correct
10 Correct 21 ms 81128 KB Output is correct
11 Correct 20 ms 80988 KB Output is correct
12 Correct 19 ms 80988 KB Output is correct
13 Correct 20 ms 80984 KB Output is correct
14 Correct 18 ms 80476 KB Output is correct
15 Correct 17 ms 80472 KB Output is correct
16 Correct 21 ms 80988 KB Output is correct
17 Correct 22 ms 81164 KB Output is correct
18 Correct 21 ms 80988 KB Output is correct
19 Correct 18 ms 80644 KB Output is correct
20 Correct 22 ms 80988 KB Output is correct
21 Correct 22 ms 80988 KB Output is correct
22 Correct 21 ms 80984 KB Output is correct
23 Correct 17 ms 80476 KB Output is correct
24 Correct 18 ms 80732 KB Output is correct
25 Correct 23 ms 80984 KB Output is correct
26 Correct 18 ms 81116 KB Output is correct
27 Correct 22 ms 80988 KB Output is correct
28 Correct 20 ms 80472 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 80476 KB Output is correct
2 Correct 16 ms 80472 KB Output is correct
3 Correct 20 ms 81060 KB Output is correct
4 Correct 21 ms 81168 KB Output is correct
5 Correct 22 ms 81188 KB Output is correct
6 Correct 22 ms 81084 KB Output is correct
7 Correct 21 ms 80988 KB Output is correct
8 Correct 23 ms 81412 KB Output is correct
9 Correct 21 ms 80988 KB Output is correct
10 Correct 21 ms 81128 KB Output is correct
11 Correct 20 ms 80988 KB Output is correct
12 Correct 19 ms 80988 KB Output is correct
13 Correct 20 ms 80984 KB Output is correct
14 Correct 18 ms 80476 KB Output is correct
15 Correct 17 ms 80472 KB Output is correct
16 Correct 21 ms 80988 KB Output is correct
17 Correct 22 ms 81164 KB Output is correct
18 Correct 21 ms 80988 KB Output is correct
19 Correct 18 ms 80644 KB Output is correct
20 Correct 22 ms 80988 KB Output is correct
21 Correct 22 ms 80988 KB Output is correct
22 Correct 21 ms 80984 KB Output is correct
23 Correct 17 ms 80476 KB Output is correct
24 Correct 18 ms 80732 KB Output is correct
25 Correct 23 ms 80984 KB Output is correct
26 Correct 18 ms 81116 KB Output is correct
27 Correct 22 ms 80988 KB Output is correct
28 Correct 20 ms 80472 KB Output is correct
29 Correct 22 ms 81192 KB Output is correct
30 Correct 23 ms 81496 KB Output is correct
31 Correct 22 ms 81240 KB Output is correct
32 Correct 23 ms 81224 KB Output is correct
33 Correct 22 ms 80988 KB Output is correct
34 Correct 22 ms 80988 KB Output is correct
35 Correct 22 ms 80984 KB Output is correct
36 Correct 26 ms 81256 KB Output is correct
37 Correct 20 ms 80988 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 80476 KB Output is correct
2 Correct 16 ms 80472 KB Output is correct
3 Correct 20 ms 81060 KB Output is correct
4 Correct 21 ms 81168 KB Output is correct
5 Correct 22 ms 81188 KB Output is correct
6 Correct 22 ms 81084 KB Output is correct
7 Correct 21 ms 80988 KB Output is correct
8 Correct 23 ms 81412 KB Output is correct
9 Correct 21 ms 80988 KB Output is correct
10 Correct 21 ms 81128 KB Output is correct
11 Correct 20 ms 80988 KB Output is correct
12 Correct 19 ms 80988 KB Output is correct
13 Correct 20 ms 80984 KB Output is correct
14 Correct 18 ms 80476 KB Output is correct
15 Correct 17 ms 80472 KB Output is correct
16 Correct 21 ms 80988 KB Output is correct
17 Correct 22 ms 81164 KB Output is correct
18 Correct 21 ms 80988 KB Output is correct
19 Correct 18 ms 80644 KB Output is correct
20 Correct 22 ms 80988 KB Output is correct
21 Correct 22 ms 80988 KB Output is correct
22 Correct 21 ms 80984 KB Output is correct
23 Correct 17 ms 80476 KB Output is correct
24 Correct 18 ms 80732 KB Output is correct
25 Correct 23 ms 80984 KB Output is correct
26 Correct 18 ms 81116 KB Output is correct
27 Correct 22 ms 80988 KB Output is correct
28 Correct 20 ms 80472 KB Output is correct
29 Correct 22 ms 81192 KB Output is correct
30 Correct 23 ms 81496 KB Output is correct
31 Correct 22 ms 81240 KB Output is correct
32 Correct 23 ms 81224 KB Output is correct
33 Correct 22 ms 80988 KB Output is correct
34 Correct 22 ms 80988 KB Output is correct
35 Correct 22 ms 80984 KB Output is correct
36 Correct 26 ms 81256 KB Output is correct
37 Correct 20 ms 80988 KB Output is correct
38 Correct 159 ms 96228 KB Output is correct
39 Runtime error 399 ms 412648 KB Execution killed with signal 6
40 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 80476 KB Output is correct
2 Correct 17 ms 80520 KB Output is correct
3 Correct 17 ms 80472 KB Output is correct
4 Correct 17 ms 80476 KB Output is correct
5 Correct 35 ms 80824 KB Output is correct
6 Correct 19 ms 80988 KB Output is correct
7 Correct 20 ms 80988 KB Output is correct
8 Correct 19 ms 80476 KB Output is correct
9 Correct 18 ms 80548 KB Output is correct
10 Correct 18 ms 80984 KB Output is correct
11 Correct 17 ms 80472 KB Output is correct
12 Correct 21 ms 81140 KB Output is correct
13 Correct 76 ms 81432 KB Output is correct
14 Correct 123 ms 81744 KB Output is correct
15 Correct 99 ms 81492 KB Output is correct
16 Runtime error 365 ms 408140 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 80464 KB Output is correct
2 Correct 17 ms 80476 KB Output is correct
3 Correct 18 ms 80604 KB Output is correct
4 Correct 55 ms 80988 KB Output is correct
5 Correct 97 ms 81488 KB Output is correct
6 Correct 21 ms 80988 KB Output is correct
7 Correct 22 ms 81028 KB Output is correct
8 Correct 26 ms 80988 KB Output is correct
9 Correct 172 ms 96212 KB Output is correct
10 Runtime error 484 ms 412568 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -