oj.uz

Submission #718808

# Submission time Handle Problem Language Result Execution time Memory
718808 2023-04-04T23:52:38 Z Abrar_Al_Samit Jail (JOI22_jail) C++17
0 / 100
 17 ms 6016 KB 
#include<bits/stdc++.h>
using namespace std;

const int nax = 120001;
const int lg = 17;

vector<int>g[nax], t[nax];
int n, m;

int bed[nax], work[nax];
int sp[nax][lg];
int tt = 0, st[nax], en[nax];
int vis[nax], dep[nax];

void dfs(int v, int p = 1, int d = 0) {
	dep[v] = d;
	sp[v][0] = p;
	st[v] = tt++;
	for(int j=1; j<lg; ++j) {
		sp[v][j] = sp[sp[v][j-1]][j-1];
	}
	for(int u : g[v]) if(u!=p) {
		dfs(u, v, d+1);
	}
	en[v] = tt-1;
}
bool anc(int u, int v) {
	return st[u] <= st[v] && en[u] >= en[v];
}
int LIFT(int u, int v) {
	for(int j=lg-1; j>=0; --j) if(!anc(sp[u][j], v)) {
		u = sp[u][j];
	}
	if(!anc(u, v)) u = sp[u][0];
	return u;
}
bool lies(int u, int v, int lca, int x) {
	if(anc(lca, x)) {
		return anc(x, u) || anc(x, v);
	}
	return false;
}
int bond(int i, int j) {
	int lca1 = LIFT(bed[i], work[i]);
	int lca2 = LIFT(bed[j], work[j]);
	int len1 = dep[bed[i]] + dep[work[i]] - 2 * dep[lca1];
	int len2 = dep[bed[j]] + dep[work[j]] - 2 * dep[lca2];

	if(len1 < len2) {
		swap(i, j);
		swap(len1, len2);
		swap(lca1, lca2);
	}

	bool f = lies(bed[i], work[i], lca1, bed[j]);
	bool ff = lies(bed[i], work[i], lca1, work[j]);

	if(f && ff) return 1;
	if(f) {
		t[j].push_back(i);
		//cerr<<j<<' '<<i<<'\n';
	}
	if(ff) {
		t[i].push_back(j);
		//cerr<<i<<' '<<j<<'\n';
	}
	return 0;
}

int go(int v) {
	vis[v] = 1;
	for(int u : t[v]) {
		if(!vis[u]) {
			if(go(u)) return 1;
		} else {
			if(vis[u]==1) return 1;
		}
	}
	vis[v] = 2;
	return 0;
}
void PlayGround() {
	cin>>n;
	for(int i=1; i<=n; ++i) {
		g[i].clear(), t[i].clear(), tt = vis[i] = 0;
	}
	for(int i=0; i<n-1; ++i) {
		int u, v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1);

	cin>>m;
	for(int i=1; i<=m; ++i) {
		cin>>bed[i]>>work[i];
	}


	for(int i=1; i<=m; ++i) {
		for(int j=1; j<=m; ++j) if(i-j) {
			if(bond(i, j)) {
				cout<<"No\n";
				return;
			}
		}
	}

	for(int i=1; i<=m; ++i) if(!vis[i]) {
		if(go(i)) {
			cout<<"No\n";
			return;
		}
	}
	cout<<"Yes\n";

	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc;
	cin>>tc;
	while(tc--) {
		PlayGround();
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Incorrect 17 ms 6016 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5972 KB Output is correct
2 Correct 5 ms 5952 KB Output is correct
3 Incorrect 5 ms 5928 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5972 KB Output is correct
2 Correct 5 ms 5952 KB Output is correct
3 Incorrect 5 ms 5928 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5972 KB Output is correct
2 Correct 5 ms 5952 KB Output is correct
3 Incorrect 5 ms 5928 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5972 KB Output is correct
2 Correct 5 ms 5952 KB Output is correct
3 Incorrect 5 ms 5928 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Correct 3 ms 5972 KB Output is correct
5 Incorrect 13 ms 6000 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Incorrect 17 ms 6016 KB Output isn't correct
5 Halted 0 ms 0 KB -