oj.uz

Submission #860370

# Submission time Handle Problem Language Result Execution time Memory
860370 2023-10-12T18:17:38 Z KiaRez Jail (JOI22_jail) C++17
49 / 100
 642 ms 624252 KB 
/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define set_dec(x)	                           cout << fixed << setprecision(x);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 2e5+23, lg = 18;
ll Mod = 1e9+7;
//ll Mod = 998244353;

inline ll MOD(ll a, ll mod=Mod) {
	a%=mod; (a<0)&&(a+=mod); return a;
}
inline ll max(ll a, ll b) {return (a>b ? a : b);}
inline ll min(ll a, ll b) {return (a<b ? a : b);}
inline ll abso(ll a) {return (a<0?-a:a);}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

struct Node {
	int deg;
	vector<int> adj;
	Node() {
		deg=0;
	}
} node[N*20];

int q, n, m, cnt, h[N], par[lg][N], s[N], t[N], rs[N], rt[N];
int fakes[lg][N], faket[lg][N];
vector<int> tree[N];

void add(int v, int u) {
	if(v==0 || u==0 || v==u) return;
	node[v].adj.pb(u);
	node[u].deg++;
}

void init(int v, int p=0) {
	par[0][v]=p, h[v]=h[p]+1;

	for(int i=1; i<lg; i++) {
		par[i][v] = par[i-1][par[i-1][v]];
	}
	for(int i=0; i<lg; i++) {
		fakes[i][v] = ++cnt;
		faket[i][v] = ++cnt;
	}
	int tmp = v;
	add(faket[0][v], rt[tmp]);
	tmp = par[0][v];
	add(faket[0][v], rt[tmp]);
	
	tmp = v;
	add(rs[tmp], fakes[0][v]);
	tmp = par[0][v];
	add(rs[tmp], fakes[0][v]);

	for(int i=1; i<lg; i++) {
		add(faket[i][v], faket[i-1][v]);
		add(faket[i][v], faket[i-1][par[i-1][v]]);

		add(fakes[i-1][v], fakes[i][v]);
		add(fakes[i-1][par[i-1][v]], fakes[i][v]);
	}

	for(int u : tree[v]) {
		if(u == p) continue;
		init(u, v);
	}
}

int getPar(int v, int dist) {
	for(int i=0; i<lg; i++) {
		if((dist>>i)%2) {
			v = par[i][v];
		}
	}
	return v;
}

int LCA(int v, int u) {
	if(h[u] < h[v]) swap(v,u);
	u = getPar(u, h[u]-h[v]);
	if(v == u) return v;

	for(int i=lg-1; i>=0; i--) {
		if(par[i][v] != par[i][u]) {
			v=par[i][v], u=par[i][u];
		}
	}
	return par[0][v];
}

void addPaths(int cnd, int v, int dist) {
	if(dist<0 || cnd==0 || v==0) return;
	//cout<<"addPath : "<<cnd<<' '<<v<<' '<<dist<<endl;
	if(dist == 0) {
		//add(cnd, rt[v]);
		add(rs[v], cnd);
		return;
	}
	for(int i=0; i<lg; i++) {
		if((dist>>i)%2==1) {
			//cout<<"edge : "<<cnd<<" ===> ("<<i<<", "<<v<<")\n";
			//add(cnd, faket[i][v]);
			//cout<<"edge : "<<cnd<<" <=== ("<<i<<", "<<v<<")\n";
			add(fakes[i][v], cnd);
			v = par[i][v];
		}
	}
	return;
}

void addPatht(int cnd, int v, int dist) {
	if(dist<0 || cnd==0 || v==0) return;
	//cout<<"addPath : "<<cnd<<' '<<v<<' '<<dist<<endl;
	if(dist == 0) {
		add(cnd, rt[v]);
		return;
	}
	for(int i=0; i<lg; i++) {
		if((dist>>i)%2==1) {
			//cout<<"edge : "<<cnd<<" ===> ("<<i<<", "<<v<<")\n";
			add(cnd, faket[i][v]);
			//cout<<"edge : "<<cnd<<" <=== ("<<i<<", "<<v<<")\n";
			//add(fakes[i][v], cnd);
			v = par[i][v];
		}
	}
	return;
}

