답안 #860372

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
860372	2023-10-12T18:18:57 Z	KiaRez	Jail (JOI22_jail)	C++17	100 / 100	1109 ms	453064 KB

jail

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define set_dec(x)	                           cout << fixed << setprecision(x);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 2e5+23, lg = 18;
ll Mod = 1e9+7;
//ll Mod = 998244353;

inline ll MOD(ll a, ll mod=Mod) {
	a%=mod; (a<0)&&(a+=mod); return a;
}
inline ll max(ll a, ll b) {return (a>b ? a : b);}
inline ll min(ll a, ll b) {return (a<b ? a : b);}
inline ll abso(ll a) {return (a<0?-a:a);}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

struct Node {
	int deg;
	vector<int> adj;
	Node() {
		deg=0;
	}
} node[N*38];

int q, n, m, cnt, h[N], par[lg][N], s[N], t[N], rs[N], rt[N];
int fakes[lg][N], faket[lg][N];
vector<int> tree[N];

void add(int v, int u) {
	if(v==0 || u==0 || v==u) return;
	node[v].adj.pb(u);
	node[u].deg++;
}

void init(int v, int p=0) {
	par[0][v]=p, h[v]=h[p]+1;

	for(int i=1; i<lg; i++) {
		par[i][v] = par[i-1][par[i-1][v]];
	}
	for(int i=0; i<lg; i++) {
		fakes[i][v] = ++cnt;
		faket[i][v] = ++cnt;
	}
	int tmp = v;
	add(faket[0][v], rt[tmp]);
	tmp = par[0][v];
	add(faket[0][v], rt[tmp]);
	
	tmp = v;
	add(rs[tmp], fakes[0][v]);
	tmp = par[0][v];
	add(rs[tmp], fakes[0][v]);

	for(int i=1; i<lg; i++) {
		add(faket[i][v], faket[i-1][v]);
		add(faket[i][v], faket[i-1][par[i-1][v]]);

		add(fakes[i-1][v], fakes[i][v]);
		add(fakes[i-1][par[i-1][v]], fakes[i][v]);
	}

	for(int u : tree[v]) {
		if(u == p) continue;
		init(u, v);
	}
}

int getPar(int v, int dist) {
	for(int i=0; i<lg; i++) {
		if((dist>>i)%2) {
			v = par[i][v];
		}
	}
	return v;
}

int LCA(int v, int u) {
	if(h[u] < h[v]) swap(v,u);
	u = getPar(u, h[u]-h[v]);
	if(v == u) return v;

	for(int i=lg-1; i>=0; i--) {
		if(par[i][v] != par[i][u]) {
			v=par[i][v], u=par[i][u];
		}
	}
	return par[0][v];
}

void addPaths(int cnd, int v, int dist) {
	if(dist<0 || cnd==0 || v==0) return;
	//cout<<"addPath : "<<cnd<<' '<<v<<' '<<dist<<endl;
	if(dist == 0) {
		//add(cnd, rt[v]);
		add(rs[v], cnd);
		return;
	}
	for(int i=0; i<lg; i++) {
		if((dist>>i)%2==1) {
			//cout<<"edge : "<<cnd<<" ===> ("<<i<<", "<<v<<")\n";
			//add(cnd, faket[i][v]);
			//cout<<"edge : "<<cnd<<" <=== ("<<i<<", "<<v<<")\n";
			add(fakes[i][v], cnd);
			v = par[i][v];
		}
	}
	return;
}

void addPatht(int cnd, int v, int dist) {
	if(dist<0 || cnd==0 || v==0) return;
	//cout<<"addPath : "<<cnd<<' '<<v<<' '<<dist<<endl;
	if(dist == 0) {
		add(cnd, rt[v]);
		return;
	}
	for(int i=0; i<lg; i++) {
		if((dist>>i)%2==1) {
			//cout<<"edge : "<<cnd<<" ===> ("<<i<<", "<<v<<")\n";
			add(cnd, faket[i][v]);
			//cout<<"edge : "<<cnd<<" <=== ("<<i<<", "<<v<<")\n";
			//add(fakes[i][v], cnd);
			v = par[i][v];
		}
	}
	return;
}

