oj.uz

Submission #930195

# Submission time Handle Problem Language Result Execution time Memory
930195 2024-02-18T23:53:53 Z asdf1234coding Jail (JOI22_jail) C++14
77 / 100
 910 ms 137520 KB 
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define vi vector<int>
#define ff first
#define ss second
#define pii pair<int, int>
#define pb push_back

const int MX = 120000+10;
const int MN = 25;
int n;

vi vis; // 1 is on stack, 2 is visited
int ok=1;

vector<vi> adj2;


struct Segtree {
	void add(int u, int v) {
		adj2[u].pb(v);
		// cout<<"edge "<<u<<"->"<<v<<endl;
	}
	void build(int t=1, int l=1, int r=n) {
		if(l==r) {
			// do something with an edge
			// gotta connect ID or something
			return;
		}
		int m=(l+r)>>1;
		build(t<<1, l, m); build(t<<1|1, m+1, r);
		add(t, t<<1); add(t, t<<1|1); //add(t<<1, t); add(t<<1|1, t);
	}
	void upd(int ul, int ur, int src, int t=1, int l=1, int r=n) {
		// cout<<"upd "<<ul<<' '<<ur<<' '<<src<<' '<<t<<' '<<l<<' '<<r<<endl;
		if(ul>r || ur<l) return;
		// add edges from src to [ul, ur]
		if(ul<=l && r<=ur) {
			// do something
			add(src, t);
			return;
		}
		int m=(l+r)>>1;
		if(ul<=m) upd(ul, ur, src, t<<1, l, m);
		if(m+1<=ur) upd(ul, ur, src, t<<1|1, m+1, r);
	}
	void upd2(int ul, int ur, int src, int t=1, int l=1, int r=n) {
		// cout<<"upd2 "<<ul<<' '<<ur<<' '<<src<<' '<<t<<' '<<l<<' '<<r<<endl;
		if(ul>r || ur<l) return;
		// add edges from src to [ul, ur]
		if(ul<=l && r<=ur) {
			// do something
			add(t, src);
			return;
		}
		int m=(l+r)>>1;
		if(ul<=m) upd2(ul, ur, src, t<<1, l, m);
		if(m+1<=ur) upd2(ul, ur, src, t<<1|1, m+1, r);
	}


};


struct Segtree2 {
	void add(int u, int v) {
		adj2[u].pb(v);
		// cout<<"edge "<<u<<"->"<<v<<endl;
	}
	void build(int t=1, int l=1, int r=n) {
		if(l==r) {
			// do something with an edge
			// gotta connect ID or something
			return;
		}
		int m=(l+r)>>1;
		build(t<<1, l, m); build(t<<1|1, m+1, r);
		add((t<<1)+4*n+10, (t)+4*n+10); add((t<<1|1)+4*n+10, (t)+4*n+10); //add(t<<1, t); add(t<<1|1, t);
		// add(t+4*n+10, (t<<1)+4*n+10); add(t+4*n+10, (t<<1|1)+4*n+10); //add(t<<1, t); add(t<<1|1, t);
	}
	void upd(int ul, int ur, int src, int t=1, int l=1, int r=n) {
		// cout<<"upd "<<ul<<' '<<ur<<' '<<src<<' '<<t<<' '<<l<<' '<<r<<endl;
		if(ul>r || ur<l) return;
		// add edges from src to [ul, ur]
		if(ul<=l && r<=ur) {
			// do something
			add(src, t+4*n+10);
			return;
		}
		int m=(l+r)>>1;
		if(ul<=m) upd(ul, ur, src, t<<1, l, m);
		if(m+1<=ur) upd(ul, ur, src, t<<1|1, m+1, r);
	}
	void upd2(int ul, int ur, int src, int t=1, int l=1, int r=n) {
		// cout<<"upd2 "<<ul<<' '<<ur<<' '<<src<<' '<<t<<' '<<l<<' '<<r<<endl;
		if(ul>r || ur<l) return;
		// add edges from src to [ul, ur]
		if(ul<=l && r<=ur) {
			// do something
			add(t+4*n+10, src);
			return;
		}
		int m=(l+r)>>1;
		if(ul<=m) upd2(ul, ur, src, t<<1, l, m);
		if(m+1<=ur) upd2(ul, ur, src, t<<1|1, m+1, r);
	}

};

