oj.uz

Submission #632066

# Submission time Handle Problem Language Result Execution time Memory
632066 2022-08-19T11:29:29 Z LittleCube Jail (JOI22_jail) C++14
5 / 100
 1706 ms 386020 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma target("avx,avx2,sse,sse2,ssse3,sse4,fma,tune=native")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int T, N, M, s[1200005], e[1200005], deg[6000005], fr[1200005], to[1200005], pre[1200005][21], ts;
pii io[1200005];
vector<int> E[1200005], topo[6000006]; 

inline int idx(int u, int p = 0, int type = -1)
{
	return (2 * p + 1 + type) * N + u;
}

inline void dfs(int u)
{
	io[u].F = ++ts;
	for(int p = 1; p <= 20; p++)
	{
		pre[u][p] = pre[pre[u][p - 1]][p - 1];
		topo[idx(u, 		  p-1, 0)].emplace_back(idx(u, p, 0));
		topo[idx(pre[u][p-1], p-1, 0)].emplace_back(idx(u, p, 0));
		topo[idx(u, p, 1)].emplace_back(idx(u, 			 p-1, 1));
		topo[idx(u, p, 1)].emplace_back(idx(pre[u][p-1], p-1, 1));
	}
	if(s[pre[u][0]])
		topo[s[pre[u][0]]].emplace_back(idx(u, 0, 0));
	if(e[pre[u][0]])
		topo[idx(u, 0, 1)].emplace_back(e[pre[u][0]]);

	for(int v : E[u])
		if(pre[u][0] != v)
		{
			pre[v][0] = u;
			dfs(v);
		}
	io[u].S = ts;
}
inline void addedge(int pos, int i)
{
	if(s[pos] && s[pos] != i)
		topo[s[pos]].emplace_back(i);
	if(e[pos] && e[pos] != i)
		topo[i].emplace_back(e[pos]);
}

inline bool isSubtree(int r, int c)
{
	return io[r].F <= io[c].F && io[c].S <= io[r].S;
}

inline int jump(int u, int v, int i)
{
	int lca = u;
	for(int p = 20; p >= 0; p--)
		if(!isSubtree(pre[u][p], v))
		{
			topo[i].emplace_back(idx(u, p, 1));
			topo[idx(u, p, 0)].emplace_back(i);
			// cout << u << ' ' << p << ' ' << i << '\n';
			u = pre[u][p];
		}
	return lca;
}


inline void solve()
{
	ts = 0;
	cin >> N;
	for(int i = 1; i <= N; i++)
	{
		pre[i][0] = s[i] = e[i] = 0;
		E[i].clear();
	}
	for(int i = 1; i < N; i++)
	{
		int u, v;
		cin >> u >> v;
		E[u].emplace_back(v);
		E[v].emplace_back(u);
	}
	
	for(int p = 0; p <= 20; p++)
		pre[1][p] = 1;

	cin >> M;
	
	for(int i = 1; i <= 42 * N; i++)
	{
		deg[i] = 0;
		topo[i].clear();
	}
	
	for(int i = 1; i <= M; i++)
	{
		cin >> fr[i] >> to[i];
		s[fr[i]] = i;
		e[to[i]] = i;
	}

	dfs(1);

	for(int i = 1; i <= M; i++)
	{
		int u = fr[i], v = to[i];
		addedge(u, i);
		addedge(v, i);

		if(pre[u][0] == v || pre[v][0] == u) continue;
		
		if(isSubtree(u, v))
			jump(v, u, i);
		else if(isSubtree(v, u))
			jump(u, v, i);
		else
		{	
			int lca = jump(u, v, i);
			jump(v, u, i);
			addedge(pre[lca][0], i);
		}
	}

	for(int i = 1; i <= 42 * N; i++)
		for(int j : topo[i])
		{	
			// cout << i << "->" << j << '\n';
			deg[j]++;
		}
	
	queue<int> q;
	for(int i = 1; i <= 42 * N; i++)
		if(deg[i] == 0)
			q.emplace(i);

	for(int t = 1; t <= 42 * N; t++)
	{
		if(q.empty())
		{
			cout << "No\n";
			return;
		}
		int u = q.front();
		q.pop();
		for(int v : topo[u])
		{
			deg[v]--;
			if(deg[v] == 0)
				q.emplace(v);
		}
	}
	cout << "Yes\n";
}



signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T;
	while(T--)
	{
		solve();
	}
}

Compilation message

jail.cpp:2: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    2 | #pragma target("avx,avx2,sse,sse2,ssse3,sse4,fma,tune=native")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 169420 KB Output is correct
2 Correct 86 ms 169424 KB Output is correct
3 Correct 94 ms 169420 KB Output is correct
4 Correct 164 ms 170224 KB Output is correct
5 Correct 276 ms 171408 KB Output is correct
6 Correct 94 ms 169976 KB Output is correct
7 Correct 97 ms 169904 KB Output is correct
8 Correct 116 ms 169920 KB Output is correct
9 Correct 641 ms 182348 KB Output is correct
10 Correct 1221 ms 368492 KB Output is correct
11 Correct 123 ms 169804 KB Output is correct
12 Correct 283 ms 171540 KB Output is correct
13 Correct 1635 ms 373208 KB Output is correct
14 Correct 1320 ms 372208 KB Output is correct
15 Correct 1706 ms 374792 KB Output is correct
16 Correct 1576 ms 386020 KB Output is correct
17 Correct 1393 ms 376476 KB Output is correct
18 Correct 1321 ms 375576 KB Output is correct
19 Correct 1395 ms 376476 KB Output is correct
20 Correct 1247 ms 376552 KB Output is correct
21 Correct 1061 ms 375700 KB Output is correct
22 Correct 1075 ms 371780 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 169412 KB Output is correct
2 Correct 90 ms 169404 KB Output is correct
3 Correct 99 ms 169948 KB Output is correct
4 Incorrect 97 ms 169932 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 169412 KB Output is correct
2 Correct 90 ms 169404 KB Output is correct
3 Correct 99 ms 169948 KB Output is correct
4 Incorrect 97 ms 169932 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 169412 KB Output is correct
2 Correct 90 ms 169404 KB Output is correct
3 Correct 99 ms 169948 KB Output is correct
4 Incorrect 97 ms 169932 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 169412 KB Output is correct
2 Correct 90 ms 169404 KB Output is correct
3 Correct 99 ms 169948 KB Output is correct
4 Incorrect 97 ms 169932 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 169384 KB Output is correct
2 Correct 114 ms 169400 KB Output is correct
3 Correct 91 ms 169344 KB Output is correct
4 Correct 88 ms 169392 KB Output is correct
5 Correct 121 ms 169640 KB Output is correct
6 Correct 100 ms 169928 KB Output is correct
7 Incorrect 95 ms 169852 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 169420 KB Output is correct
2 Correct 86 ms 169424 KB Output is correct
3 Correct 94 ms 169420 KB Output is correct
4 Correct 164 ms 170224 KB Output is correct
5 Correct 276 ms 171408 KB Output is correct
6 Correct 94 ms 169976 KB Output is correct
7 Correct 97 ms 169904 KB Output is correct
8 Correct 116 ms 169920 KB Output is correct
9 Correct 641 ms 182348 KB Output is correct
10 Correct 1221 ms 368492 KB Output is correct
11 Correct 123 ms 169804 KB Output is correct
12 Correct 283 ms 171540 KB Output is correct
13 Correct 1635 ms 373208 KB Output is correct
14 Correct 1320 ms 372208 KB Output is correct
15 Correct 1706 ms 374792 KB Output is correct
16 Correct 1576 ms 386020 KB Output is correct
17 Correct 1393 ms 376476 KB Output is correct
18 Correct 1321 ms 375576 KB Output is correct
19 Correct 1395 ms 376476 KB Output is correct
20 Correct 1247 ms 376552 KB Output is correct
21 Correct 1061 ms 375700 KB Output is correct
22 Correct 1075 ms 371780 KB Output is correct
23 Correct 94 ms 169412 KB Output is correct
24 Correct 90 ms 169404 KB Output is correct
25 Correct 99 ms 169948 KB Output is correct
26 Incorrect 97 ms 169932 KB Output isn't correct
27 Halted 0 ms 0 KB -