oj.uz

답안 #777934

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
777934 2023-07-09T23:00:24 Z aZvezda Jail (JOI22_jail) C++14
100 / 100
 1291 ms 167568 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
 
#ifndef LOCAL
#define cerr if(false)cerr
#endif
 
const int MAX_N = 1e6 + 10, LOG = 20;
int n, m, par[MAX_N][LOG], d[MAX_N], in[MAX_N], out[MAX_N], tme;
int sz[MAX_N], chain[MAX_N];
pair<int, int> quer[MAX_N];
vector<int> g[MAX_N], eul;
 
void calc(int x, int p) {
	sz[x] = 1;
	d[x] = d[p] + 1;
	par[x][0] = p;
	for(int i = 1; i < LOG; i ++) {
		par[x][i] = par[par[x][i - 1]][i - 1];
	}
	for(auto it : g[x]) {
		if(it == p) { continue; }
		calc(it, x);
		sz[x] += sz[it];
	}
}
 
void dfs(int x, int p, bool big = false) {
	if(big) {
		chain[x] = chain[p];
	} else {
		chain[x] = x;
	}
 
	in[x] = eul.size();
	eul.push_back(x);
	eul.push_back(x);
 
	int heavy = -1;
	for(auto it : g[x]) {
		if(it == p) { continue; }
		if(heavy == -1 || sz[it] > sz[heavy]) {
			heavy = it;
		}
	}
 
	if(heavy != -1) { dfs(heavy, x, true); }
	for(auto it : g[x]) {
		if(it == p || it == heavy) { continue; }
		dfs(it, x, false);
	}
 
	out[x] = eul.size() - 1;
}
 
int lca(int a, int b) {
	if(d[a] < d[b]) { swap(a, b); }
	for(int i = LOG - 1; i >= 0; i --) {
		if(d[par[a][i]] >= d[b]) {
			a = par[a][i];
		}
	}
	if(a == b) { return a; }
	for(int i = LOG - 1; i >= 0; i --) {
		if(par[a][i] != par[b][i]) {
			a = par[a][i];
			b = par[b][i];
		}
	}
	return par[a][0];
}
 
struct node_sim {
	pair<int, int> mn, mx;
	node_sim() { mn = {mod, -1}; mx = {-mod, -1}; }
	node_sim(const pair<int, int> &x) { mn = mx = x; }
	node_sim operator +(const node_sim &other) const {
		node_sim ret;
		ret.mn = mn.first < other.mn.first ? mn : other.mn;
		ret.mx = mx.first > other.mx.first ? mx : other.mx;
		return ret;
	}
};
 
struct node_ex {
	int val;
	node_ex(const pair<int, int> &_val = {-1, -1}) { val = _val.first; }
	node_ex operator +(const node_ex &other) const {
		node_ex ret;
		ret.val = val != -1 ? val : other.val;
		return ret;
	}
};
 
template<class node>
struct seg_tree {
	node tree[4 * MAX_N];
	void upd(int curr, int l, int r, int ind, const pair<int, int> &val = {-1, -1}) {
		if(l == r && l == ind) {
			if(val.first == -1) {
				tree[curr] = node();
			} else {
				tree[curr] = node(val);
			}
			return;
		} else if(l > ind || r < ind) { return; }
		int m = (l + r) / 2ll;
		upd(curr * 2, l, m, ind, val);
		upd(curr * 2 + 1, m + 1, r, ind, val);
		tree[curr] = tree[curr * 2] + tree[curr * 2 + 1]; 
	}
	node ans(int curr, int l, int r,  int ql, int qr) {
		if(ql <= l && r <= qr) {
			return tree[curr];
		} else if(l > qr || r < ql) { return node(); }
		int m = (l + r) / 2ll;
		return ans(curr * 2, l, m, ql, qr) + ans(curr * 2 + 1, m + 1, r, ql, qr);
	}
};
 
seg_tree<node_sim> st;
seg_tree<node_ex> st_ex;
 
vector<int> ret = {};
vector<int> who[MAX_N];
int used[MAX_N];
 
