oj.uz

Submission #560933

# Submission time Handle Problem Language Result Execution time Memory
560933 2022-05-12T05:16:52 Z 8e7 Jail (JOI22_jail) C++17
0 / 100
 12 ms 6100 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 120005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn], g[maxn];
int anc[18][maxn], dep[maxn], deg[maxn], c[2][maxn], rig[maxn];
pii ed[maxn];
void dfs(int n, int par, int d) {
	anc[0][n] = par;
	dep[n] = d;	
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n, d + 1);
		}
	}
}
int main() {
	io
	int T;
	cin >> T;
	while (T--) {

		int n;
		cin >> n;
		for (int i = 1;i <= n;i++) {
			adj[i].clear();
			g[i].clear();
			deg[i] = 0;
			c[0][i] = c[1][i] = 0;
			rig[i] = 0;
		}
		for (int i = 0;i < n - 1;i++) {
			int u,v;
			cin >> u >> v;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		dfs(1, 0, 0);
		for (int i = 1;i < 18;i++) {
			for (int j = 1;j <= n;j++) anc[i][j] = anc[i-1][anc[i-1][j]];
		}
		int m;
		cin >> m;
		auto addedge = [&] (int u, int v) {
			//debug("edge", u, v);
			g[u].push_back(v);
			deg[v]++;
		};
		for (int i = 1;i <= m;i++) {
			int u, v;
			cin >> u >> v;
			if (u < v) c[0][u]++, c[0][v]--, rig[u] = v;
			else c[1][v]++, c[1][u]--, rig[v] = u;
			ed[i] = {u, v};
		}
		bool poss = 1;
		int cur = 0;
		for (int i = 1;i <= n;i++) {
			c[0][i] += c[0][i-1], c[1][i] += c[1][i-1];
			if (c[0][i] && c[1][i]) {
				poss = 0;
				break;
			}
			if (rig[i] && rig[i] < cur) {
				poss = 0;
				break;
			}
			cur = rig[i];
		}
		cout << (poss ? "Yes" : "No") << "\n";	
	}
}

Compilation message

jail.cpp: In function 'int main()':
jail.cpp:60:8: warning: variable 'addedge' set but not used [-Wunused-but-set-variable]
   60 |   auto addedge = [&] (int u, int v) {
      |        ^~~~~~~

Subtask #1
0 / 5.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 Incorrect 12 ms 6088 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 4 ms 5972 KB Output is correct
3 Incorrect 4 ms 6100 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 4 ms 5972 KB Output is correct
3 Incorrect 4 ms 6100 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 4 ms 5972 KB Output is correct
3 Incorrect 4 ms 6100 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 4 ms 5972 KB Output is correct
3 Incorrect 4 ms 6100 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 8 ms 6060 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.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 Incorrect 12 ms 6088 KB Output isn't correct
5 Halted 0 ms 0 KB -