void chk(int cur, int par) {
	// cout<<"chk at "<<cur<<endl;
	vis[cur]=1;
	for(auto x:adj2[cur]) {
		// cout<<cur<<"->"<<x<<endl;
		if(x==par) continue;
		if(vis[x]==1) {
			ok=0; return;
		}
		if(vis[x]==0) chk(x, cur);
	}
	vis[cur]=2;
}

vi adj[MX];
// int sz[MX]; int tp[MX]; int id[MX]; int p[MX]; int dep[MX]; int di[MX];
vi sz, tp, id, p, dep, di;
vi tin, tout;
vector<vi> succ;
int tt;
int ttin=0;
void dfs1(int cur, int par) {
	tin[cur]=++ttin;
	p[cur]=par; sz[cur]=1;
	dep[cur]=dep[par]+1;
	succ[0][cur]=par;
	for(auto x:adj[cur]) {
		if(x==par) continue;
		dfs1(x, cur);
		sz[cur]+=sz[x];
	}
	tout[cur]=ttin;
}
void dfs2(int cur, int par, int top) {
	id[cur]=++tt;
	// if(id[cur]<=10) {
	// 	cout<<"at "<<cur<<' '<<tt<<endl;
	// }
	di[id[cur]]=cur;
	tp[cur]=top;
	int mxs=-1; int mxi=-1;
	for(auto x:adj[cur]) {
		if(x==par) continue;
		if(sz[x]>mxs) {
			mxs=sz[x]; mxi=x;
		}
	}
	if(mxi==-1) return;
	dfs2(mxi, cur, top);
	for(auto x:adj[cur]) {
		if(x==par||x==mxi) continue;
		dfs2(x, cur, x);
	}
}

vector<pii> getpath(int l, int r) {
	vector<pii> a,b;
	while(tp[l]!=tp[r]) {
		// cout<<l<<' '<<r<<endl;
		if(dep[tp[l] ]>dep[tp[r]]) {
			a.pb({id[tp[l]], id[l]});
			l=p[tp[l]];
		} else {
			b.pb({id[tp[r]], id[r]});
			r=p[tp[r]];
		}
	}
	// cout<<l<<' '<<r<<endl;

	a.pb({id[l], id[r]});
	reverse(b.begin(), b.end());
	for(auto x:b) a.pb(x);
	return a;
}

int blift(int x, int d) {
	// cout<<"lift node "<<x<<' '<<d<<endl;
	for(int i=MN-1; i>=0; i--) {
		if((d>>i)&1) {
			x=succ[i][x];
		}
	}
	return x;
}

pii trim(int x, int y) { // return path from x to y without y
	// x is ancestor of y
	if(tin[x]<=tin[y] && tout[y]<=tout[x]) {
		return {x, p[y]};
	}
	// y is ancestor of x
	if(tin[y]<=tin[x] && tout[x]<=tout[y]) {
		// cout<<"this case"<<endl;
		return {x, blift(x, dep[x]-dep[y]-1)};
	}
	return {x, p[y]};
}


