oj.uz

답안 #648106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
648106 2022-10-05T11:45:02 Z blue Jail (JOI22_jail) C++17
100 / 100
 1113 ms 154352 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
 
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
 
const int lg = 17;
const int INF = 1'000'000;
 
int N;
int M;
vi* edge;
 
int ct;
vi ord;
vi ordind;
 
vvi anc;
vi depth;
vi subtree;
 
void dfs(int u)
{
	ct++;
	ord[ct] = u;
	ordind[u] = ct;
 
	for(int v : edge[u])
	{
		if(v == anc[u][0]) continue;
 
		anc[v][0] = u;
		depth[v] = 1 + depth[u];
 
		dfs(v);
 
		subtree[u] += subtree[v];
	}
}
 
int ancestor(int u, int k)
{
	for(int e = 0; e <= lg; e++)
		if(k & (1 << e))
			u = anc[u][e];
 
	return u;
}
 
int lca(int u, int v)
{
	if(depth[u] > depth[v]) swap(u, v);
 
	v = ancestor(v, depth[v] - depth[u]);
 
	if(u == v) return u;
 
	for(int e = lg; e >= 0; e--)
	{
		if(anc[u][e] == anc[v][e]) continue;
		u = anc[u][e];
		v = anc[v][e];
	}
 
	return anc[u][0];
}
 
 
 
 
struct segtree1
{
	vector< set<pii> > markers;
	vpii bestmark;
 
	segtree1()
	{
		markers = vector<set<pii>>(1+4*N);
		bestmark = vector<pii>(1+4*N, {INF, -1});
	}
 
	void insert(int I, pii V, int i = 1, int l = 1, int r = N)
	{
		if(I < l || r < I) return;
		else if(l == r)
		{
			markers[i].insert(V);
			bestmark[i] = min(bestmark[i], V);
		}
		else
		{
			insert(I, V, 2*i, l, (l+r)/2);
			insert(I, V, 2*i+1, (l+r)/2+1, r);
			bestmark[i] = min({bestmark[i], bestmark[2*i], bestmark[2*i+1]});
		}
	}
 
	void erase(int I, pii V, int i = 1, int l = 1, int r = N)
	{
		if(I < l || r < I) return;
		else if(l == r)
		{
			markers[i].erase(V);
			if(markers[i].empty()) bestmark[i] = {INF, -1};
			else bestmark[i] = *markers[i].begin();
 
		}
		else
		{
			erase(I, V, 2*i, l, (l+r)/2);
			erase(I, V, 2*i+1, (l+r)/2+1, r);
			bestmark[i] = min(bestmark[2*i], bestmark[2*i+1]);
		}
	}
 
	pii rangemin(int L, int R, int i = 1, int l = 1, int r = N)
	{
		if(R < l || r < L) return {INF, -1};
		else if(L <= l && r <= R) return bestmark[i];
		else return min(rangemin(L, R, 2*i, l, (l+r)/2), rangemin(L, R, 2*i+1, (l+r)/2+1, r));
	}
};
 
 
 
struct segtree2
{
	vector<set<pii>> markers;
 
	segtree2()
	{
		markers = vector<set<pii>>(1+4*N);
	}
 
	void insert(int L, int R, pii V, int i = 1, int l = 1, int r = N)
	{
		if(R < l || r < L) return;
		else if(L <= l && r <= R)
		{
			markers[i].insert(V);
		}
		else
		{
			insert(L, R, V, 2*i, l, (l+r)/2);
			insert(L, R, V, 2*i+1, (l+r)/2+1, r);
		}
	}
 
	void erase(int L, int R, pii V, int i = 1, int l = 1, int r = N)
	{
		if(R < l || r < L) return;
		else if(L <= l && r <= R)
		{
			markers[i].erase(V);
		}
		else
		{
			erase(L, R, V, 2*i, l, (l+r)/2);
			erase(L, R, V, 2*i+1, (l+r)/2+1, r);
		}
	}
 