void solve() {
	cin>>n;
	for(int v,u,i=1; i<n; i++) {
		cin>>v>>u;
		tree[v].pb(u); tree[u].pb(v);
	}
	cin>>m;
	for(int i=1; i<=m; i++) {
		cin>>s[i]>>t[i];
		rs[s[i]] = i;
		rt[t[i]] = i;
	}
	cnt = m;

	init(1);

	for(int i=1; i<=m; i++) {
		int lca = LCA(s[i], t[i]);
		//int ff = (s[i]==lca || t[i]==lca);
		addPaths(i, par[0][s[i]], h[par[0][s[i]]] - h[lca]);
		addPatht(i, s[i], h[s[i]] - h[lca] - (t[i]==lca));

		addPaths(i, t[i], h[t[i]] - h[lca] - (s[i]==lca));
		addPatht(i, par[0][t[i]], h[par[0][t[i]]] - h[lca]);
	}

	int cnt2=0;
	queue<int> q;
	for(int i=1; i<=cnt; i++) {
		if(node[i].deg == 0) q.push(i);
	}

	while(size(q)) {
		int v = q.front();
		q.pop();
		cnt2 ++;
		for(int u : node[v].adj) {
			node[u].deg--;
			if(node[u].deg==0) {
				q.push(u);
			}
		}
	}

	//fuck(cnt); fuck(cnt2);
	if(cnt2 == cnt) cout<<"Yes\n";
	else cout<<"No\n";
}

/*
node[N*20];
int q, n, m, cnt, h[N], par[lg][N], s[N], t[N], rs[N], rt[N];
int fakes[lg][N], faket[lg][N];
vector<int> tree[N];
*/

