oj.uz

Submission #632073

# Submission time Handle Problem Language Result Execution time Memory
632073 2022-08-19T11:37:22 Z LittleCube Jail (JOI22_jail) C++14
5 / 100
 1744 ms 384884 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 89 ms 169452 KB Output is correct
2 Correct 85 ms 169428 KB Output is correct
3 Correct 85 ms 169432 KB Output is correct
4 Correct 171 ms 170152 KB Output is correct
5 Correct 267 ms 170648 KB Output is correct
6 Correct 95 ms 169912 KB Output is correct
7 Correct 95 ms 169948 KB Output is correct
8 Correct 96 ms 169896 KB Output is correct
9 Correct 629 ms 181208 KB Output is correct
10 Correct 1228 ms 366956 KB Output is correct
11 Correct 125 ms 169804 KB Output is correct
12 Correct 296 ms 170600 KB Output is correct
13 Correct 1652 ms 370976 KB Output is correct
14 Correct 1372 ms 371172 KB Output is correct
15 Correct 1744 ms 373616 KB Output is correct
16 Correct 1533 ms 384884 KB Output is correct
17 Correct 1487 ms 375304 KB Output is correct
18 Correct 1372 ms 374364 KB Output is correct
19 Correct 1307 ms 375328 KB Output is correct
20 Correct 1201 ms 375328 KB Output is correct
21 Correct 1033 ms 374444 KB Output is correct
22 Correct 1053 ms 370620 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 169448 KB Output is correct
2 Correct 88 ms 169380 KB Output is correct
3 Correct 97 ms 169888 KB Output is correct
4 Incorrect 100 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 91 ms 169448 KB Output is correct
2 Correct 88 ms 169380 KB Output is correct
3 Correct 97 ms 169888 KB Output is correct
4 Incorrect 100 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 91 ms 169448 KB Output is correct
2 Correct 88 ms 169380 KB Output is correct
3 Correct 97 ms 169888 KB Output is correct
4 Incorrect 100 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 91 ms 169448 KB Output is correct
2 Correct 88 ms 169380 KB Output is correct
3 Correct 97 ms 169888 KB Output is correct
4 Incorrect 100 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 86 ms 169364 KB Output is correct
2 Correct 91 ms 169448 KB Output is correct
3 Correct 87 ms 169448 KB Output is correct
4 Correct 88 ms 169444 KB Output is correct
5 Correct 124 ms 169668 KB Output is correct
6 Correct 93 ms 169924 KB Output is correct
7 Incorrect 94 ms 169924 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 169452 KB Output is correct
2 Correct 85 ms 169428 KB Output is correct
3 Correct 85 ms 169432 KB Output is correct
4 Correct 171 ms 170152 KB Output is correct
5 Correct 267 ms 170648 KB Output is correct
6 Correct 95 ms 169912 KB Output is correct
7 Correct 95 ms 169948 KB Output is correct
8 Correct 96 ms 169896 KB Output is correct
9 Correct 629 ms 181208 KB Output is correct
10 Correct 1228 ms 366956 KB Output is correct
11 Correct 125 ms 169804 KB Output is correct
12 Correct 296 ms 170600 KB Output is correct
13 Correct 1652 ms 370976 KB Output is correct
14 Correct 1372 ms 371172 KB Output is correct
15 Correct 1744 ms 373616 KB Output is correct
16 Correct 1533 ms 384884 KB Output is correct
17 Correct 1487 ms 375304 KB Output is correct
18 Correct 1372 ms 374364 KB Output is correct
19 Correct 1307 ms 375328 KB Output is correct
20 Correct 1201 ms 375328 KB Output is correct
21 Correct 1033 ms 374444 KB Output is correct
22 Correct 1053 ms 370620 KB Output is correct
23 Correct 91 ms 169448 KB Output is correct
24 Correct 88 ms 169380 KB Output is correct
25 Correct 97 ms 169888 KB Output is correct
26 Incorrect 100 ms 169932 KB Output isn't correct
27 Halted 0 ms 0 KB -