void solve() {
	tt=0; ttin=0; ok=1;
	// cout<<"====="<<endl;
	cin>>n;
	adj2=vector<vi>(20*n);
	Segtree st; st.build();
	Segtree2 st2; st2.build();
// 	return;
	sz=vi(n+5); tp=vi(n+5); id=vi(n+5); p=vi(n+5); dep=vi(n+5); di=vi(n+5); tin=vi(n+5); tout=vi(n+5); 
	vis=vi(20*n+5);
	// cout<<"MN n+5  " <<MN<<' '<<n+5<<endl;
	succ=vector<vi>(MN, vi(n+5));
	// cout<<"???"<<endl;
	vector<pii> edges;
	for(int i=0; i<=n; i++) {
		adj[i].clear();
	}

	for(int i=0; i<n-1; i++) {
		int u,v; cin>>u>>v; adj[u].pb(v); adj[v].pb(u);
	}
	dfs1(1, 0); dfs2(1, 0, 1);
	for(int j=1; j<MN; j++) {
		for(int i=1; i<=n; i++) {
			succ[j][i]=succ[j-1][succ[j-1][i]];
		}
	}

	// for(int i=1; i<=n; i++) {
	// 	cout<<i<<": "<<id[i]<<' '<<tp[i]<<endl;
	// }
	int q; cin>>q;
	edges.pb({-1, -1});
	// return;
	for(int i=1; i<=q; i++) {
		// cout<<"qry number "<<i<<endl;
		int x,y; cin>>x>>y; edges.pb({x,y});
		// add edge from 3*n + i to [x, y]
		// trim [x, y] so that it doesnt contain y?
		auto [nx, ny] = trim(x,y);
		auto [ny2, nx2] = trim(y, x);
		// int nx=x; int ny=y;
		// cout<<"nxny "<<nx<<' '<<ny<<endl;
		vector<pii> res = getpath(nx, ny);
		vector<pii> res2 = getpath(nx2, ny2);

		for(auto seg:res) {
			// cout<<"seg "<<seg.ff<<' '<<seg.ss<<endl;
			st.upd(min(seg.ff, seg.ss), max(seg.ff, seg.ss), 3*n+i);
		}
		for(auto seg:res2) {
			st2.upd2(min(seg.ff, seg.ss), max(seg.ff, seg.ss), 3*n+i);
		}
	}
	// now in theory we have a graph where 3*n+i -> [segment s_i to t_i]
	// now gotta connect id[x] to 3*n+x and make sure no cycles


	// cout<<"almost finished building graph"<<endl;

	for(int i=1; i<=q; i++) {
		st.upd2(id[edges[i].ss], id[edges[i].ss], 3*n+i);
		st2.upd(id[edges[i].ff], id[edges[i].ff], 3*n+i);
	}

	// now dfs to find cycles
	for(int i=1; i<=q; i++) {
		if(vis[3*n+i]==0) {
			// cout<<"lol "<<3*n+i<<endl;
			chk(3*n+i, 0); 
		}
	}
	if(ok) {
		cout<<"Yes"<<endl;
	} else {
		cout<<"No"<<endl;
	}
}

int32_t main() {
	int t; cin>>t; while(t--) solve();
}

Compilation message

jail.cpp: In function 'void solve()':
jail.cpp:250:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  250 |   auto [nx, ny] = trim(x,y);
      |        ^
jail.cpp:251:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  251 |   auto [ny2, nx2] = trim(y, x);
      |        ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 34 ms 3420 KB Output is correct