	pii pointmax(int I, int i = 1, int l = 1, int r = N)
	{
		pii curr = markers[i].empty() ? pii{-INF, -1} : *markers[i].rbegin();
		if(l == r) return curr;
		else if(I <= (l+r)/2) return max(curr, pointmax(I, 2*i, l, (l+r)/2));
		else return max(curr, pointmax(I, 2*i+1, (l+r)/2+1, r));
	}
};
 
 
 
 
 
 
 
 
vi S, T;
vi A;
 
 
 
 
 
segtree1 ST1;
segtree2 ST2;
 
 
 
 
bool cyclic;
 
 
void insert_prisoner(int j)
{
	// cerr << "insert prisoner " << j << '\n';
	ST1.insert(ordind[S[j]], {depth[A[j]], j});	
	ST1.insert(ordind[T[j]], {depth[A[j]], j});
 
	ST2.insert(ordind[T[j]], ordind[T[j]] + subtree[T[j]] - 1, {depth[T[j]], j});
}
 
void erase_prisoner(int j)
{
	// cerr << "erase prisoner " << j << '\n';
	ST1.erase(ordind[S[j]], {depth[A[j]], j});	
	ST1.erase(ordind[T[j]], {depth[A[j]], j});
 
	ST2.erase(ordind[T[j]], ordind[T[j]] + subtree[T[j]] - 1, {depth[T[j]], j});
}
 
vi dfsenter;
vi dfsexit;
 
 
 
void prisonerdfs(int u)
{
	dfsenter[u] = 1;
 
	bool usedfirst = 0;
	bool usedS = 0;
 
 
	erase_prisoner(u);
 
	while(1)
	{
		pii vp;
		if(!usedfirst)
		{
			// cerr << "type = 1\n";
			vp = ST1.rangemin(ordind[S[u]], ordind[S[u]] + subtree[S[u]] - 1);
			if(vp.first > depth[S[u]])
			{
				usedfirst = 1;
				// cerr << "continuing\n";
				continue;
			}
		}
		else if(!usedS)
		{
			// cerr << "type = 2\n";
			vp = ST2.pointmax(ordind[S[u]]);
			if(vp.first < depth[A[u]])
			{
				usedS = 1;
				// cerr << "continuing\n";
				continue;
			} 
		}
		else
		{
			// cerr << "type = 3\n";
			vp = ST2.pointmax(ordind[T[u]]);
			if(vp.first < depth[A[u]])
			{
				// cerr << "breaking\n";
				break;
			}
		}
 
		int v = vp.second;
 
		// cerr << "edge = " << u << " -> " << v << '\n';
 
		if(dfsenter[v] && !dfsexit[v])
		{
			cyclic = 1;
			return;
		}
		else if(dfsenter[v] && dfsexit[v])
		{
			;
		}
		else
		{	
			insert_prisoner(u);
			prisonerdfs(v);
			erase_prisoner(u);
			if(cyclic) return;
		}
	}
 
 
 
 
	erase_prisoner(u);
	dfsexit[u] = 1;
}
 
 
 
