답안 #635251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
635251	2022-08-25T18:02:40 Z	LittleCube	Jail (JOI22_jail)	C++17	100 / 100	3040 ms	347208 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[5400005], fr[1200005], to[1200005], pre[1200005][18], ts;
pii io[1200005];
vector<int> E[1200005], topo[5400006]; 

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();
	}
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	75 ms	155340 KB	Output is correct
2	Correct	71 ms	155244 KB	Output is correct
3	Correct	72 ms	155332 KB	Output is correct
4	Correct	153 ms	156008 KB	Output is correct
5	Correct	241 ms	156552 KB	Output is correct
6	Correct	90 ms	155688 KB	Output is correct
7	Correct	84 ms	155756 KB	Output is correct
8	Correct	86 ms	155740 KB	Output is correct
9	Correct	530 ms	165948 KB	Output is correct
10	Correct	1004 ms	329300 KB	Output is correct
11	Correct	119 ms	155536 KB	Output is correct
12	Correct	270 ms	156536 KB	Output is correct
13	Correct	1411 ms	333496 KB	Output is correct
14	Correct	1184 ms	333612 KB	Output is correct
15	Correct	1532 ms	335944 KB	Output is correct
16	Correct	1476 ms	347208 KB	Output is correct
17	Correct	1143 ms	337812 KB	Output is correct
18	Correct	1190 ms	336760 KB	Output is correct
19	Correct	1212 ms	337848 KB	Output is correct
20	Correct	1026 ms	337760 KB	Output is correct
21	Correct	904 ms	336664 KB	Output is correct
22	Correct	882 ms	333088 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	155360 KB	Output is correct
2	Correct	76 ms	155248 KB	Output is correct
3	Correct	81 ms	155788 KB	Output is correct
4	Correct	82 ms	155768 KB	Output is correct
5	Correct	85 ms	155740 KB	Output is correct
6	Correct	86 ms	155688 KB	Output is correct
7	Correct	84 ms	155700 KB	Output is correct
8	Correct	84 ms	155776 KB	Output is correct
9	Correct	85 ms	155796 KB	Output is correct
10	Correct	85 ms	155724 KB	Output is correct
11	Correct	84 ms	155720 KB	Output is correct
12	Correct	78 ms	155648 KB	Output is correct
13	Correct	79 ms	155644 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	155360 KB	Output is correct
2	Correct	76 ms	155248 KB	Output is correct
3	Correct	81 ms	155788 KB	Output is correct
4	Correct	82 ms	155768 KB	Output is correct
5	Correct	85 ms	155740 KB	Output is correct
6	Correct	86 ms	155688 KB	Output is correct
7	Correct	84 ms	155700 KB	Output is correct
8	Correct	84 ms	155776 KB	Output is correct
9	Correct	85 ms	155796 KB	Output is correct
10	Correct	85 ms	155724 KB	Output is correct
11	Correct	84 ms	155720 KB	Output is correct
12	Correct	78 ms	155648 KB	Output is correct
13	Correct	79 ms	155644 KB	Output is correct
14	Correct	73 ms	155256 KB	Output is correct
15	Correct	73 ms	155340 KB	Output is correct
16	Correct	83 ms	155724 KB	Output is correct
17	Correct	85 ms	155752 KB	Output is correct
18	Correct	84 ms	155704 KB	Output is correct
19	Correct	73 ms	155316 KB	Output is correct
20	Correct	89 ms	155724 KB	Output is correct
21	Correct	84 ms	155792 KB	Output is correct
22	Correct	84 ms	155852 KB	Output is correct
23	Correct	73 ms	155368 KB	Output is correct
24	Correct	72 ms	155520 KB	Output is correct
25	Correct	84 ms	155804 KB	Output is correct
26	Correct	82 ms	155624 KB	Output is correct
27	Correct	89 ms	155784 KB	Output is correct
28	Correct	74 ms	155340 KB	Output is correct

