답안 #632412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
632412	2022-08-20T01:45:15 Z	LittleCube	Jail (JOI22_jail)	C++14	100 / 100	3044 ms	362252 KB

jail

#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 <= 17; 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)
{
	// cout << pos << ' ' << i << '\n';
	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)
{
	for(int p = 17; 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 u;
}


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 <= 17; p++)
		pre[1][p] = 1;
		
	cin >> M;
	
	for(int i = 1; i <= 36 * 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 <= 36 * N; i++)
		for(int j : topo[i])
		{	
			// cout << i << "->" << j << '\n';
			deg[j]++;
		}
	
	queue<int> q;
	for(int i = 1; i <= 36 * N; i++)
		if(deg[i] == 0)
			q.emplace(i);

	for(int t = 1; t <= 36 * 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

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	169456 KB	Output is correct
2	Correct	104 ms	169360 KB	Output is correct
3	Correct	100 ms	169480 KB	Output is correct
4	Correct	162 ms	170376 KB	Output is correct
5	Correct	235 ms	171404 KB	Output is correct
6	Correct	93 ms	169804 KB	Output is correct
7	Correct	104 ms	169984 KB	Output is correct
8	Correct	97 ms	169928 KB	Output is correct
9	Correct	553 ms	181068 KB	Output is correct
10	Correct	1062 ms	341596 KB	Output is correct
11	Correct	125 ms	169772 KB	Output is correct
12	Correct	256 ms	171568 KB	Output is correct
13	Correct	1452 ms	346300 KB	Output is correct
14	Correct	1152 ms	346560 KB	Output is correct
15	Correct	1589 ms	348784 KB	Output is correct
16	Correct	1491 ms	360844 KB	Output is correct
17	Correct	1192 ms	350692 KB	Output is correct
18	Correct	1127 ms	350412 KB	Output is correct
19	Correct	1188 ms	350720 KB	Output is correct
20	Correct	1084 ms	350640 KB	Output is correct
21	Correct	980 ms	349652 KB	Output is correct
22	Correct	882 ms	345920 KB	Output is correct

Subtask #2

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	95 ms	169420 KB	Output is correct
2	Correct	96 ms	169432 KB	Output is correct
3	Correct	104 ms	169864 KB	Output is correct
4	Correct	105 ms	169884 KB	Output is correct
5	Correct	107 ms	169916 KB	Output is correct
6	Correct	104 ms	169916 KB	Output is correct
7	Correct	117 ms	169916 KB	Output is correct
8	Correct	104 ms	169908 KB	Output is correct
9	Correct	102 ms	169856 KB	Output is correct
10	Correct	105 ms	169900 KB	Output is correct
11	Correct	102 ms	169832 KB	Output is correct
12	Correct	98 ms	169852 KB	Output is correct
13	Correct	104 ms	169796 KB	Output is correct

Subtask #3

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	95 ms	169420 KB	Output is correct
2	Correct	96 ms	169432 KB	Output is correct
3	Correct	104 ms	169864 KB	Output is correct
4	Correct	105 ms	169884 KB	Output is correct
5	Correct	107 ms	169916 KB	Output is correct
6	Correct	104 ms	169916 KB	Output is correct
7	Correct	117 ms	169916 KB	Output is correct
8	Correct	104 ms	169908 KB	Output is correct
9	Correct	102 ms	169856 KB	Output is correct
10	Correct	105 ms	169900 KB	Output is correct
11	Correct	102 ms	169832 KB	Output is correct
12	Correct	98 ms	169852 KB	Output is correct
13	Correct	104 ms	169796 KB	Output is correct
14	Correct	93 ms	169328 KB	Output is correct
15	Correct	92 ms	169388 KB	Output is correct
16	Correct	103 ms	169808 KB	Output is correct
17	Correct	109 ms	169908 KB	Output is correct
18	Correct	104 ms	169872 KB	Output is correct
19	Correct	93 ms	169440 KB	Output is correct
20	Correct	103 ms	169912 KB	Output is correct
21	Correct	102 ms	169804 KB	Output is correct
22	Correct	100 ms	169848 KB	Output is correct
23	Correct	94 ms	169424 KB	Output is correct
24	Correct	110 ms	169592 KB	Output is correct
25	Correct	103 ms	169892 KB	Output is correct
26	Correct	96 ms	169764 KB	Output is correct
27	Correct	102 ms	169872 KB	Output is correct
28	Correct	95 ms	169388 KB	Output is correct

Subtask #4

28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	95 ms	169420 KB	Output is correct
2	Correct	96 ms	169432 KB	Output is correct
3	Correct	104 ms	169864 KB	Output is correct
4	Correct	105 ms	169884 KB	Output is correct
5	Correct	107 ms	169916 KB	Output is correct
6	Correct	104 ms	169916 KB	Output is correct
7	Correct	117 ms	169916 KB	Output is correct
8	Correct	104 ms	169908 KB	Output is correct
9	Correct	102 ms	169856 KB	Output is correct
10	Correct	105 ms	169900 KB	Output is correct
11	Correct	102 ms	169832 KB	Output is correct
12	Correct	98 ms	169852 KB	Output is correct
13	Correct	104 ms	169796 KB	Output is correct
14	Correct	93 ms	169328 KB	Output is correct
15	Correct	92 ms	169388 KB	Output is correct
16	Correct	103 ms	169808 KB	Output is correct
17	Correct	109 ms	169908 KB	Output is correct
18	Correct	104 ms	169872 KB	Output is correct
19	Correct	93 ms	169440 KB	Output is correct
20	Correct	103 ms	169912 KB	Output is correct
21	Correct	102 ms	169804 KB	Output is correct
22	Correct	100 ms	169848 KB	Output is correct
23	Correct	94 ms	169424 KB	Output is correct
24	Correct	110 ms	169592 KB	Output is correct
25	Correct	103 ms	169892 KB	Output is correct
26	Correct	96 ms	169764 KB	Output is correct
27	Correct	102 ms	169872 KB	Output is correct
28	Correct	95 ms	169388 KB	Output is correct
29	Correct	104 ms	170016 KB	Output is correct
30	Correct	105 ms	170016 KB	Output is correct
31	Correct	110 ms	169928 KB	Output is correct
32	Correct	103 ms	169912 KB	Output is correct
33	Correct	102 ms	169900 KB	Output is correct
34	Correct	111 ms	169832 KB	Output is correct
35	Correct	103 ms	169756 KB	Output is correct
36	Correct	102 ms	169860 KB	Output is correct
37	Correct	97 ms	169848 KB	Output is correct

Subtask #5

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	95 ms	169420 KB	Output is correct
2	Correct	96 ms	169432 KB	Output is correct
3	Correct	104 ms	169864 KB	Output is correct
4	Correct	105 ms	169884 KB	Output is correct
5	Correct	107 ms	169916 KB	Output is correct
6	Correct	104 ms	169916 KB	Output is correct
7	Correct	117 ms	169916 KB	Output is correct
8	Correct	104 ms	169908 KB	Output is correct
9	Correct	102 ms	169856 KB	Output is correct
10	Correct	105 ms	169900 KB	Output is correct
11	Correct	102 ms	169832 KB	Output is correct
12	Correct	98 ms	169852 KB	Output is correct
13	Correct	104 ms	169796 KB	Output is correct
14	Correct	93 ms	169328 KB	Output is correct
15	Correct	92 ms	169388 KB	Output is correct
16	Correct	103 ms	169808 KB	Output is correct
17	Correct	109 ms	169908 KB	Output is correct
18	Correct	104 ms	169872 KB	Output is correct
19	Correct	93 ms	169440 KB	Output is correct
20	Correct	103 ms	169912 KB	Output is correct
21	Correct	102 ms	169804 KB	Output is correct
22	Correct	100 ms	169848 KB	Output is correct
23	Correct	94 ms	169424 KB	Output is correct
24	Correct	110 ms	169592 KB	Output is correct
25	Correct	103 ms	169892 KB	Output is correct
26	Correct	96 ms	169764 KB	Output is correct
27	Correct	102 ms	169872 KB	Output is correct
28	Correct	95 ms	169388 KB	Output is correct
29	Correct	104 ms	170016 KB	Output is correct
30	Correct	105 ms	170016 KB	Output is correct
31	Correct	110 ms	169928 KB	Output is correct
32	Correct	103 ms	169912 KB	Output is correct
33	Correct	102 ms	169900 KB	Output is correct
34	Correct	111 ms	169832 KB	Output is correct
35	Correct	103 ms	169756 KB	Output is correct
36	Correct	102 ms	169860 KB	Output is correct
37	Correct	97 ms	169848 KB	Output is correct
38	Correct	558 ms	181064 KB	Output is correct
39	Correct	996 ms	341640 KB	Output is correct
40	Correct	688 ms	182352 KB	Output is correct
41	Correct	771 ms	181612 KB	Output is correct
42	Correct	438 ms	181928 KB	Output is correct
43	Correct	774 ms	182176 KB	Output is correct
44	Correct	145 ms	171468 KB	Output is correct
45	Correct	2671 ms	339916 KB	Output is correct
46	Correct	2648 ms	339924 KB	Output is correct
47	Correct	1686 ms	337928 KB	Output is correct
48	Correct	1765 ms	338000 KB	Output is correct
49	Correct	1938 ms	340840 KB	Output is correct
50	Correct	1900 ms	340868 KB	Output is correct
51	Correct	1884 ms	340212 KB	Output is correct
52	Correct	1885 ms	340292 KB	Output is correct
53	Correct	242 ms	182592 KB	Output is correct
54	Correct	2738 ms	340576 KB	Output is correct

Subtask #6

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	99 ms	169440 KB	Output is correct
2	Correct	94 ms	169444 KB	Output is correct
3	Correct	92 ms	169436 KB	Output is correct
4	Correct	98 ms	169420 KB	Output is correct
5	Correct	122 ms	169720 KB	Output is correct
6	Correct	96 ms	169864 KB	Output is correct
7	Correct	103 ms	169872 KB	Output is correct
8	Correct	92 ms	169420 KB	Output is correct
9	Correct	99 ms	169516 KB	Output is correct
10	Correct	95 ms	169624 KB	Output is correct
11	Correct	92 ms	169388 KB	Output is correct
12	Correct	105 ms	169772 KB	Output is correct
13	Correct	197 ms	170668 KB	Output is correct
14	Correct	290 ms	171492 KB	Output is correct
15	Correct	249 ms	171556 KB	Output is correct
16	Correct	2743 ms	341568 KB	Output is correct
17	Correct	2631 ms	347016 KB	Output is correct
18	Correct	2875 ms	355532 KB	Output is correct
19	Correct	2768 ms	341852 KB	Output is correct
20	Correct	2772 ms	341916 KB	Output is correct
21	Correct	2720 ms	341876 KB	Output is correct
22	Correct	2714 ms	346468 KB	Output is correct
23	Correct	2318 ms	346560 KB	Output is correct
24	Correct	2832 ms	346448 KB	Output is correct
25	Correct	2789 ms	346564 KB	Output is correct
26	Correct	3044 ms	346396 KB	Output is correct
27	Correct	2784 ms	347012 KB	Output is correct
28	Correct	2639 ms	346988 KB	Output is correct
29	Correct	2596 ms	346936 KB	Output is correct
30	Correct	2820 ms	345380 KB	Output is correct
31	Correct	2850 ms	345300 KB	Output is correct
32	Correct	2752 ms	343380 KB	Output is correct
33	Correct	2628 ms	343176 KB	Output is correct

Subtask #7

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	169456 KB	Output is correct
2	Correct	104 ms	169360 KB	Output is correct
3	Correct	100 ms	169480 KB	Output is correct
4	Correct	162 ms	170376 KB	Output is correct
5	Correct	235 ms	171404 KB	Output is correct
6	Correct	93 ms	169804 KB	Output is correct
7	Correct	104 ms	169984 KB	Output is correct
8	Correct	97 ms	169928 KB	Output is correct
9	Correct	553 ms	181068 KB	Output is correct
10	Correct	1062 ms	341596 KB	Output is correct
11	Correct	125 ms	169772 KB	Output is correct
12	Correct	256 ms	171568 KB	Output is correct
13	Correct	1452 ms	346300 KB	Output is correct
14	Correct	1152 ms	346560 KB	Output is correct
15	Correct	1589 ms	348784 KB	Output is correct
16	Correct	1491 ms	360844 KB	Output is correct
17	Correct	1192 ms	350692 KB	Output is correct
18	Correct	1127 ms	350412 KB	Output is correct
19	Correct	1188 ms	350720 KB	Output is correct
20	Correct	1084 ms	350640 KB	Output is correct
21	Correct	980 ms	349652 KB	Output is correct
22	Correct	882 ms	345920 KB	Output is correct
23	Correct	95 ms	169420 KB	Output is correct
24	Correct	96 ms	169432 KB	Output is correct
25	Correct	104 ms	169864 KB	Output is correct
26	Correct	105 ms	169884 KB	Output is correct
27	Correct	107 ms	169916 KB	Output is correct
28	Correct	104 ms	169916 KB	Output is correct
29	Correct	117 ms	169916 KB	Output is correct
30	Correct	104 ms	169908 KB	Output is correct
31	Correct	102 ms	169856 KB	Output is correct
32	Correct	105 ms	169900 KB	Output is correct
33	Correct	102 ms	169832 KB	Output is correct
34	Correct	98 ms	169852 KB	Output is correct
35	Correct	104 ms	169796 KB	Output is correct
36	Correct	93 ms	169328 KB	Output is correct
37	Correct	92 ms	169388 KB	Output is correct
38	Correct	103 ms	169808 KB	Output is correct
39	Correct	109 ms	169908 KB	Output is correct
40	Correct	104 ms	169872 KB	Output is correct
41	Correct	93 ms	169440 KB	Output is correct
42	Correct	103 ms	169912 KB	Output is correct
43	Correct	102 ms	169804 KB	Output is correct
44	Correct	100 ms	169848 KB	Output is correct
45	Correct	94 ms	169424 KB	Output is correct
46	Correct	110 ms	169592 KB	Output is correct
47	Correct	103 ms	169892 KB	Output is correct
48	Correct	96 ms	169764 KB	Output is correct
49	Correct	102 ms	169872 KB	Output is correct
50	Correct	95 ms	169388 KB	Output is correct
51	Correct	104 ms	170016 KB	Output is correct
52	Correct	105 ms	170016 KB	Output is correct
53	Correct	110 ms	169928 KB	Output is correct
54	Correct	103 ms	169912 KB	Output is correct
55	Correct	102 ms	169900 KB	Output is correct
56	Correct	111 ms	169832 KB	Output is correct
57	Correct	103 ms	169756 KB	Output is correct
58	Correct	102 ms	169860 KB	Output is correct
59	Correct	97 ms	169848 KB	Output is correct
60	Correct	558 ms	181064 KB	Output is correct
61	Correct	996 ms	341640 KB	Output is correct
62	Correct	688 ms	182352 KB	Output is correct
63	Correct	771 ms	181612 KB	Output is correct
64	Correct	438 ms	181928 KB	Output is correct
65	Correct	774 ms	182176 KB	Output is correct
66	Correct	145 ms	171468 KB	Output is correct
67	Correct	2671 ms	339916 KB	Output is correct
68	Correct	2648 ms	339924 KB	Output is correct
69	Correct	1686 ms	337928 KB	Output is correct
70	Correct	1765 ms	338000 KB	Output is correct
71	Correct	1938 ms	340840 KB	Output is correct
72	Correct	1900 ms	340868 KB	Output is correct
73	Correct	1884 ms	340212 KB	Output is correct
74	Correct	1885 ms	340292 KB	Output is correct
75	Correct	242 ms	182592 KB	Output is correct
76	Correct	2738 ms	340576 KB	Output is correct
77	Correct	99 ms	169440 KB	Output is correct
78	Correct	94 ms	169444 KB	Output is correct
79	Correct	92 ms	169436 KB	Output is correct
80	Correct	98 ms	169420 KB	Output is correct
81	Correct	122 ms	169720 KB	Output is correct
82	Correct	96 ms	169864 KB	Output is correct
83	Correct	103 ms	169872 KB	Output is correct
84	Correct	92 ms	169420 KB	Output is correct
85	Correct	99 ms	169516 KB	Output is correct
86	Correct	95 ms	169624 KB	Output is correct
87	Correct	92 ms	169388 KB	Output is correct
88	Correct	105 ms	169772 KB	Output is correct
89	Correct	197 ms	170668 KB	Output is correct
90	Correct	290 ms	171492 KB	Output is correct
91	Correct	249 ms	171556 KB	Output is correct
92	Correct	2743 ms	341568 KB	Output is correct
93	Correct	2631 ms	347016 KB	Output is correct
94	Correct	2875 ms	355532 KB	Output is correct
95	Correct	2768 ms	341852 KB	Output is correct
96	Correct	2772 ms	341916 KB	Output is correct
97	Correct	2720 ms	341876 KB	Output is correct
98	Correct	2714 ms	346468 KB	Output is correct
99	Correct	2318 ms	346560 KB	Output is correct
100	Correct	2832 ms	346448 KB	Output is correct
101	Correct	2789 ms	346564 KB	Output is correct
102	Correct	3044 ms	346396 KB	Output is correct
103	Correct	2784 ms	347012 KB	Output is correct
104	Correct	2639 ms	346988 KB	Output is correct
105	Correct	2596 ms	346936 KB	Output is correct
106	Correct	2820 ms	345380 KB	Output is correct
107	Correct	2850 ms	345300 KB	Output is correct
108	Correct	2752 ms	343380 KB	Output is correct
109	Correct	2628 ms	343176 KB	Output is correct
110	Correct	301 ms	171880 KB	Output is correct
111	Correct	251 ms	171448 KB	Output is correct
112	Correct	1695 ms	350960 KB	Output is correct
113	Correct	1912 ms	340904 KB	Output is correct
114	Correct	1316 ms	350460 KB	Output is correct
115	Correct	790 ms	344760 KB	Output is correct
116	Correct	2889 ms	348020 KB	Output is correct
117	Correct	2722 ms	357996 KB	Output is correct
118	Correct	2757 ms	340512 KB	Output is correct
119	Correct	2769 ms	340616 KB	Output is correct
120	Correct	213 ms	184448 KB	Output is correct
121	Correct	2870 ms	347440 KB	Output is correct
122	Correct	2826 ms	347636 KB	Output is correct
123	Correct	1814 ms	341380 KB	Output is correct
124	Correct	1482 ms	341328 KB	Output is correct
125	Correct	1779 ms	342008 KB	Output is correct
126	Correct	1823 ms	362252 KB	Output is correct
127	Correct	1692 ms	351672 KB	Output is correct
128	Correct	1689 ms	351764 KB	Output is correct
129	Correct	1937 ms	351772 KB	Output is correct
130	Correct	1668 ms	351652 KB	Output is correct