void solve() {
	cin>>n;
	for(int v,u,i=1; i<n; i++) {
		cin>>v>>u;
		tree[v].pb(u); tree[u].pb(v);
	}
	cin>>m;
	for(int i=1; i<=m; i++) {
		cin>>s[i]>>t[i];
		rs[s[i]] = i;
		rt[t[i]] = i;
	}
	cnt = m;

	init(1);

	for(int i=1; i<=m; i++) {
		int lca = LCA(s[i], t[i]);
		//int ff = (s[i]==lca || t[i]==lca);
		addPaths(i, par[0][s[i]], h[par[0][s[i]]] - h[lca]);
		addPatht(i, s[i], h[s[i]] - h[lca] - (t[i]==lca));

		addPaths(i, t[i], h[t[i]] - h[lca] - (s[i]==lca));
		addPatht(i, par[0][t[i]], h[par[0][t[i]]] - h[lca]);
	}

	int cnt2=0;
	queue<int> q;
	for(int i=1; i<=cnt; i++) {
		if(node[i].deg == 0) q.push(i);
	}

	while(size(q)) {
		int v = q.front();
		q.pop();
		cnt2 ++;
		for(int u : node[v].adj) {
			node[u].deg--;
			if(node[u].deg==0) {
				q.push(u);
			}
		}
	}

	//fuck(cnt); fuck(cnt2);
	if(cnt2 == cnt) cout<<"Yes\n";
	else cout<<"No\n";
}

/*
node[N*20];
int q, n, m, cnt, h[N], par[lg][N], s[N], t[N], rs[N], rt[N];
int fakes[lg][N], faket[lg][N];
vector<int> tree[N];
*/