Subtask #4
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	155360 KB	Output is correct
2	Correct	76 ms	155248 KB	Output is correct
3	Correct	81 ms	155788 KB	Output is correct
4	Correct	82 ms	155768 KB	Output is correct
5	Correct	85 ms	155740 KB	Output is correct
6	Correct	86 ms	155688 KB	Output is correct
7	Correct	84 ms	155700 KB	Output is correct
8	Correct	84 ms	155776 KB	Output is correct
9	Correct	85 ms	155796 KB	Output is correct
10	Correct	85 ms	155724 KB	Output is correct
11	Correct	84 ms	155720 KB	Output is correct
12	Correct	78 ms	155648 KB	Output is correct
13	Correct	79 ms	155644 KB	Output is correct
14	Correct	73 ms	155256 KB	Output is correct
15	Correct	73 ms	155340 KB	Output is correct
16	Correct	83 ms	155724 KB	Output is correct
17	Correct	85 ms	155752 KB	Output is correct
18	Correct	84 ms	155704 KB	Output is correct
19	Correct	73 ms	155316 KB	Output is correct
20	Correct	89 ms	155724 KB	Output is correct
21	Correct	84 ms	155792 KB	Output is correct
22	Correct	84 ms	155852 KB	Output is correct
23	Correct	73 ms	155368 KB	Output is correct
24	Correct	72 ms	155520 KB	Output is correct
25	Correct	84 ms	155804 KB	Output is correct
26	Correct	82 ms	155624 KB	Output is correct
27	Correct	89 ms	155784 KB	Output is correct
28	Correct	74 ms	155340 KB	Output is correct
29	Correct	84 ms	155800 KB	Output is correct
30	Correct	94 ms	155780 KB	Output is correct
31	Correct	87 ms	155828 KB	Output is correct
32	Correct	84 ms	155756 KB	Output is correct
33	Correct	85 ms	155724 KB	Output is correct
34	Correct	80 ms	155732 KB	Output is correct
35	Correct	80 ms	155708 KB	Output is correct
36	Correct	85 ms	155664 KB	Output is correct
37	Correct	78 ms	155724 KB	Output is correct

Subtask #5
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	155360 KB	Output is correct
2	Correct	76 ms	155248 KB	Output is correct
3	Correct	81 ms	155788 KB	Output is correct
4	Correct	82 ms	155768 KB	Output is correct
5	Correct	85 ms	155740 KB	Output is correct
6	Correct	86 ms	155688 KB	Output is correct
7	Correct	84 ms	155700 KB	Output is correct
8	Correct	84 ms	155776 KB	Output is correct
9	Correct	85 ms	155796 KB	Output is correct
10	Correct	85 ms	155724 KB	Output is correct
11	Correct	84 ms	155720 KB	Output is correct
12	Correct	78 ms	155648 KB	Output is correct
13	Correct	79 ms	155644 KB	Output is correct
14	Correct	73 ms	155256 KB	Output is correct
15	Correct	73 ms	155340 KB	Output is correct
16	Correct	83 ms	155724 KB	Output is correct
17	Correct	85 ms	155752 KB	Output is correct
18	Correct	84 ms	155704 KB	Output is correct
19	Correct	73 ms	155316 KB	Output is correct
20	Correct	89 ms	155724 KB	Output is correct
21	Correct	84 ms	155792 KB	Output is correct
22	Correct	84 ms	155852 KB	Output is correct
23	Correct	73 ms	155368 KB	Output is correct
24	Correct	72 ms	155520 KB	Output is correct
25	Correct	84 ms	155804 KB	Output is correct
26	Correct	82 ms	155624 KB	Output is correct
27	Correct	89 ms	155784 KB	Output is correct
28	Correct	74 ms	155340 KB	Output is correct
29	Correct	84 ms	155800 KB	Output is correct
30	Correct	94 ms	155780 KB	Output is correct
31	Correct	87 ms	155828 KB	Output is correct
32	Correct	84 ms	155756 KB	Output is correct
33	Correct	85 ms	155724 KB	Output is correct
34	Correct	80 ms	155732 KB	Output is correct
35	Correct	80 ms	155708 KB	Output is correct
36	Correct	85 ms	155664 KB	Output is correct
37	Correct	78 ms	155724 KB	Output is correct
38	Correct	577 ms	165920 KB	Output is correct
39	Correct	1012 ms	329412 KB	Output is correct
40	Correct	712 ms	167028 KB	Output is correct
41	Correct	765 ms	166208 KB	Output is correct
42	Correct	441 ms	166752 KB	Output is correct
43	Correct	709 ms	167024 KB	Output is correct
44	Correct	129 ms	157280 KB	Output is correct
45	Correct	2617 ms	323112 KB	Output is correct
46	Correct	2399 ms	323076 KB	Output is correct
47	Correct	1574 ms	323420 KB	Output is correct
48	Correct	1697 ms	323540 KB	Output is correct
49	Correct	1846 ms	324148 KB	Output is correct
50	Correct	1928 ms	323992 KB	Output is correct
51	Correct	1919 ms	324176 KB	Output is correct
52	Correct	1835 ms	324252 KB	Output is correct
53	Correct	227 ms	167988 KB	Output is correct
54	Correct	2839 ms	323648 KB	Output is correct