int find_block(int a, int b) {
	node_ex ans;
	while(chain[a] != chain[b]) {
		if(d[chain[a]] < d[chain[b]]) { swap(a, b); }
		ans = ans + st_ex.ans(1, 0, MAX_N - 1, in[chain[a]], in[a]);
		a = par[chain[a]][0];
	}
	if(d[a] > d[b]) { swap(a, b); }
	ans = ans + st_ex.ans(1, 0, MAX_N - 1, in[a], in[b]);
	return ans.val;
}
 
 
void topo(int x) {
	if(used[x]) { return; }
	used[x] = true;
	cerr << "Starting " << x << endl;
 
	int a = quer[x].first, b = quer[x].second;
	st_ex.upd(1, 0, MAX_N - 1, in[a]);
 
	for(auto it : who[b]) { topo(it); }
	
	int bl;
	while((bl = find_block(a, b)) != -1) {
		st_ex.upd(1, 0, MAX_N - 1, in[quer[bl].first]);
		topo(bl);
	}
 
	const auto find = [&](const auto ret) {
		if(in[quer[ret.second].first] == ret.first) {
			return in[quer[ret.second].second] + 1;
		} else {
			return in[quer[ret.second].first];
		}
		return -1;
	};
 
 	cerr << "Searching for kid " << x << " " << in[b] << " " << out[b] << endl;
	while(true) {
		auto now = st.ans(1, 0, MAX_N - 1, in[b], out[b]);
		cerr << "Found " << x << " " << now.mx.first << " " << now.mx.second << " " << now.mn.first << endl;
		if(now.mx.first > out[b]) {
			st.upd(1, 0, MAX_N - 1, find(now.mx));
			topo(now.mx.second);
		} else if(now.mn.first < in[b]) {
			st.upd(1, 0, MAX_N - 1, find(now.mn));
			topo(now.mn.second);
		} else {
			break;
		}
	}
 
	cerr << "Ending " << x << endl;
	ret.push_back(x);
}
 
void reset() {
	for(int i = 0; i <= 2 * n + 10; i ++) { st.upd(1, 0, MAX_N - 1, i); }
	for(int i = 0; i <= 2 * n + 10; i ++) { st_ex.upd(1, 0, MAX_N - 1, i); }
}
 