5 Correct 66 ms 4180 KB Output is correct
6 Correct 5 ms 3676 KB Output is correct
7 Correct 5 ms 3676 KB Output is correct
8 Correct 6 ms 3772 KB Output is correct
9 Correct 108 ms 15960 KB Output is correct
10 Correct 125 ms 110500 KB Output is correct
11 Correct 19 ms 3420 KB Output is correct
12 Correct 104 ms 4348 KB Output is correct
13 Correct 212 ms 116428 KB Output is correct
14 Correct 209 ms 116676 KB Output is correct
15 Correct 312 ms 121212 KB Output is correct
16 Correct 614 ms 137520 KB Output is correct
17 Correct 260 ms 124452 KB Output is correct
18 Correct 236 ms 120184 KB Output is correct
19 Correct 219 ms 122376 KB Output is correct
20 Correct 239 ms 122492 KB Output is correct
21 Correct 247 ms 123516 KB Output is correct
22 Correct 194 ms 115324 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 4 ms 3676 KB Output is correct
4 Correct 5 ms 4076 KB Output is correct
5 Correct 4 ms 3664 KB Output is correct
6 Correct 4 ms 3672 KB Output is correct
7 Correct 4 ms 3676 KB Output is correct
8 Correct 4 ms 3676 KB Output is correct
9 Correct 4 ms 3676 KB Output is correct
10 Correct 4 ms 3676 KB Output is correct
11 Correct 4 ms 3676 KB Output is correct
12 Correct 3 ms 3636 KB Output is correct
13 Correct 3 ms 3676 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 4 ms 3676 KB Output is correct
4 Correct 5 ms 4076 KB Output is correct
5 Correct 4 ms 3664 KB Output is correct
6 Correct 4 ms 3672 KB Output is correct
7 Correct 4 ms 3676 KB Output is correct
8 Correct 4 ms 3676 KB Output is correct
9 Correct 4 ms 3676 KB Output is correct
10 Correct 4 ms 3676 KB Output is correct
11 Correct 4 ms 3676 KB Output is correct
12 Correct 3 ms 3636 KB Output is correct
13 Correct 3 ms 3676 KB Output is correct
14 Correct 1 ms 3164 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 5 ms 3676 KB Output is correct
17 Correct 4 ms 3672 KB Output is correct
18 Correct 5 ms 3676 KB Output is correct
19 Correct 2 ms 3164 KB Output is correct
20 Correct 4 ms 3676 KB Output is correct
21 Correct 4 ms 3676 KB Output is correct
22 Correct 5 ms 3676 KB Output is correct
23 Correct 1 ms 3164 KB Output is correct
24 Correct 2 ms 3256 KB Output is correct
25 Correct 5 ms 3672 KB Output is correct
26 Correct 2 ms 3420 KB Output is correct
27 Correct 6 ms 3672 KB Output is correct
28 Correct 2 ms 3164 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 4 ms 3676 KB Output is correct
4 Correct 5 ms 4076 KB Output is correct
5 Correct 4 ms 3664 KB Output is correct
6 Correct 4 ms 3672 KB Output is correct
7 Correct 4 ms 3676 KB Output is correct
8 Correct 4 ms 3676 KB Output is correct
9 Correct 4 ms 3676 KB Output is correct
10 Correct 4 ms 3676 KB Output is correct
11 Correct 4 ms 3676 KB Output is correct
12 Correct 3 ms 3636 KB Output is correct
13 Correct 3 ms 3676 KB Output is correct
14 Correct 1 ms 3164 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 5 ms 3676 KB Output is correct
17 Correct 4 ms 3672 KB Output is correct
18 Correct 5 ms 3676 KB Output is correct
19 Correct 2 ms 3164 KB Output is correct
20 Correct 4 ms 3676 KB Output is correct
21 Correct 4 ms 3676 KB Output is correct
22 Correct 5 ms 3676 KB Output is correct
23 Correct 1 ms 3164 KB Output is correct
24 Correct 2 ms 3256 KB Output is correct
25 Correct 5 ms 3672 KB Output is correct
26 Correct 2 ms 3420 KB Output is correct
27 Correct 6 ms 3672 KB Output is correct
28 Correct 2 ms 3164 KB Output is correct
29 Correct 6 ms 3676 KB Output is correct
30 Correct 6 ms 3676 KB Output is correct
31 Correct 6 ms 3676 KB Output is correct
32 Correct 6 ms 3676 KB Output is correct
33 Correct 5 ms 3552 KB Output is correct
34 Correct 6 ms 3420 KB Output is correct
35 Correct 6 ms 3420 KB Output is correct
36 Correct 5 ms 3420 KB Output is correct
37 Correct 4 ms 3420 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 4 ms 3676 KB Output is correct
4 Correct 5 ms 4076 KB Output is correct
5 Correct 4 ms 3664 KB Output is correct
6 Correct 4 ms 3672 KB Output is correct
7 Correct 4 ms 3676 KB Output is correct
8 Correct 4 ms 3676 KB Output is correct
9 Correct 4 ms 3676 KB Output is correct
10 Correct 4 ms 3676 KB Output is correct
11 Correct 4 ms 3676 KB Output is correct
12 Correct 3 ms 3636 KB Output is correct
13 Correct 3 ms 3676 KB Output is correct
14 Correct 1 ms 3164 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 5 ms 3676 KB Output is correct
17 Correct 4 ms 3672 KB Output is correct
18 Correct 5 ms 3676 KB Output is correct
19 Correct 2 ms 3164 KB Output is correct
20 Correct 4 ms 3676 KB Output is correct
21 Correct 4 ms 3676 KB Output is correct
22 Correct 5 ms 3676 KB Output is correct
23 Correct 1 ms 3164 KB Output is correct
24 Correct 2 ms 3256 KB Output is correct
25 Correct 5 ms 3672 KB Output is correct
26 Correct 2 ms 3420 KB Output is correct
27 Correct 6 ms 3672 KB Output is correct
28 Correct 2 ms 3164 KB Output is correct
29 Correct 6 ms 3676 KB Output is correct
30 Correct 6 ms 3676 KB Output is correct
31 Correct 6 ms 3676 KB Output is correct
32 Correct 6 ms 3676 KB Output is correct
33 Correct 5 ms 3552 KB Output is correct
34 Correct 6 ms 3420 KB Output is correct
35 Correct 6 ms 3420 KB Output is correct
36 Correct 5 ms 3420 KB Output is correct
37 Correct 4 ms 3420 KB Output is correct
38 Correct 94 ms 16100 KB Output is correct
39 Correct 124 ms 110520 KB Output is correct
40 Correct 105 ms 14952 KB Output is correct
41 Correct 108 ms 15308 KB Output is correct
42 Correct 96 ms 15976 KB Output is correct
43 Correct 78 ms 13252 KB Output is correct
44 Correct 31 ms 4892 KB Output is correct
45 Correct 127 ms 101236 KB Output is correct
46 Correct 137 ms 101108 KB Output is correct
47 Correct 122 ms 105800 KB Output is correct
48 Correct 130 ms 105856 KB Output is correct
49 Correct 133 ms 101408 KB Output is correct
50 Correct 134 ms 101364 KB Output is correct
51 Correct 117 ms 102520 KB Output is correct
52 Correct 120 ms 102488 KB Output is correct
53 Correct 32 ms 10828 KB Output is correct
54 Correct 154 ms 101144 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3216 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 19 ms 3164 KB Output is correct
6 Correct 3 ms 3676 KB Output is correct
7 Correct 3 ms 3676 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3164 KB Output is correct
11 Correct 2 ms 3164 KB Output is correct
12 Correct 5 ms 3420 KB Output is correct
13 Correct 71 ms 3976 KB Output is correct
14 Correct 112 ms 4204 KB Output is correct
15 Correct 90 ms 3964 KB Output is correct
16 Correct 182 ms 102728 KB Output is correct
17 Correct 482 ms 112504 KB Output is correct
18 Correct 686 ms 125936 KB Output is correct
19 Correct 269 ms 105044 KB Output is correct
20 Correct 232 ms 104828 KB Output is correct
21 Correct 230 ms 104820 KB Output is correct
22 Correct 407 ms 112012 KB Output is correct
23 Correct 320 ms 111956 KB Output is correct
24 Correct 322 ms 112148 KB Output is correct
25 Correct 316 ms 111996 KB Output is correct
26 Correct 361 ms 112268 KB Output is correct
27 Correct 409 ms 114552 KB Output is correct
28 Correct 460 ms 123156 KB Output is correct
29 Correct 443 ms 117108 KB Output is correct
30 Correct 308 ms 112060 KB Output is correct
31 Correct 288 ms 113388 KB Output is correct
32 Correct 293 ms 109888 KB Output is correct
33 Correct 273 ms 113300 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 34 ms 3420 KB Output is correct
5 Correct 66 ms 4180 KB Output is correct
6 Correct 5 ms 3676 KB Output is correct
7 Correct 5 ms 3676 KB Output is correct
8 Correct 6 ms 3772 KB Output is correct
9 Correct 108 ms 15960 KB Output is correct
10 Correct 125 ms 110500 KB Output is correct
11 Correct 19 ms 3420 KB Output is correct
12 Correct 104 ms 4348 KB Output is correct
13 Correct 212 ms 116428 KB Output is correct
14 Correct 209 ms 116676 KB Output is correct
15 Correct 312 ms 121212 KB Output is correct
16 Correct 614 ms 137520 KB Output is correct
17 Correct 260 ms 124452 KB Output is correct
18 Correct 236 ms 120184 KB Output is correct
19 Correct 219 ms 122376 KB Output is correct
20 Correct 239 ms 122492 KB Output is correct
21 Correct 247 ms 123516 KB Output is correct
22 Correct 194 ms 115324 KB Output is correct
23 Correct 1 ms 3164 KB Output is correct
24 Correct 1 ms 3164 KB Output is correct
25 Correct 4 ms 3676 KB Output is correct
26 Correct 5 ms 4076 KB Output is correct
27 Correct 4 ms 3664 KB Output is correct
28 Correct 4 ms 3672 KB Output is correct
29 Correct 4 ms 3676 KB Output is correct
30 Correct 4 ms 3676 KB Output is correct
31 Correct 4 ms 3676 KB Output is correct
32 Correct 4 ms 3676 KB Output is correct
33 Correct 4 ms 3676 KB Output is correct
34 Correct 3 ms 3636 KB Output is correct
35 Correct 3 ms 3676 KB Output is correct
36 Correct 1 ms 3164 KB Output is correct
37 Correct 1 ms 3164 KB Output is correct
38 Correct 5 ms 3676 KB Output is correct
39 Correct 4 ms 3672 KB Output is correct
40 Correct 5 ms 3676 KB Output is correct
41 Correct 2 ms 3164 KB Output is correct
42 Correct 4 ms 3676 KB Output is correct
43 Correct 4 ms 3676 KB Output is correct
44 Correct 5 ms 3676 KB Output is correct
45 Correct 1 ms 3164 KB Output is correct
46 Correct 2 ms 3256 KB Output is correct
47 Correct 5 ms 3672 KB Output is correct
48 Correct 2 ms 3420 KB Output is correct
49 Correct 6 ms 3672 KB Output is correct
50 Correct 2 ms 3164 KB Output is correct
51 Correct 6 ms 3676 KB Output is correct
52 Correct 6 ms 3676 KB Output is correct
53 Correct 6 ms 3676 KB Output is correct
54 Correct 6 ms 3676 KB Output is correct
55 Correct 5 ms 3552 KB Output is correct
56 Correct 6 ms 3420 KB Output is correct
57 Correct 6 ms 3420 KB Output is correct
58 Correct 5 ms 3420 KB Output is correct
59 Correct 4 ms 3420 KB Output is correct
60 Correct 94 ms 16100 KB Output is correct
61 Correct 124 ms 110520 KB Output is correct
62 Correct 105 ms 14952 KB Output is correct
63 Correct 108 ms 15308 KB Output is correct
64 Correct 96 ms 15976 KB Output is correct
65 Correct 78 ms 13252 KB Output is correct
66 Correct 31 ms 4892 KB Output is correct
67 Correct 127 ms 101236 KB Output is correct
68 Correct 137 ms 101108 KB Output is correct
69 Correct 122 ms 105800 KB Output is correct
70 Correct 130 ms 105856 KB Output is correct
71 Correct 133 ms 101408 KB Output is correct
72 Correct 134 ms 101364 KB Output is correct
73 Correct 117 ms 102520 KB Output is correct
74 Correct 120 ms 102488 KB Output is correct
75 Correct 32 ms 10828 KB Output is correct
76 Correct 154 ms 101144 KB Output is correct
77 Correct 1 ms 3160 KB Output is correct
78 Correct 1 ms 3164 KB Output is correct
79 Correct 1 ms 3216 KB Output is correct
80 Correct 1 ms 3164 KB Output is correct
81 Correct 19 ms 3164 KB Output is correct
82 Correct 3 ms 3676 KB Output is correct
83 Correct 3 ms 3676 KB Output is correct
84 Correct 1 ms 3164 KB Output is correct
85 Correct 1 ms 3164 KB Output is correct
86 Correct 1 ms 3164 KB Output is correct
87 Correct 2 ms 3164 KB Output is correct
88 Correct 5 ms 3420 KB Output is correct
89 Correct 71 ms 3976 KB Output is correct
90 Correct 112 ms 4204 KB Output is correct
91 Correct 90 ms 3964 KB Output is correct
92 Correct 182 ms 102728 KB Output is correct
93 Correct 482 ms 112504 KB Output is correct
94 Correct 686 ms 125936 KB Output is correct
95 Correct 269 ms 105044 KB Output is correct
96 Correct 232 ms 104828 KB Output is correct
97 Correct 230 ms 104820 KB Output is correct
98 Correct 407 ms 112012 KB Output is correct
99 Correct 320 ms 111956 KB Output is correct
100 Correct 322 ms 112148 KB Output is correct
101 Correct 316 ms 111996 KB Output is correct
102 Correct 361 ms 112268 KB Output is correct
103 Correct 409 ms 114552 KB Output is correct
104 Correct 460 ms 123156 KB Output is correct
105 Correct 443 ms 117108 KB Output is correct
106 Correct 308 ms 112060 KB Output is correct
107 Correct 288 ms 113388 KB Output is correct
108 Correct 293 ms 109888 KB Output is correct
109 Correct 273 ms 113300 KB Output is correct
110 Correct 118 ms 4432 KB Output is correct
111 Correct 67 ms 4088 KB Output is correct
112 Correct 344 ms 118904 KB Output is correct
113 Correct 207 ms 110380 KB Output is correct
114 Correct 280 ms 114540 KB Output is correct
115 Correct 120 ms 101500 KB Output is correct
116 Correct 264 ms 106244 KB Output is correct
117 Correct 910 ms 136060 KB Output is correct
118 Correct 131 ms 101244 KB Output is correct
119 Correct 131 ms 101244 KB Output is correct
120 Incorrect 21 ms 11868 KB Output isn't correct
121 Halted 0 ms 0 KB -