Subtask #6
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	74 ms	155340 KB	Output is correct
2	Correct	75 ms	155320 KB	Output is correct
3	Correct	79 ms	155284 KB	Output is correct
4	Correct	75 ms	155272 KB	Output is correct
5	Correct	111 ms	155716 KB	Output is correct
6	Correct	75 ms	155752 KB	Output is correct
7	Correct	77 ms	155652 KB	Output is correct
8	Correct	72 ms	155256 KB	Output is correct
9	Correct	78 ms	155256 KB	Output is correct
10	Correct	73 ms	155524 KB	Output is correct
11	Correct	79 ms	155380 KB	Output is correct
12	Correct	82 ms	155688 KB	Output is correct
13	Correct	181 ms	156124 KB	Output is correct
14	Correct	292 ms	156608 KB	Output is correct
15	Correct	229 ms	156740 KB	Output is correct
16	Correct	2783 ms	324600 KB	Output is correct
17	Correct	2569 ms	329556 KB	Output is correct
18	Correct	2783 ms	337360 KB	Output is correct
19	Correct	2689 ms	324808 KB	Output is correct
20	Correct	2763 ms	324744 KB	Output is correct
21	Correct	2689 ms	324828 KB	Output is correct
22	Correct	2742 ms	328836 KB	Output is correct
23	Correct	2531 ms	328852 KB	Output is correct
24	Correct	3017 ms	328744 KB	Output is correct
25	Correct	2994 ms	328864 KB	Output is correct
26	Correct	3036 ms	328748 KB	Output is correct
27	Correct	2558 ms	328500 KB	Output is correct
28	Correct	2619 ms	328564 KB	Output is correct
29	Correct	2508 ms	328564 KB	Output is correct
30	Correct	2732 ms	327860 KB	Output is correct
31	Correct	3016 ms	327668 KB	Output is correct
32	Correct	2676 ms	325696 KB	Output is correct
33	Correct	2629 ms	325508 KB	Output is correct