void run()
{
	cin >> N;
	edge = new vi[1+N];
 
	for(int e = 1; e <= N-1; e++)
	{
		int a, b;
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
 
	ct = 0;
	ord = vi(1+N, 0);
	ordind = vi(1+N, 0);
 
	depth = vi(1+N, 0);
	anc = vvi(1+N, vi(1+lg, 0));
	subtree = vi(1+N, 1);
 
	anc[1][0] = 0;
	depth[1] = 1;
 
	dfs(1);
 
	for(int e = 1; e <= lg; e++)
	{
		for(int i = 0; i <= N; i++)
		{
			anc[i][e] = anc[ anc[i][e-1] ][e-1];
		}
	}
 
	ST1 = segtree1();
	ST2 = segtree2();
 
	cyclic = 0;
 
	cin >> M;
 
	S = T = vi(1+M);
	A = vi(1+M);
 
 
	for(int j = 1; j <= M; j++)
	{
		cin >> S[j] >> T[j];
 
		A[j] = lca(S[j], T[j]);
 
		insert_prisoner(j);
	}
 
	dfsenter = dfsexit = vi(1+M, 0);
 
	for(int i = 1; i <= M; i++)
	{
		if(dfsenter[i]) continue;
		prisonerdfs(i);
		if(cyclic) break;
	}
 
	if(cyclic) cout << "No\n";
	else cout << "Yes\n";
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	int T;
	cin >> T;
 
	for(int t = 1; t <= T; t++)
	{
		run();
	}
  
  cout << "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n";
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 25 ms 3832 KB Output is correct
5 Correct 52 ms 7708 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 3 ms 844 KB Output is correct
8 Correct 7 ms 856 KB Output is correct
9 Correct 107 ms 13428 KB Output is correct
10 Correct 117 ms 78888 KB Output is correct
11 Correct 20 ms 1620 KB Output is correct
12 Correct 113 ms 8112 KB Output is correct
13 Correct 363 ms 105192 KB Output is correct
14 Correct 245 ms 105196 KB Output is correct
15 Correct 432 ms 105192 KB Output is correct
16 Correct 994 ms 142152 KB Output is correct
17 Correct 320 ms 109192 KB Output is correct
18 Correct 544 ms 142328 KB Output is correct
19 Correct 359 ms 110056 KB Output is correct
20 Correct 284 ms 110124 KB Output is correct
21 Correct 281 ms 110508 KB Output is correct
22 Correct 259 ms 110408 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 776 KB Output is correct
4 Correct 4 ms 764 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 764 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 4 ms 840 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 700 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 776 KB Output is correct
4 Correct 4 ms 764 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 764 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 4 ms 840 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 700 KB Output is correct
14 Correct 1 ms 320 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3 ms 836 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 3 ms 844 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 3 ms 852 KB Output is correct
21 Correct 4 ms 844 KB Output is correct
22 Correct 3 ms 844 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 3 ms 852 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 1 ms 324 KB Output is correct

Subtask #4
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 776 KB Output is correct
4 Correct 4 ms 764 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 764 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 4 ms 840 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 700 KB Output is correct
14 Correct 1 ms 320 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3 ms 836 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 3 ms 844 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 3 ms 852 KB Output is correct
21 Correct 4 ms 844 KB Output is correct
22 Correct 3 ms 844 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 3 ms 852 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 1 ms 324 KB Output is correct
29 Correct 6 ms 852 KB Output is correct
30 Correct 4 ms 840 KB Output is correct
31 Correct 4 ms 852 KB Output is correct
32 Correct 4 ms 848 KB Output is correct
33 Correct 3 ms 844 KB Output is correct
34 Correct 6 ms 724 KB Output is correct
35 Correct 6 ms 724 KB Output is correct
36 Correct 7 ms 716 KB Output is correct
37 Correct 5 ms 596 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 776 KB Output is correct
4 Correct 4 ms 764 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 764 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 4 ms 840 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 700 KB Output is correct
14 Correct 1 ms 320 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3 ms 836 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 3 ms 844 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 3 ms 852 KB Output is correct
21 Correct 4 ms 844 KB Output is correct
22 Correct 3 ms 844 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 3 ms 852 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 1 ms 324 KB Output is correct
29 Correct 6 ms 852 KB Output is correct
30 Correct 4 ms 840 KB Output is correct
31 Correct 4 ms 852 KB Output is correct
32 Correct 4 ms 848 KB Output is correct
33 Correct 3 ms 844 KB Output is correct
34 Correct 6 ms 724 KB Output is correct
35 Correct 6 ms 724 KB Output is correct
36 Correct 7 ms 716 KB Output is correct
37 Correct 5 ms 596 KB Output is correct
38 Correct 86 ms 13492 KB Output is correct
39 Correct 84 ms 78948 KB Output is correct
40 Correct 76 ms 13524 KB Output is correct
41 Correct 85 ms 13812 KB Output is correct
42 Correct 72 ms 14200 KB Output is correct
43 Correct 53 ms 13108 KB Output is correct
44 Correct 29 ms 2684 KB Output is correct
45 Correct 106 ms 71364 KB Output is correct
46 Correct 107 ms 71448 KB Output is correct
47 Correct 88 ms 75068 KB Output is correct
48 Correct 87 ms 75112 KB Output is correct
49 Correct 93 ms 71556 KB Output is correct
50 Correct 102 ms 71512 KB Output is correct
51 Correct 98 ms 72592 KB Output is correct
52 Correct 88 ms 72652 KB Output is correct
53 Correct 42 ms 7500 KB Output is correct
54 Correct 125 ms 71328 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 17 ms 1620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 2 ms 692 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 6 ms 724 KB Output is correct
13 Correct 56 ms 4636 KB Output is correct
14 Correct 95 ms 7948 KB Output is correct
15 Correct 89 ms 6132 KB Output is correct
16 Correct 123 ms 73352 KB Output is correct
17 Correct 260 ms 83688 KB Output is correct
18 Correct 446 ms 95788 KB Output is correct
19 Correct 222 ms 74828 KB Output is correct
20 Correct 145 ms 74876 KB Output is correct
21 Correct 211 ms 74796 KB Output is correct
22 Correct 231 ms 83504 KB Output is correct
23 Correct 211 ms 83532 KB Output is correct
24 Correct 432 ms 83572 KB Output is correct
25 Correct 267 ms 83460 KB Output is correct
26 Correct 467 ms 83504 KB Output is correct
27 Correct 1066 ms 97728 KB Output is correct
28 Correct 929 ms 113100 KB Output is correct
29 Correct 634 ms 102176 KB Output is correct
30 Correct 728 ms 91764 KB Output is correct
31 Correct 716 ms 93724 KB Output is correct
32 Correct 713 ms 87160 KB Output is correct
33 Correct 623 ms 92184 KB Output is correct

Subtask #7
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 25 ms 3832 KB Output is correct
5 Correct 52 ms 7708 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 3 ms 844 KB Output is correct
8 Correct 7 ms 856 KB Output is correct
9 Correct 107 ms 13428 KB Output is correct
10 Correct 117 ms 78888 KB Output is correct
11 Correct 20 ms 1620 KB Output is correct
12 Correct 113 ms 8112 KB Output is correct
13 Correct 363 ms 105192 KB Output is correct
14 Correct 245 ms 105196 KB Output is correct
15 Correct 432 ms 105192 KB Output is correct
16 Correct 994 ms 142152 KB Output is correct
17 Correct 320 ms 109192 KB Output is correct
18 Correct 544 ms 142328 KB Output is correct
19 Correct 359 ms 110056 KB Output is correct
20 Correct 284 ms 110124 KB Output is correct
21 Correct 281 ms 110508 KB Output is correct
22 Correct 259 ms 110408 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 3 ms 776 KB Output is correct
26 Correct 4 ms 764 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 3 ms 768 KB Output is correct
29 Correct 3 ms 764 KB Output is correct
30 Correct 3 ms 852 KB Output is correct
31 Correct 4 ms 840 KB Output is correct
32 Correct 3 ms 852 KB Output is correct
33 Correct 3 ms 724 KB Output is correct
34 Correct 2 ms 596 KB Output is correct
35 Correct 2 ms 700 KB Output is correct
36 Correct 1 ms 320 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 3 ms 836 KB Output is correct
39 Correct 3 ms 852 KB Output is correct
40 Correct 3 ms 844 KB Output is correct
41 Correct 1 ms 316 KB Output is correct
42 Correct 3 ms 852 KB Output is correct
43 Correct 4 ms 844 KB Output is correct
44 Correct 3 ms 844 KB Output is correct
45 Correct 1 ms 340 KB Output is correct
46 Correct 1 ms 340 KB Output is correct
47 Correct 3 ms 852 KB Output is correct
48 Correct 1 ms 468 KB Output is correct
49 Correct 3 ms 852 KB Output is correct
50 Correct 1 ms 324 KB Output is correct
51 Correct 6 ms 852 KB Output is correct
52 Correct 4 ms 840 KB Output is correct
53 Correct 4 ms 852 KB Output is correct
54 Correct 4 ms 848 KB Output is correct
55 Correct 3 ms 844 KB Output is correct
56 Correct 6 ms 724 KB Output is correct
57 Correct 6 ms 724 KB Output is correct
58 Correct 7 ms 716 KB Output is correct
59 Correct 5 ms 596 KB Output is correct
60 Correct 86 ms 13492 KB Output is correct
61 Correct 84 ms 78948 KB Output is correct
62 Correct 76 ms 13524 KB Output is correct
63 Correct 85 ms 13812 KB Output is correct
64 Correct 72 ms 14200 KB Output is correct
65 Correct 53 ms 13108 KB Output is correct
66 Correct 29 ms 2684 KB Output is correct
67 Correct 106 ms 71364 KB Output is correct
68 Correct 107 ms 71448 KB Output is correct
69 Correct 88 ms 75068 KB Output is correct
70 Correct 87 ms 75112 KB Output is correct
71 Correct 93 ms 71556 KB Output is correct
72 Correct 102 ms 71512 KB Output is correct
73 Correct 98 ms 72592 KB Output is correct
74 Correct 88 ms 72652 KB Output is correct
75 Correct 42 ms 7500 KB Output is correct
76 Correct 125 ms 71328 KB Output is correct
77 Correct 0 ms 212 KB Output is correct
78 Correct 1 ms 212 KB Output is correct
79 Correct 1 ms 212 KB Output is correct
80 Correct 1 ms 340 KB Output is correct
81 Correct 17 ms 1620 KB Output is correct
82 Correct 1 ms 620 KB Output is correct
83 Correct 2 ms 692 KB Output is correct
84 Correct 1 ms 340 KB Output is correct
85 Correct 1 ms 340 KB Output is correct
86 Correct 1 ms 340 KB Output is correct
87 Correct 1 ms 340 KB Output is correct
88 Correct 6 ms 724 KB Output is correct
89 Correct 56 ms 4636 KB Output is correct
90 Correct 95 ms 7948 KB Output is correct
91 Correct 89 ms 6132 KB Output is correct
92 Correct 123 ms 73352 KB Output is correct
93 Correct 260 ms 83688 KB Output is correct
94 Correct 446 ms 95788 KB Output is correct
95 Correct 222 ms 74828 KB Output is correct
96 Correct 145 ms 74876 KB Output is correct
97 Correct 211 ms 74796 KB Output is correct
98 Correct 231 ms 83504 KB Output is correct
99 Correct 211 ms 83532 KB Output is correct
100 Correct 432 ms 83572 KB Output is correct
101 Correct 267 ms 83460 KB Output is correct
102 Correct 467 ms 83504 KB Output is correct
103 Correct 1066 ms 97728 KB Output is correct
104 Correct 929 ms 113100 KB Output is correct
105 Correct 634 ms 102176 KB Output is correct
106 Correct 728 ms 91764 KB Output is correct
107 Correct 716 ms 93724 KB Output is correct
108 Correct 713 ms 87160 KB Output is correct
109 Correct 623 ms 92184 KB Output is correct
110 Correct 94 ms 8136 KB Output is correct
111 Correct 64 ms 6424 KB Output is correct
112 Correct 570 ms 107192 KB Output is correct
113 Correct 242 ms 78376 KB Output is correct
114 Correct 340 ms 95340 KB Output is correct
115 Correct 101 ms 72036 KB Output is correct
116 Correct 444 ms 85188 KB Output is correct
117 Correct 523 ms 97724 KB Output is correct
118 Correct 134 ms 71500 KB Output is correct
119 Correct 139 ms 71428 KB Output is correct
120 Correct 37 ms 7560 KB Output is correct
121 Correct 698 ms 87720 KB Output is correct
122 Correct 664 ms 87936 KB Output is correct
123 Correct 252 ms 80320 KB Output is correct
124 Correct 167 ms 80436 KB Output is correct
125 Correct 257 ms 80940 KB Output is correct
126 Correct 1113 ms 154352 KB Output is correct
127 Correct 506 ms 110776 KB Output is correct
128 Correct 326 ms 110796 KB Output is correct
129 Correct 673 ms 116164 KB Output is correct
130 Correct 367 ms 111044 KB Output is correct