oj.uz

Submission #632058

# Submission time Handle Problem Language Result Execution time Memory
632058 2022-08-19T11:04:44 Z LittleCube Jail (JOI22_jail) C++14
0 / 100
 143 ms 170108 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));

	}
	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);
			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;
	dfs(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;
		topo[idx(i)].emplace_back(idx(fr[i], 0, 0));
	   	topo[idx(to[i], 0, 1)].emplace_back(idx(i));	
	}
	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))
		{	
			v = pre[v][0];
			jump(v, u, i);
		}
		else if(isSubtree(v, u))
		{	
			u = pre[u][0];
			jump(u, v, i);
		}
		else
		{	
			u = pre[u][0], v = pre[v][0];
			jump(u, v, i);
			jump(v, u, 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 169448 KB Output is correct
2 Correct 98 ms 169384 KB Output is correct
3 Correct 90 ms 169396 KB Output is correct
4 Incorrect 143 ms 170108 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 169332 KB Output is correct
2 Correct 92 ms 169496 KB Output is correct
3 Incorrect 97 ms 169848 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 169332 KB Output is correct
2 Correct 92 ms 169496 KB Output is correct
3 Incorrect 97 ms 169848 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 169332 KB Output is correct
2 Correct 92 ms 169496 KB Output is correct
3 Incorrect 97 ms 169848 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 169332 KB Output is correct
2 Correct 92 ms 169496 KB Output is correct
3 Incorrect 97 ms 169848 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 169444 KB Output is correct
2 Correct 88 ms 169376 KB Output is correct
3 Correct 93 ms 169432 KB Output is correct
4 Correct 86 ms 169392 KB Output is correct
5 Incorrect 114 ms 169596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 169448 KB Output is correct
2 Correct 98 ms 169384 KB Output is correct
3 Correct 90 ms 169396 KB Output is correct
4 Incorrect 143 ms 170108 KB Output isn't correct
5 Halted 0 ms 0 KB -