Subtask #7
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	75 ms	155340 KB	Output is correct
2	Correct	71 ms	155244 KB	Output is correct
3	Correct	72 ms	155332 KB	Output is correct
4	Correct	153 ms	156008 KB	Output is correct
5	Correct	241 ms	156552 KB	Output is correct
6	Correct	90 ms	155688 KB	Output is correct
7	Correct	84 ms	155756 KB	Output is correct
8	Correct	86 ms	155740 KB	Output is correct
9	Correct	530 ms	165948 KB	Output is correct
10	Correct	1004 ms	329300 KB	Output is correct
11	Correct	119 ms	155536 KB	Output is correct
12	Correct	270 ms	156536 KB	Output is correct
13	Correct	1411 ms	333496 KB	Output is correct
14	Correct	1184 ms	333612 KB	Output is correct
15	Correct	1532 ms	335944 KB	Output is correct
16	Correct	1476 ms	347208 KB	Output is correct
17	Correct	1143 ms	337812 KB	Output is correct
18	Correct	1190 ms	336760 KB	Output is correct
19	Correct	1212 ms	337848 KB	Output is correct
20	Correct	1026 ms	337760 KB	Output is correct
21	Correct	904 ms	336664 KB	Output is correct
22	Correct	882 ms	333088 KB	Output is correct
23	Correct	77 ms	155360 KB	Output is correct
24	Correct	76 ms	155248 KB	Output is correct
25	Correct	81 ms	155788 KB	Output is correct
26	Correct	82 ms	155768 KB	Output is correct
27	Correct	85 ms	155740 KB	Output is correct
28	Correct	86 ms	155688 KB	Output is correct
29	Correct	84 ms	155700 KB	Output is correct
30	Correct	84 ms	155776 KB	Output is correct
31	Correct	85 ms	155796 KB	Output is correct
32	Correct	85 ms	155724 KB	Output is correct
33	Correct	84 ms	155720 KB	Output is correct
34	Correct	78 ms	155648 KB	Output is correct
35	Correct	79 ms	155644 KB	Output is correct
36	Correct	73 ms	155256 KB	Output is correct
37	Correct	73 ms	155340 KB	Output is correct
38	Correct	83 ms	155724 KB	Output is correct
39	Correct	85 ms	155752 KB	Output is correct
40	Correct	84 ms	155704 KB	Output is correct
41	Correct	73 ms	155316 KB	Output is correct
42	Correct	89 ms	155724 KB	Output is correct
43	Correct	84 ms	155792 KB	Output is correct
44	Correct	84 ms	155852 KB	Output is correct
45	Correct	73 ms	155368 KB	Output is correct
46	Correct	72 ms	155520 KB	Output is correct
47	Correct	84 ms	155804 KB	Output is correct
48	Correct	82 ms	155624 KB	Output is correct
49	Correct	89 ms	155784 KB	Output is correct
50	Correct	74 ms	155340 KB	Output is correct
51	Correct	84 ms	155800 KB	Output is correct
52	Correct	94 ms	155780 KB	Output is correct
53	Correct	87 ms	155828 KB	Output is correct
54	Correct	84 ms	155756 KB	Output is correct
55	Correct	85 ms	155724 KB	Output is correct
56	Correct	80 ms	155732 KB	Output is correct
57	Correct	80 ms	155708 KB	Output is correct
58	Correct	85 ms	155664 KB	Output is correct
59	Correct	78 ms	155724 KB	Output is correct
60	Correct	577 ms	165920 KB	Output is correct
61	Correct	1012 ms	329412 KB	Output is correct
62	Correct	712 ms	167028 KB	Output is correct
63	Correct	765 ms	166208 KB	Output is correct
64	Correct	441 ms	166752 KB	Output is correct
65	Correct	709 ms	167024 KB	Output is correct
66	Correct	129 ms	157280 KB	Output is correct
67	Correct	2617 ms	323112 KB	Output is correct
68	Correct	2399 ms	323076 KB	Output is correct
69	Correct	1574 ms	323420 KB	Output is correct
70	Correct	1697 ms	323540 KB	Output is correct
71	Correct	1846 ms	324148 KB	Output is correct
72	Correct	1928 ms	323992 KB	Output is correct
73	Correct	1919 ms	324176 KB	Output is correct
74	Correct	1835 ms	324252 KB	Output is correct
75	Correct	227 ms	167988 KB	Output is correct
76	Correct	2839 ms	323648 KB	Output is correct
77	Correct	74 ms	155340 KB	Output is correct
78	Correct	75 ms	155320 KB	Output is correct
79	Correct	79 ms	155284 KB	Output is correct
80	Correct	75 ms	155272 KB	Output is correct
81	Correct	111 ms	155716 KB	Output is correct
82	Correct	75 ms	155752 KB	Output is correct
83	Correct	77 ms	155652 KB	Output is correct
84	Correct	72 ms	155256 KB	Output is correct
85	Correct	78 ms	155256 KB	Output is correct
86	Correct	73 ms	155524 KB	Output is correct
87	Correct	79 ms	155380 KB	Output is correct
88	Correct	82 ms	155688 KB	Output is correct
89	Correct	181 ms	156124 KB	Output is correct
90	Correct	292 ms	156608 KB	Output is correct
91	Correct	229 ms	156740 KB	Output is correct
92	Correct	2783 ms	324600 KB	Output is correct
93	Correct	2569 ms	329556 KB	Output is correct
94	Correct	2783 ms	337360 KB	Output is correct
95	Correct	2689 ms	324808 KB	Output is correct
96	Correct	2763 ms	324744 KB	Output is correct
97	Correct	2689 ms	324828 KB	Output is correct
98	Correct	2742 ms	328836 KB	Output is correct
99	Correct	2531 ms	328852 KB	Output is correct
100	Correct	3017 ms	328744 KB	Output is correct
101	Correct	2994 ms	328864 KB	Output is correct
102	Correct	3036 ms	328748 KB	Output is correct
103	Correct	2558 ms	328500 KB	Output is correct
104	Correct	2619 ms	328564 KB	Output is correct
105	Correct	2508 ms	328564 KB	Output is correct
106	Correct	2732 ms	327860 KB	Output is correct
107	Correct	3016 ms	327668 KB	Output is correct
108	Correct	2676 ms	325696 KB	Output is correct
109	Correct	2629 ms	325508 KB	Output is correct
110	Correct	303 ms	156872 KB	Output is correct
111	Correct	235 ms	156540 KB	Output is correct
112	Correct	1559 ms	335792 KB	Output is correct
113	Correct	1937 ms	326028 KB	Output is correct
114	Correct	1325 ms	335360 KB	Output is correct
115	Correct	804 ms	328260 KB	Output is correct
116	Correct	2864 ms	330116 KB	Output is correct
117	Correct	2818 ms	339652 KB	Output is correct
118	Correct	2853 ms	323588 KB	Output is correct
119	Correct	2758 ms	323752 KB	Output is correct
120	Correct	208 ms	169972 KB	Output is correct
121	Correct	2885 ms	329960 KB	Output is correct
122	Correct	3040 ms	330004 KB	Output is correct
123	Correct	1872 ms	327348 KB	Output is correct
124	Correct	1373 ms	327372 KB	Output is correct
125	Correct	1832 ms	327872 KB	Output is correct
126	Correct	1805 ms	346988 KB	Output is correct
127	Correct	1751 ms	335720 KB	Output is correct
128	Correct	1612 ms	335796 KB	Output is correct
129	Correct	1891 ms	335680 KB	Output is correct
130	Correct	1648 ms	335656 KB	Output is correct

답안 #635251

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 16.0 / 16.0

Subtask #4 28.0 / 28.0

Subtask #5 12.0 / 12.0

Subtask #6 11.0 / 11.0

Subtask #7 23.0 / 23.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
16.0 / 16.0

Subtask #4
28.0 / 28.0

Subtask #5
12.0 / 12.0

Subtask #6
11.0 / 11.0

Subtask #7
23.0 / 23.0