void reset() {
	for(int i=0; i<=n+2; i++) {
		h[i]=s[i]=t[i]=rs[i]=rt[i]=0;
		for(int j=0; j<lg; j++) {
			fakes[j][i]=faket[j][i]=0;
		}
		while(size(tree[i])) tree[i].pop_back();
	}

	for(int i=0; i<=cnt; i++) {
		node[i].deg=0;
		while(size(node[i].adj)) node[i].adj.pop_back();
	}
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>q;
	while(q--) {
		solve();
		reset();
	}

	return 0;
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	52 ms	277072 KB	Output is correct
2	Correct	53 ms	277072 KB	Output is correct
3	Correct	54 ms	277072 KB	Output is correct
4	Correct	86 ms	277472 KB	Output is correct
5	Correct	130 ms	277580 KB	Output is correct
6	Correct	56 ms	277560 KB	Output is correct
7	Correct	58 ms	281252 KB	Output is correct
8	Correct	58 ms	277328 KB	Output is correct
9	Correct	247 ms	285264 KB	Output is correct
10	Correct	833 ms	431468 KB	Output is correct
11	Correct	70 ms	289364 KB	Output is correct
12	Correct	162 ms	290644 KB	Output is correct
13	Correct	917 ms	439324 KB	Output is correct
14	Correct	816 ms	439372 KB	Output is correct
15	Correct	787 ms	440824 KB	Output is correct
16	Correct	1032 ms	451412 KB	Output is correct
17	Correct	1089 ms	441568 KB	Output is correct
18	Correct	938 ms	446816 KB	Output is correct
19	Correct	932 ms	441456 KB	Output is correct
20	Correct	878 ms	441564 KB	Output is correct
21	Correct	688 ms	441816 KB	Output is correct
22	Correct	722 ms	438384 KB	Output is correct

Subtask #2

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	53 ms	289108 KB	Output is correct
2	Correct	53 ms	289224 KB	Output is correct
3	Correct	57 ms	289364 KB	Output is correct
4	Correct	57 ms	289616 KB	Output is correct
5	Correct	57 ms	289372 KB	Output is correct
6	Correct	57 ms	289508 KB	Output is correct
7	Correct	59 ms	289488 KB	Output is correct
8	Correct	58 ms	289616 KB	Output is correct
9	Correct	59 ms	289628 KB	Output is correct
10	Correct	57 ms	289616 KB	Output is correct
11	Correct	57 ms	289620 KB	Output is correct
12	Correct	55 ms	289364 KB	Output is correct
13	Correct	55 ms	289432 KB	Output is correct

Subtask #3

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	53 ms	289108 KB	Output is correct
2	Correct	53 ms	289224 KB	Output is correct
3	Correct	57 ms	289364 KB	Output is correct
4	Correct	57 ms	289616 KB	Output is correct
5	Correct	57 ms	289372 KB	Output is correct
6	Correct	57 ms	289508 KB	Output is correct
7	Correct	59 ms	289488 KB	Output is correct
8	Correct	58 ms	289616 KB	Output is correct
9	Correct	59 ms	289628 KB	Output is correct
10	Correct	57 ms	289616 KB	Output is correct
11	Correct	57 ms	289620 KB	Output is correct
12	Correct	55 ms	289364 KB	Output is correct
13	Correct	55 ms	289432 KB	Output is correct
14	Correct	53 ms	289112 KB	Output is correct
15	Correct	55 ms	289396 KB	Output is correct
16	Correct	57 ms	289360 KB	Output is correct
17	Correct	59 ms	289616 KB	Output is correct
18	Correct	58 ms	289616 KB	Output is correct
19	Correct	52 ms	289252 KB	Output is correct
20	Correct	57 ms	289620 KB	Output is correct
21	Correct	57 ms	289372 KB	Output is correct
22	Correct	58 ms	289620 KB	Output is correct
23	Correct	53 ms	289108 KB	Output is correct
24	Correct	53 ms	289360 KB	Output is correct
25	Correct	57 ms	289600 KB	Output is correct
26	Correct	53 ms	289360 KB	Output is correct
27	Correct	59 ms	289624 KB	Output is correct
28	Correct	53 ms	289220 KB	Output is correct

Subtask #4

28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	53 ms	289108 KB	Output is correct
2	Correct	53 ms	289224 KB	Output is correct
3	Correct	57 ms	289364 KB	Output is correct
4	Correct	57 ms	289616 KB	Output is correct
5	Correct	57 ms	289372 KB	Output is correct
6	Correct	57 ms	289508 KB	Output is correct
7	Correct	59 ms	289488 KB	Output is correct
8	Correct	58 ms	289616 KB	Output is correct
9	Correct	59 ms	289628 KB	Output is correct
10	Correct	57 ms	289616 KB	Output is correct
11	Correct	57 ms	289620 KB	Output is correct
12	Correct	55 ms	289364 KB	Output is correct
13	Correct	55 ms	289432 KB	Output is correct
14	Correct	53 ms	289112 KB	Output is correct
15	Correct	55 ms	289396 KB	Output is correct
16	Correct	57 ms	289360 KB	Output is correct
17	Correct	59 ms	289616 KB	Output is correct
18	Correct	58 ms	289616 KB	Output is correct
19	Correct	52 ms	289252 KB	Output is correct
20	Correct	57 ms	289620 KB	Output is correct
21	Correct	57 ms	289372 KB	Output is correct
22	Correct	58 ms	289620 KB	Output is correct
23	Correct	53 ms	289108 KB	Output is correct
24	Correct	53 ms	289360 KB	Output is correct
25	Correct	57 ms	289600 KB	Output is correct
26	Correct	53 ms	289360 KB	Output is correct
27	Correct	59 ms	289624 KB	Output is correct
28	Correct	53 ms	289220 KB	Output is correct
29	Correct	64 ms	289620 KB	Output is correct
30	Correct	59 ms	289620 KB	Output is correct
31	Correct	59 ms	289612 KB	Output is correct
32	Correct	57 ms	289416 KB	Output is correct
33	Correct	61 ms	289620 KB	Output is correct
34	Correct	58 ms	289364 KB	Output is correct
35	Correct	57 ms	289364 KB	Output is correct
36	Correct	56 ms	289368 KB	Output is correct
37	Correct	55 ms	289360 KB	Output is correct

Subtask #5

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	53 ms	289108 KB	Output is correct
2	Correct	53 ms	289224 KB	Output is correct
3	Correct	57 ms	289364 KB	Output is correct
4	Correct	57 ms	289616 KB	Output is correct
5	Correct	57 ms	289372 KB	Output is correct
6	Correct	57 ms	289508 KB	Output is correct
7	Correct	59 ms	289488 KB	Output is correct
8	Correct	58 ms	289616 KB	Output is correct
9	Correct	59 ms	289628 KB	Output is correct
10	Correct	57 ms	289616 KB	Output is correct
11	Correct	57 ms	289620 KB	Output is correct
12	Correct	55 ms	289364 KB	Output is correct
13	Correct	55 ms	289432 KB	Output is correct
14	Correct	53 ms	289112 KB	Output is correct
15	Correct	55 ms	289396 KB	Output is correct
16	Correct	57 ms	289360 KB	Output is correct
17	Correct	59 ms	289616 KB	Output is correct
18	Correct	58 ms	289616 KB	Output is correct
19	Correct	52 ms	289252 KB	Output is correct
20	Correct	57 ms	289620 KB	Output is correct
21	Correct	57 ms	289372 KB	Output is correct
22	Correct	58 ms	289620 KB	Output is correct
23	Correct	53 ms	289108 KB	Output is correct
24	Correct	53 ms	289360 KB	Output is correct
25	Correct	57 ms	289600 KB	Output is correct
26	Correct	53 ms	289360 KB	Output is correct
27	Correct	59 ms	289624 KB	Output is correct
28	Correct	53 ms	289220 KB	Output is correct
29	Correct	64 ms	289620 KB	Output is correct
30	Correct	59 ms	289620 KB	Output is correct
31	Correct	59 ms	289612 KB	Output is correct
32	Correct	57 ms	289416 KB	Output is correct
33	Correct	61 ms	289620 KB	Output is correct
34	Correct	58 ms	289364 KB	Output is correct
35	Correct	57 ms	289364 KB	Output is correct
36	Correct	56 ms	289368 KB	Output is correct
37	Correct	55 ms	289360 KB	Output is correct
38	Correct	271 ms	296644 KB	Output is correct
39	Correct	842 ms	431280 KB	Output is correct
40	Correct	255 ms	299092 KB	Output is correct
41	Correct	308 ms	298576 KB	Output is correct
42	Correct	219 ms	298576 KB	Output is correct
43	Correct	351 ms	298560 KB	Output is correct
44	Correct	74 ms	290956 KB	Output is correct
45	Correct	737 ms	425556 KB	Output is correct
46	Correct	709 ms	425760 KB	Output is correct
47	Correct	931 ms	428204 KB	Output is correct
48	Correct	916 ms	428224 KB	Output is correct
49	Correct	725 ms	428608 KB	Output is correct
50	Correct	713 ms	428372 KB	Output is correct
51	Correct	821 ms	429388 KB	Output is correct
52	Correct	804 ms	429184 KB	Output is correct
53	Correct	106 ms	299088 KB	Output is correct
54	Correct	740 ms	425632 KB	Output is correct

Subtask #6

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	289104 KB	Output is correct
2	Correct	54 ms	289288 KB	Output is correct
3	Correct	53 ms	289320 KB	Output is correct
4	Correct	56 ms	289104 KB	Output is correct
5	Correct	67 ms	289104 KB	Output is correct
6	Correct	55 ms	289480 KB	Output is correct
7	Correct	55 ms	289588 KB	Output is correct
8	Correct	53 ms	289116 KB	Output is correct
9	Correct	52 ms	289320 KB	Output is correct
10	Correct	53 ms	289460 KB	Output is correct
11	Correct	54 ms	289312 KB	Output is correct
12	Correct	56 ms	289432 KB	Output is correct
13	Correct	104 ms	289528 KB	Output is correct
14	Correct	149 ms	289488 KB	Output is correct
15	Correct	128 ms	289992 KB	Output is correct
16	Correct	750 ms	425060 KB	Output is correct
17	Correct	687 ms	433212 KB	Output is correct
18	Correct	772 ms	440404 KB	Output is correct
19	Correct	736 ms	427268 KB	Output is correct
20	Correct	740 ms	427580 KB	Output is correct
21	Correct	778 ms	427544 KB	Output is correct
22	Correct	640 ms	432708 KB	Output is correct
23	Correct	629 ms	432568 KB	Output is correct
24	Correct	755 ms	432600 KB	Output is correct
25	Correct	692 ms	432208 KB	Output is correct
26	Correct	711 ms	432684 KB	Output is correct
27	Correct	665 ms	433108 KB	Output is correct
28	Correct	541 ms	433096 KB	Output is correct
29	Correct	537 ms	432996 KB	Output is correct
30	Correct	702 ms	430508 KB	Output is correct
31	Correct	692 ms	430552 KB	Output is correct
32	Correct	618 ms	428240 KB	Output is correct
33	Correct	508 ms	428176 KB	Output is correct

Subtask #7

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	52 ms	277072 KB	Output is correct
2	Correct	53 ms	277072 KB	Output is correct
3	Correct	54 ms	277072 KB	Output is correct
4	Correct	86 ms	277472 KB	Output is correct
5	Correct	130 ms	277580 KB	Output is correct
6	Correct	56 ms	277560 KB	Output is correct
7	Correct	58 ms	281252 KB	Output is correct
8	Correct	58 ms	277328 KB	Output is correct
9	Correct	247 ms	285264 KB	Output is correct
10	Correct	833 ms	431468 KB	Output is correct
11	Correct	70 ms	289364 KB	Output is correct
12	Correct	162 ms	290644 KB	Output is correct
13	Correct	917 ms	439324 KB	Output is correct
14	Correct	816 ms	439372 KB	Output is correct
15	Correct	787 ms	440824 KB	Output is correct
16	Correct	1032 ms	451412 KB	Output is correct
17	Correct	1089 ms	441568 KB	Output is correct
18	Correct	938 ms	446816 KB	Output is correct
19	Correct	932 ms	441456 KB	Output is correct
20	Correct	878 ms	441564 KB	Output is correct
21	Correct	688 ms	441816 KB	Output is correct
22	Correct	722 ms	438384 KB	Output is correct
23	Correct	53 ms	289108 KB	Output is correct
24	Correct	53 ms	289224 KB	Output is correct
25	Correct	57 ms	289364 KB	Output is correct
26	Correct	57 ms	289616 KB	Output is correct
27	Correct	57 ms	289372 KB	Output is correct
28	Correct	57 ms	289508 KB	Output is correct
29	Correct	59 ms	289488 KB	Output is correct
30	Correct	58 ms	289616 KB	Output is correct
31	Correct	59 ms	289628 KB	Output is correct
32	Correct	57 ms	289616 KB	Output is correct
33	Correct	57 ms	289620 KB	Output is correct
34	Correct	55 ms	289364 KB	Output is correct
35	Correct	55 ms	289432 KB	Output is correct
36	Correct	53 ms	289112 KB	Output is correct
37	Correct	55 ms	289396 KB	Output is correct
38	Correct	57 ms	289360 KB	Output is correct
39	Correct	59 ms	289616 KB	Output is correct
40	Correct	58 ms	289616 KB	Output is correct
41	Correct	52 ms	289252 KB	Output is correct
42	Correct	57 ms	289620 KB	Output is correct
43	Correct	57 ms	289372 KB	Output is correct
44	Correct	58 ms	289620 KB	Output is correct
45	Correct	53 ms	289108 KB	Output is correct
46	Correct	53 ms	289360 KB	Output is correct
47	Correct	57 ms	289600 KB	Output is correct
48	Correct	53 ms	289360 KB	Output is correct
49	Correct	59 ms	289624 KB	Output is correct
50	Correct	53 ms	289220 KB	Output is correct
51	Correct	64 ms	289620 KB	Output is correct
52	Correct	59 ms	289620 KB	Output is correct
53	Correct	59 ms	289612 KB	Output is correct
54	Correct	57 ms	289416 KB	Output is correct
55	Correct	61 ms	289620 KB	Output is correct
56	Correct	58 ms	289364 KB	Output is correct
57	Correct	57 ms	289364 KB	Output is correct
58	Correct	56 ms	289368 KB	Output is correct
59	Correct	55 ms	289360 KB	Output is correct
60	Correct	271 ms	296644 KB	Output is correct
61	Correct	842 ms	431280 KB	Output is correct
62	Correct	255 ms	299092 KB	Output is correct
63	Correct	308 ms	298576 KB	Output is correct
64	Correct	219 ms	298576 KB	Output is correct
65	Correct	351 ms	298560 KB	Output is correct
66	Correct	74 ms	290956 KB	Output is correct
67	Correct	737 ms	425556 KB	Output is correct
68	Correct	709 ms	425760 KB	Output is correct
69	Correct	931 ms	428204 KB	Output is correct
70	Correct	916 ms	428224 KB	Output is correct
71	Correct	725 ms	428608 KB	Output is correct
72	Correct	713 ms	428372 KB	Output is correct
73	Correct	821 ms	429388 KB	Output is correct
74	Correct	804 ms	429184 KB	Output is correct
75	Correct	106 ms	299088 KB	Output is correct
76	Correct	740 ms	425632 KB	Output is correct
77	Correct	54 ms	289104 KB	Output is correct
78	Correct	54 ms	289288 KB	Output is correct
79	Correct	53 ms	289320 KB	Output is correct
80	Correct	56 ms	289104 KB	Output is correct
81	Correct	67 ms	289104 KB	Output is correct
82	Correct	55 ms	289480 KB	Output is correct
83	Correct	55 ms	289588 KB	Output is correct
84	Correct	53 ms	289116 KB	Output is correct
85	Correct	52 ms	289320 KB	Output is correct
86	Correct	53 ms	289460 KB	Output is correct
87	Correct	54 ms	289312 KB	Output is correct
88	Correct	56 ms	289432 KB	Output is correct
89	Correct	104 ms	289528 KB	Output is correct
90	Correct	149 ms	289488 KB	Output is correct
91	Correct	128 ms	289992 KB	Output is correct
92	Correct	750 ms	425060 KB	Output is correct
93	Correct	687 ms	433212 KB	Output is correct
94	Correct	772 ms	440404 KB	Output is correct
95	Correct	736 ms	427268 KB	Output is correct
96	Correct	740 ms	427580 KB	Output is correct
97	Correct	778 ms	427544 KB	Output is correct
98	Correct	640 ms	432708 KB	Output is correct
99	Correct	629 ms	432568 KB	Output is correct
100	Correct	755 ms	432600 KB	Output is correct
101	Correct	692 ms	432208 KB	Output is correct
102	Correct	711 ms	432684 KB	Output is correct
103	Correct	665 ms	433108 KB	Output is correct
104	Correct	541 ms	433096 KB	Output is correct
105	Correct	537 ms	432996 KB	Output is correct
106	Correct	702 ms	430508 KB	Output is correct
107	Correct	692 ms	430552 KB	Output is correct
108	Correct	618 ms	428240 KB	Output is correct
109	Correct	508 ms	428176 KB	Output is correct
110	Correct	152 ms	290644 KB	Output is correct
111	Correct	124 ms	290128 KB	Output is correct
112	Correct	924 ms	442488 KB	Output is correct
113	Correct	983 ms	432288 KB	Output is correct
114	Correct	769 ms	438480 KB	Output is correct
115	Correct	574 ms	427684 KB	Output is correct
116	Correct	817 ms	432296 KB	Output is correct
117	Correct	829 ms	443728 KB	Output is correct
118	Correct	740 ms	425556 KB	Output is correct
119	Correct	746 ms	425804 KB	Output is correct
120	Correct	108 ms	301536 KB	Output is correct
121	Correct	903 ms	434000 KB	Output is correct
122	Correct	829 ms	433492 KB	Output is correct
123	Correct	1037 ms	433228 KB	Output is correct
124	Correct	834 ms	433152 KB	Output is correct
125	Correct	1044 ms	433908 KB	Output is correct
126	Correct	1109 ms	453064 KB	Output is correct
127	Correct	1068 ms	442668 KB	Output is correct
128	Correct	998 ms	442476 KB	Output is correct
129	Correct	1103 ms	442548 KB	Output is correct
130	Correct	1022 ms	442704 KB	Output is correct