void solve() {
	reset();
	eul.resize(0);
	for(int i = 1; i <= n; i ++) {
		who[i].resize(0);
		g[i].resize(0);
	}
	fill_n(used, n + 1, false); 
 
	cin >> n;
	for(int i = 0; i < n - 1; i ++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	calc(1, 0);
	dfs(1, 0, false);
	
	cin >> m;
	for(int i = 0; i < m; i ++) {
		int a, b;
		cin >> a >> b;
		quer[i] = {a, b};
		who[lca(a, b)].push_back(i);
		st.upd(1, 0, MAX_N - 1, in[a], {in[b], i});
		st.upd(1, 0, MAX_N - 1, in[b] + 1, {in[a], i});
		st_ex.upd(1, 0, MAX_N - 1, in[a], {i, -1});
		cerr << "Quer " << i << " " << a << " " << b << " -> " << in[a] << " " << in[b] << " " << lca(a, b) << endl;
	}
 
	ret = {};
	for(int i = 0; i < m; i ++) {
		if(!used[i]) {
			topo(i);
		}
	}
	
	reset();
	for(int i = 0; i < m; i ++) {
		int a = quer[i].first, b = quer[i].second;
		st_ex.upd(1, 0, MAX_N - 1, in[a], {i, -1});
	}
 
	for(auto it : ret) {
		cerr << "look " << it << endl;
		int a = quer[it].first;
		int b = quer[it].second;
 
		st_ex.upd(1, 0, MAX_N - 1, in[a]);
		if(find_block(a, b) != -1) {
			cout << "No" << endl;
			return;
		}
		st_ex.upd(1, 0, MAX_N - 1, in[b], {it, -1});
	}
	cout << "Yes" << endl;
}
 
signed main() {
	// ios_base::sync_with_stdio(false); cin.tie(NULL);
 
	int t;
	cin >> t;
	while(t --) {
		solve();
	}
}

Compilation message

jail.cpp: In function 'void solve()':
jail.cpp:232:26: warning: unused variable 'b' [-Wunused-variable]
  232 |   int a = quer[i].first, b = quer[i].second;
      |                          ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 125588 KB Output is correct
2 Correct 49 ms 125600 KB Output is correct
3 Correct 48 ms 125592 KB Output is correct
4 Correct 119 ms 125592 KB Output is correct
5 Correct 200 ms 125596 KB Output is correct
6 Correct 55 ms 125624 KB Output is correct
7 Correct 54 ms 125616 KB Output is correct
8 Correct 60 ms 125616 KB Output is correct
9 Correct 227 ms 127032 KB Output is correct
10 Correct 182 ms 151488 KB Output is correct
11 Correct 91 ms 125556 KB Output is correct
12 Correct 280 ms 125624 KB Output is correct
13 Correct 351 ms 154036 KB Output is correct
14 Correct 302 ms 154008 KB Output is correct
15 Correct 465 ms 153812 KB Output is correct
16 Correct 803 ms 165596 KB Output is correct
17 Correct 362 ms 154416 KB Output is correct
18 Correct 476 ms 166944 KB Output is correct
19 Correct 358 ms 154488 KB Output is correct
20 Correct 337 ms 154532 KB Output is correct
21 Correct 369 ms 154504 KB Output is correct
22 Correct 337 ms 154484 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 125540 KB Output is correct
2 Correct 59 ms 125556 KB Output is correct
3 Correct 59 ms 125588 KB Output is correct
4 Correct 59 ms 125540 KB Output is correct
5 Correct 56 ms 125544 KB Output is correct
6 Correct 57 ms 125560 KB Output is correct
7 Correct 57 ms 125516 KB Output is correct
8 Correct 56 ms 125572 KB Output is correct
9 Correct 57 ms 125520 KB Output is correct
10 Correct 55 ms 125548 KB Output is correct
11 Correct 56 ms 125516 KB Output is correct
12 Correct 52 ms 125616 KB Output is correct
13 Correct 54 ms 125600 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 125540 KB Output is correct
2 Correct 59 ms 125556 KB Output is correct
3 Correct 59 ms 125588 KB Output is correct
4 Correct 59 ms 125540 KB Output is correct
5 Correct 56 ms 125544 KB Output is correct
6 Correct 57 ms 125560 KB Output is correct
7 Correct 57 ms 125516 KB Output is correct
8 Correct 56 ms 125572 KB Output is correct
9 Correct 57 ms 125520 KB Output is correct
10 Correct 55 ms 125548 KB Output is correct
11 Correct 56 ms 125516 KB Output is correct
12 Correct 52 ms 125616 KB Output is correct
13 Correct 54 ms 125600 KB Output is correct
14 Correct 51 ms 125516 KB Output is correct
15 Correct 52 ms 125504 KB Output is correct
16 Correct 58 ms 125544 KB Output is correct
17 Correct 56 ms 125628 KB Output is correct
18 Correct 62 ms 125640 KB Output is correct
19 Correct 50 ms 125580 KB Output is correct
20 Correct 57 ms 125556 KB Output is correct
21 Correct 57 ms 125616 KB Output is correct
22 Correct 66 ms 125600 KB Output is correct
23 Correct 54 ms 125568 KB Output is correct
24 Correct 49 ms 125508 KB Output is correct
25 Correct 55 ms 125624 KB Output is correct
26 Correct 50 ms 125516 KB Output is correct
27 Correct 55 ms 125516 KB Output is correct
28 Correct 51 ms 125524 KB Output is correct

Subtask #4
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 125540 KB Output is correct
2 Correct 59 ms 125556 KB Output is correct
3 Correct 59 ms 125588 KB Output is correct
4 Correct 59 ms 125540 KB Output is correct
5 Correct 56 ms 125544 KB Output is correct
6 Correct 57 ms 125560 KB Output is correct
7 Correct 57 ms 125516 KB Output is correct
8 Correct 56 ms 125572 KB Output is correct
9 Correct 57 ms 125520 KB Output is correct
10 Correct 55 ms 125548 KB Output is correct
11 Correct 56 ms 125516 KB Output is correct
12 Correct 52 ms 125616 KB Output is correct
13 Correct 54 ms 125600 KB Output is correct
14 Correct 51 ms 125516 KB Output is correct
15 Correct 52 ms 125504 KB Output is correct
16 Correct 58 ms 125544 KB Output is correct
17 Correct 56 ms 125628 KB Output is correct
18 Correct 62 ms 125640 KB Output is correct
19 Correct 50 ms 125580 KB Output is correct
20 Correct 57 ms 125556 KB Output is correct
21 Correct 57 ms 125616 KB Output is correct
22 Correct 66 ms 125600 KB Output is correct
23 Correct 54 ms 125568 KB Output is correct
24 Correct 49 ms 125508 KB Output is correct
25 Correct 55 ms 125624 KB Output is correct
26 Correct 50 ms 125516 KB Output is correct
27 Correct 55 ms 125516 KB Output is correct
28 Correct 51 ms 125524 KB Output is correct
29 Correct 58 ms 125552 KB Output is correct
30 Correct 65 ms 125692 KB Output is correct
31 Correct 60 ms 125644 KB Output is correct
32 Correct 61 ms 125632 KB Output is correct
33 Correct 57 ms 125516 KB Output is correct
34 Correct 60 ms 125544 KB Output is correct
35 Correct 59 ms 125596 KB Output is correct
36 Correct 60 ms 125648 KB Output is correct
37 Correct 60 ms 125512 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 125540 KB Output is correct
2 Correct 59 ms 125556 KB Output is correct
3 Correct 59 ms 125588 KB Output is correct
4 Correct 59 ms 125540 KB Output is correct
5 Correct 56 ms 125544 KB Output is correct
6 Correct 57 ms 125560 KB Output is correct
7 Correct 57 ms 125516 KB Output is correct
8 Correct 56 ms 125572 KB Output is correct
9 Correct 57 ms 125520 KB Output is correct
10 Correct 55 ms 125548 KB Output is correct
11 Correct 56 ms 125516 KB Output is correct
12 Correct 52 ms 125616 KB Output is correct
13 Correct 54 ms 125600 KB Output is correct
14 Correct 51 ms 125516 KB Output is correct
15 Correct 52 ms 125504 KB Output is correct
16 Correct 58 ms 125544 KB Output is correct
17 Correct 56 ms 125628 KB Output is correct
18 Correct 62 ms 125640 KB Output is correct
19 Correct 50 ms 125580 KB Output is correct
20 Correct 57 ms 125556 KB Output is correct
21 Correct 57 ms 125616 KB Output is correct
22 Correct 66 ms 125600 KB Output is correct
23 Correct 54 ms 125568 KB Output is correct
24 Correct 49 ms 125508 KB Output is correct
25 Correct 55 ms 125624 KB Output is correct
26 Correct 50 ms 125516 KB Output is correct
27 Correct 55 ms 125516 KB Output is correct
28 Correct 51 ms 125524 KB Output is correct
29 Correct 58 ms 125552 KB Output is correct
30 Correct 65 ms 125692 KB Output is correct
31 Correct 60 ms 125644 KB Output is correct
32 Correct 61 ms 125632 KB Output is correct
33 Correct 57 ms 125516 KB Output is correct
34 Correct 60 ms 125544 KB Output is correct
35 Correct 59 ms 125596 KB Output is correct
36 Correct 60 ms 125648 KB Output is correct
37 Correct 60 ms 125512 KB Output is correct
38 Correct 232 ms 128052 KB Output is correct
39 Correct 180 ms 152988 KB Output is correct
40 Correct 272 ms 127904 KB Output is correct
41 Correct 264 ms 127716 KB Output is correct
42 Correct 237 ms 128004 KB Output is correct
43 Correct 215 ms 127868 KB Output is correct
44 Correct 105 ms 126000 KB Output is correct
45 Correct 199 ms 143676 KB Output is correct
46 Correct 221 ms 143676 KB Output is correct
47 Correct 187 ms 148168 KB Output is correct
48 Correct 185 ms 148220 KB Output is correct
49 Correct 229 ms 143808 KB Output is correct
50 Correct 197 ms 143788 KB Output is correct
51 Correct 189 ms 145104 KB Output is correct
52 Correct 186 ms 145080 KB Output is correct
53 Correct 118 ms 127236 KB Output is correct
54 Correct 229 ms 143564 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 125528 KB Output is correct
2 Correct 49 ms 125504 KB Output is correct
3 Correct 56 ms 125516 KB Output is correct
4 Correct 48 ms 125560 KB Output is correct
5 Correct 91 ms 125492 KB Output is correct
6 Correct 53 ms 125624 KB Output is correct
7 Correct 52 ms 125520 KB Output is correct
8 Correct 49 ms 125536 KB Output is correct
9 Correct 49 ms 125552 KB Output is correct
10 Correct 50 ms 125596 KB Output is correct
11 Correct 50 ms 125540 KB Output is correct
12 Correct 59 ms 125652 KB Output is correct
13 Correct 206 ms 125616 KB Output is correct
14 Correct 291 ms 125616 KB Output is correct
15 Correct 245 ms 125616 KB Output is correct
16 Correct 252 ms 143720 KB Output is correct
17 Correct 600 ms 149012 KB Output is correct
18 Correct 1033 ms 162516 KB Output is correct
19 Correct 345 ms 144316 KB Output is correct
20 Correct 305 ms 144284 KB Output is correct
21 Correct 357 ms 144296 KB Output is correct
22 Correct 482 ms 146740 KB Output is correct
23 Correct 440 ms 145824 KB Output is correct
24 Correct 546 ms 145728 KB Output is correct
25 Correct 435 ms 145816 KB Output is correct
26 Correct 516 ms 145788 KB Output is correct
27 Correct 935 ms 162640 KB Output is correct
28 Correct 897 ms 167260 KB Output is correct
29 Correct 801 ms 157336 KB Output is correct
30 Correct 596 ms 153704 KB Output is correct
31 Correct 576 ms 155468 KB Output is correct
32 Correct 575 ms 153068 KB Output is correct
33 Correct 538 ms 155244 KB Output is correct

Subtask #7
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 125588 KB Output is correct
2 Correct 49 ms 125600 KB Output is correct
3 Correct 48 ms 125592 KB Output is correct
4 Correct 119 ms 125592 KB Output is correct
5 Correct 200 ms 125596 KB Output is correct
6 Correct 55 ms 125624 KB Output is correct
7 Correct 54 ms 125616 KB Output is correct
8 Correct 60 ms 125616 KB Output is correct
9 Correct 227 ms 127032 KB Output is correct
10 Correct 182 ms 151488 KB Output is correct
11 Correct 91 ms 125556 KB Output is correct
12 Correct 280 ms 125624 KB Output is correct
13 Correct 351 ms 154036 KB Output is correct
14 Correct 302 ms 154008 KB Output is correct
15 Correct 465 ms 153812 KB Output is correct
16 Correct 803 ms 165596 KB Output is correct
17 Correct 362 ms 154416 KB Output is correct
18 Correct 476 ms 166944 KB Output is correct
19 Correct 358 ms 154488 KB Output is correct
20 Correct 337 ms 154532 KB Output is correct
21 Correct 369 ms 154504 KB Output is correct
22 Correct 337 ms 154484 KB Output is correct
23 Correct 61 ms 125540 KB Output is correct
24 Correct 59 ms 125556 KB Output is correct
25 Correct 59 ms 125588 KB Output is correct
26 Correct 59 ms 125540 KB Output is correct
27 Correct 56 ms 125544 KB Output is correct
28 Correct 57 ms 125560 KB Output is correct
29 Correct 57 ms 125516 KB Output is correct
30 Correct 56 ms 125572 KB Output is correct
31 Correct 57 ms 125520 KB Output is correct
32 Correct 55 ms 125548 KB Output is correct
33 Correct 56 ms 125516 KB Output is correct
34 Correct 52 ms 125616 KB Output is correct
35 Correct 54 ms 125600 KB Output is correct
36 Correct 51 ms 125516 KB Output is correct
37 Correct 52 ms 125504 KB Output is correct
38 Correct 58 ms 125544 KB Output is correct
39 Correct 56 ms 125628 KB Output is correct
40 Correct 62 ms 125640 KB Output is correct
41 Correct 50 ms 125580 KB Output is correct
42 Correct 57 ms 125556 KB Output is correct
43 Correct 57 ms 125616 KB Output is correct
44 Correct 66 ms 125600 KB Output is correct
45 Correct 54 ms 125568 KB Output is correct
46 Correct 49 ms 125508 KB Output is correct
47 Correct 55 ms 125624 KB Output is correct
48 Correct 50 ms 125516 KB Output is correct
49 Correct 55 ms 125516 KB Output is correct
50 Correct 51 ms 125524 KB Output is correct
51 Correct 58 ms 125552 KB Output is correct
52 Correct 65 ms 125692 KB Output is correct
53 Correct 60 ms 125644 KB Output is correct
54 Correct 61 ms 125632 KB Output is correct
55 Correct 57 ms 125516 KB Output is correct
56 Correct 60 ms 125544 KB Output is correct
57 Correct 59 ms 125596 KB Output is correct
58 Correct 60 ms 125648 KB Output is correct
59 Correct 60 ms 125512 KB Output is correct
60 Correct 232 ms 128052 KB Output is correct
61 Correct 180 ms 152988 KB Output is correct
62 Correct 272 ms 127904 KB Output is correct
63 Correct 264 ms 127716 KB Output is correct
64 Correct 237 ms 128004 KB Output is correct
65 Correct 215 ms 127868 KB Output is correct
66 Correct 105 ms 126000 KB Output is correct
67 Correct 199 ms 143676 KB Output is correct
68 Correct 221 ms 143676 KB Output is correct
69 Correct 187 ms 148168 KB Output is correct
70 Correct 185 ms 148220 KB Output is correct
71 Correct 229 ms 143808 KB Output is correct
72 Correct 197 ms 143788 KB Output is correct
73 Correct 189 ms 145104 KB Output is correct
74 Correct 186 ms 145080 KB Output is correct
75 Correct 118 ms 127236 KB Output is correct
76 Correct 229 ms 143564 KB Output is correct
77 Correct 57 ms 125528 KB Output is correct
78 Correct 49 ms 125504 KB Output is correct
79 Correct 56 ms 125516 KB Output is correct
80 Correct 48 ms 125560 KB Output is correct
81 Correct 91 ms 125492 KB Output is correct
82 Correct 53 ms 125624 KB Output is correct
83 Correct 52 ms 125520 KB Output is correct
84 Correct 49 ms 125536 KB Output is correct
85 Correct 49 ms 125552 KB Output is correct
86 Correct 50 ms 125596 KB Output is correct
87 Correct 50 ms 125540 KB Output is correct
88 Correct 59 ms 125652 KB Output is correct
89 Correct 206 ms 125616 KB Output is correct
90 Correct 291 ms 125616 KB Output is correct
91 Correct 245 ms 125616 KB Output is correct
92 Correct 252 ms 143720 KB Output is correct
93 Correct 600 ms 149012 KB Output is correct
94 Correct 1033 ms 162516 KB Output is correct
95 Correct 345 ms 144316 KB Output is correct
96 Correct 305 ms 144284 KB Output is correct
97 Correct 357 ms 144296 KB Output is correct
98 Correct 482 ms 146740 KB Output is correct
99 Correct 440 ms 145824 KB Output is correct
100 Correct 546 ms 145728 KB Output is correct
101 Correct 435 ms 145816 KB Output is correct
102 Correct 516 ms 145788 KB Output is correct
103 Correct 935 ms 162640 KB Output is correct
104 Correct 897 ms 167260 KB Output is correct
105 Correct 801 ms 157336 KB Output is correct
106 Correct 596 ms 153704 KB Output is correct
107 Correct 576 ms 155468 KB Output is correct
108 Correct 575 ms 153068 KB Output is correct
109 Correct 538 ms 155244 KB Output is correct
110 Correct 291 ms 126632 KB Output is correct
111 Correct 213 ms 126240 KB Output is correct
112 Correct 559 ms 154600 KB Output is correct
113 Correct 320 ms 149192 KB Output is correct
114 Correct 533 ms 152328 KB Output is correct
115 Correct 196 ms 143680 KB Output is correct
116 Correct 561 ms 146764 KB Output is correct
117 Correct 1291 ms 163260 KB Output is correct
118 Correct 235 ms 143644 KB Output is correct
119 Correct 258 ms 143640 KB Output is correct
120 Correct 79 ms 127280 KB Output is correct
121 Correct 587 ms 146276 KB Output is correct
122 Correct 517 ms 146224 KB Output is correct
123 Correct 390 ms 151048 KB Output is correct
124 Correct 324 ms 150996 KB Output is correct
125 Correct 391 ms 151188 KB Output is correct
126 Correct 884 ms 167568 KB Output is correct
127 Correct 445 ms 153628 KB Output is correct
128 Correct 417 ms 154904 KB Output is correct
129 Correct 368 ms 148744 KB Output is correct
130 Correct 366 ms 148836 KB Output is correct