void reset() {
	for(int i=0; i<=n+2; i++) {
		h[i]=s[i]=t[i]=rs[i]=rt[i]=0;
		for(int j=0; j<lg; j++) {
			fakes[j][i]=faket[j][i]=0;
		}
		while(size(tree[i])) tree[i].pop_back();
	}

	for(int i=0; i<=cnt; i++) {
		node[i].deg=0;
		while(size(node[i].adj)) node[i].adj.pop_back();
	}
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>q;
	while(q--) {
		solve();
		reset();
	}

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 176464 KB Output is correct
2 Correct 31 ms 176476 KB Output is correct
3 Correct 32 ms 176608 KB Output is correct
4 Correct 69 ms 177068 KB Output is correct
5 Correct 111 ms 177236 KB Output is correct
6 Correct 42 ms 176720 KB Output is correct
7 Correct 40 ms 177240 KB Output is correct
8 Correct 36 ms 176732 KB Output is correct
9 Correct 307 ms 184920 KB Output is correct
10 Runtime error 615 ms 623860 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 176476 KB Output is correct
2 Correct 32 ms 176496 KB Output is correct
3 Correct 36 ms 176732 KB Output is correct
4 Correct 36 ms 176724 KB Output is correct
5 Correct 37 ms 176732 KB Output is correct
6 Correct 36 ms 176732 KB Output is correct
7 Correct 37 ms 176732 KB Output is correct
8 Correct 36 ms 176892 KB Output is correct
9 Correct 39 ms 176980 KB Output is correct
10 Correct 39 ms 176728 KB Output is correct
11 Correct 35 ms 176728 KB Output is correct
12 Correct 33 ms 176728 KB Output is correct
13 Correct 35 ms 176732 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 176476 KB Output is correct
2 Correct 32 ms 176496 KB Output is correct
3 Correct 36 ms 176732 KB Output is correct
4 Correct 36 ms 176724 KB Output is correct
5 Correct 37 ms 176732 KB Output is correct
6 Correct 36 ms 176732 KB Output is correct
7 Correct 37 ms 176732 KB Output is correct
8 Correct 36 ms 176892 KB Output is correct
9 Correct 39 ms 176980 KB Output is correct
10 Correct 39 ms 176728 KB Output is correct
11 Correct 35 ms 176728 KB Output is correct
12 Correct 33 ms 176728 KB Output is correct
13 Correct 35 ms 176732 KB Output is correct
14 Correct 31 ms 176568 KB Output is correct
15 Correct 31 ms 176480 KB Output is correct
16 Correct 36 ms 176916 KB Output is correct
17 Correct 38 ms 176980 KB Output is correct
18 Correct 36 ms 176936 KB Output is correct
19 Correct 31 ms 176588 KB Output is correct
20 Correct 37 ms 176720 KB Output is correct
21 Correct 36 ms 176720 KB Output is correct
22 Correct 35 ms 176976 KB Output is correct
23 Correct 31 ms 176768 KB Output is correct
24 Correct 32 ms 176732 KB Output is correct
25 Correct 36 ms 176848 KB Output is correct
26 Correct 32 ms 176720 KB Output is correct
27 Correct 36 ms 176732 KB Output is correct
28 Correct 32 ms 176476 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 176476 KB Output is correct
2 Correct 32 ms 176496 KB Output is correct
3 Correct 36 ms 176732 KB Output is correct
4 Correct 36 ms 176724 KB Output is correct
5 Correct 37 ms 176732 KB Output is correct
6 Correct 36 ms 176732 KB Output is correct
7 Correct 37 ms 176732 KB Output is correct
8 Correct 36 ms 176892 KB Output is correct
9 Correct 39 ms 176980 KB Output is correct
10 Correct 39 ms 176728 KB Output is correct
11 Correct 35 ms 176728 KB Output is correct
12 Correct 33 ms 176728 KB Output is correct
13 Correct 35 ms 176732 KB Output is correct
14 Correct 31 ms 176568 KB Output is correct
15 Correct 31 ms 176480 KB Output is correct
16 Correct 36 ms 176916 KB Output is correct
17 Correct 38 ms 176980 KB Output is correct
18 Correct 36 ms 176936 KB Output is correct
19 Correct 31 ms 176588 KB Output is correct
20 Correct 37 ms 176720 KB Output is correct
21 Correct 36 ms 176720 KB Output is correct
22 Correct 35 ms 176976 KB Output is correct
23 Correct 31 ms 176768 KB Output is correct
24 Correct 32 ms 176732 KB Output is correct
25 Correct 36 ms 176848 KB Output is correct
26 Correct 32 ms 176720 KB Output is correct
27 Correct 36 ms 176732 KB Output is correct
28 Correct 32 ms 176476 KB Output is correct
29 Correct 37 ms 176768 KB Output is correct
30 Correct 37 ms 176988 KB Output is correct
31 Correct 36 ms 176976 KB Output is correct
32 Correct 36 ms 176888 KB Output is correct
33 Correct 37 ms 176944 KB Output is correct
34 Correct 35 ms 176732 KB Output is correct
35 Correct 39 ms 176816 KB Output is correct
36 Correct 34 ms 176900 KB Output is correct
37 Correct 34 ms 176732 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 176476 KB Output is correct
2 Correct 32 ms 176496 KB Output is correct
3 Correct 36 ms 176732 KB Output is correct
4 Correct 36 ms 176724 KB Output is correct
5 Correct 37 ms 176732 KB Output is correct
6 Correct 36 ms 176732 KB Output is correct
7 Correct 37 ms 176732 KB Output is correct
8 Correct 36 ms 176892 KB Output is correct
9 Correct 39 ms 176980 KB Output is correct
10 Correct 39 ms 176728 KB Output is correct
11 Correct 35 ms 176728 KB Output is correct
12 Correct 33 ms 176728 KB Output is correct
13 Correct 35 ms 176732 KB Output is correct
14 Correct 31 ms 176568 KB Output is correct
15 Correct 31 ms 176480 KB Output is correct
16 Correct 36 ms 176916 KB Output is correct
17 Correct 38 ms 176980 KB Output is correct
18 Correct 36 ms 176936 KB Output is correct
19 Correct 31 ms 176588 KB Output is correct
20 Correct 37 ms 176720 KB Output is correct
21 Correct 36 ms 176720 KB Output is correct
22 Correct 35 ms 176976 KB Output is correct
23 Correct 31 ms 176768 KB Output is correct
24 Correct 32 ms 176732 KB Output is correct
25 Correct 36 ms 176848 KB Output is correct
26 Correct 32 ms 176720 KB Output is correct
27 Correct 36 ms 176732 KB Output is correct
28 Correct 32 ms 176476 KB Output is correct
29 Correct 37 ms 176768 KB Output is correct
30 Correct 37 ms 176988 KB Output is correct
31 Correct 36 ms 176976 KB Output is correct
32 Correct 36 ms 176888 KB Output is correct
33 Correct 37 ms 176944 KB Output is correct
34 Correct 35 ms 176732 KB Output is correct
35 Correct 39 ms 176816 KB Output is correct
36 Correct 34 ms 176900 KB Output is correct
37 Correct 34 ms 176732 KB Output is correct
38 Correct 220 ms 184912 KB Output is correct
39 Runtime error 642 ms 624252 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 176476 KB Output is correct
2 Correct 32 ms 176472 KB Output is correct
3 Correct 33 ms 176476 KB Output is correct
4 Correct 31 ms 176476 KB Output is correct
5 Correct 47 ms 176732 KB Output is correct
6 Correct 35 ms 176852 KB Output is correct
7 Correct 34 ms 176724 KB Output is correct
8 Correct 33 ms 176472 KB Output is correct
9 Correct 35 ms 176616 KB Output is correct
10 Correct 32 ms 176720 KB Output is correct
11 Correct 31 ms 176468 KB Output is correct
12 Correct 37 ms 176892 KB Output is correct
13 Correct 82 ms 177364 KB Output is correct
14 Correct 132 ms 177916 KB Output is correct
15 Correct 115 ms 177484 KB Output is correct
16 Runtime error 518 ms 611412 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 176464 KB Output is correct
2 Correct 31 ms 176476 KB Output is correct
3 Correct 32 ms 176608 KB Output is correct
4 Correct 69 ms 177068 KB Output is correct
5 Correct 111 ms 177236 KB Output is correct
6 Correct 42 ms 176720 KB Output is correct
7 Correct 40 ms 177240 KB Output is correct
8 Correct 36 ms 176732 KB Output is correct
9 Correct 307 ms 184920 KB Output is correct
10 Runtime error 615 ms 623860 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -