oj.uz

Submission #647437

# Submission time Handle Problem Language Result Execution time Memory
647437 2022-10-02T14:56:20 Z ghostwriter Bridges (APIO19_bridges) C++14
100 / 100
 2946 ms 420216 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
    DIT ME CHUYEN BAO LOC
----------------------------------------------------------------
*/
struct Edge {
	int u, v, w;
	Edge() {}
	Edge(int u, int v, int w) : u(u), v(v), w(w) {}
};
struct Query {
	int t, a, b;
	Query() {}
	Query(int t, int a, int b) : t(t), a(a), b(b) {}
};
struct Operation {
	int x, y, px, py, sx, sy;
	Operation() {}
	Operation(int x, int y, int px, int py, int sx, int sy) : x(x), y(y), px(px), py(py), sx(sx), sy(sy) {}
};
const int N = 5e4 + 1;
const int M = 1e5 + 1;
const int Mx2 = 2e5 + 1;
const int D = 600;
int n, m, q, p[N], s[N], e1[M], ans[M];
Edge e[M];
Query query[M];
vi v, d[Mx2];
stack<Operation> s1;
int getpos(int x) { return lb(all(v), x) - v.bg(); }
int getp(int i) { return i == p[i]? i : getp(p[i]); }
bool join(int x, int y) {
	x = getp(x);
	y = getp(y);
	s1.push(Operation(x, y, p[x], p[y], s[x], s[y]));
	if (x == y) return 0;
	if (s[x] < s[y]) swap(x, y);
	p[y] = p[x];
	s[x] += s[y];
	return 1;
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    cin >> n >> m;
    FOR(i, 1, m) {
    	cin >> e[i].u >> e[i].v >> e[i].w;
    	v.pb(e[i].w);
    }
    cin >> q;
    v.pb(-1);
    FOR(i, 1, q) {
    	cin >> query[i].t >> query[i].a >> query[i].b;
    	v.pb(query[i].b);
    }
    sort(all(v));
    FOR(i, 1, m) e[i].w = getpos(e[i].w);
    FOR(i, 1, q) query[i].b = getpos(query[i].b);
    FOR(i, 1, q) {
    	int j = i;
    	WHILE(j <= q && j / D == i / D) ++j;
    	--j;
    	vi cedge, uedge;
    	FOR(z, i, j)
    		if (query[z].t == 2) d[query[z].b].pb(z);
    		else uedge.pb(query[z].a); 
    	vi a;
    	FOR(z, 1, sz(v) - 1) {
    		if (d[z].empty()) continue;
    		EACH(x, d[z]) a.pb(x);
    		d[z].clear();
    	}
    	FOR(z, 1, n) {
    		p[z] = z;
    		s[z] = 1;
    	}
    	EACH(z, uedge) e1[z] = 1;
    	FOR(z, 1, m)
    		if (!e1[z])
    			d[e[z].w].pb(z);
    	EACH(z, uedge) e1[z] = 0;
    	FOR(z, 1, sz(v) - 1) {
    		if (d[z].empty()) continue;
    		EACH(x, d[z]) cedge.pb(x);
    		d[z].clear();
    	}
    	int cur = sz(cedge) - 1;
    	FSN(z, sz(a)) {
    		int qpos = a[z];
    		WHILE(cur >= 0 && e[cedge[cur]].w >= query[qpos].b) {
    			int epos = cedge[cur];
    			join(e[epos].u, e[epos].v);
    			--cur;
    		}
    		FOR(x, i, qpos)
    			if (query[x].t == 1)
    				e1[query[x].a] = query[x].b;
    		int tupd = 0;
    		EACH(x, uedge) {
    			int w = (e1[x]? e1[x] : e[x].w);
    			if (w >= query[qpos].b) {
    				join(e[x].u, e[x].v);
    				++tupd;
    			}
    		}
    		ans[qpos] = s[getp(query[qpos].a)];
    		FRN(x, tupd) {
    			Operation &cur = s1.top();
    			p[cur.x] = cur.px;
    			p[cur.y] = cur.py;
    			s[cur.x] = cur.sx;
    			s[cur.y] = cur.sy;
    			s1.pop();
    		}
    		FOR(x, i, qpos)
    			if (query[x].t == 1)
    				e1[query[x].a] = 0;
    	}
    	FOR(z, i, j)
    		if (query[z].t == 1)
    			e[query[z].a].w = query[z].b;
    	i = j;
    }
    FOR(i, 1, q)
    	if (ans[i])
    		cout << ans[i] << '\n';
    return 0;
}
/*
3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
1 4 1
2 2 5
1 1 1
2 3 2
----------------------------------------------------------------
From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridges.cpp:92:5: note: in expansion of macro 'FOR'
   92 |     FOR(i, 1, m) {
      |     ^~~
bridges.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridges.cpp:98:5: note: in expansion of macro 'FOR'
   98 |     FOR(i, 1, q) {
      |     ^~~
bridges.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridges.cpp:103:5: note: in expansion of macro 'FOR'
  103 |     FOR(i, 1, m) e[i].w = getpos(e[i].w);
      |     ^~~
bridges.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridges.cpp:104:5: note: in expansion of macro 'FOR'
  104 |     FOR(i, 1, q) query[i].b = getpos(query[i].b);
      |     ^~~
bridges.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridges.cpp:105:5: note: in expansion of macro 'FOR'
  105 |     FOR(i, 1, q) {
      |     ^~~
bridges.cpp:32:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridges.cpp:110:6: note: in expansion of macro 'FOR'
  110 |      FOR(z, i, j)
      |      ^~~
bridges.cpp:32:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridges.cpp:114:6: note: in expansion of macro 'FOR'
  114 |      FOR(z, 1, sz(v) - 1) {
      |      ^~~
bridges.cpp:36:31: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   36 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
bridges.cpp:116:7: note: in expansion of macro 'EACH'
  116 |       EACH(x, d[z]) a.pb(x);
      |       ^~~~
bridges.cpp:32:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridges.cpp:119:6: note: in expansion of macro 'FOR'
  119 |      FOR(z, 1, n) {
      |      ^~~
bridges.cpp:36:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   36 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
bridges.cpp:123:6: note: in expansion of macro 'EACH'
  123 |      EACH(z, uedge) e1[z] = 1;
      |      ^~~~
bridges.cpp:32:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridges.cpp:124:6: note: in expansion of macro 'FOR'
  124 |      FOR(z, 1, m)
      |      ^~~
bridges.cpp:36:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   36 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
bridges.cpp:127:6: note: in expansion of macro 'EACH'
  127 |      EACH(z, uedge) e1[z] = 0;
      |      ^~~~
bridges.cpp:32:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridges.cpp:128:6: note: in expansion of macro 'FOR'
  128 |      FOR(z, 1, sz(v) - 1) {
      |      ^~~
bridges.cpp:36:31: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   36 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
bridges.cpp:130:7: note: in expansion of macro 'EACH'
  130 |       EACH(x, d[z]) cedge.pb(x);
      |       ^~~~
bridges.cpp:35:28: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   35 | #define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
      |                            ^
bridges.cpp:134:6: note: in expansion of macro 'FSN'
  134 |      FSN(z, sz(a)) {
      |      ^~~
bridges.cpp:32:31: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridges.cpp:141:7: note: in expansion of macro 'FOR'
  141 |       FOR(x, i, qpos)
      |       ^~~
bridges.cpp:36:31: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   36 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
bridges.cpp:145:7: note: in expansion of macro 'EACH'
  145 |       EACH(x, uedge) {
      |       ^~~~
bridges.cpp:34:28: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
bridges.cpp:153:7: note: in expansion of macro 'FRN'
  153 |       FRN(x, tupd) {
      |       ^~~
bridges.cpp:32:31: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridges.cpp:161:7: note: in expansion of macro 'FOR'
  161 |       FOR(x, i, qpos)
      |       ^~~
bridges.cpp:32:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridges.cpp:165:6: note: in expansion of macro 'FOR'
  165 |      FOR(z, i, j)
      |      ^~~
bridges.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
bridges.cpp:170:5: note: in expansion of macro 'FOR'
  170 |     FOR(i, 1, q)
      |     ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 50 ms 5844 KB Output is correct
4 Correct 13 ms 5512 KB Output is correct
5 Correct 48 ms 5324 KB Output is correct
6 Correct 44 ms 5404 KB Output is correct
7 Correct 46 ms 5280 KB Output is correct
8 Correct 50 ms 5352 KB Output is correct
9 Correct 60 ms 5332 KB Output is correct
10 Correct 48 ms 5364 KB Output is correct
11 Correct 44 ms 5328 KB Output is correct
12 Correct 52 ms 5324 KB Output is correct
13 Correct 48 ms 5332 KB Output is correct
14 Correct 49 ms 5424 KB Output is correct
15 Correct 49 ms 5324 KB Output is correct
16 Correct 50 ms 5288 KB Output is correct
17 Correct 52 ms 5280 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1694 ms 213904 KB Output is correct
2 Correct 1688 ms 213784 KB Output is correct
3 Correct 1688 ms 213756 KB Output is correct
4 Correct 1684 ms 213824 KB Output is correct
5 Correct 1743 ms 213764 KB Output is correct
6 Correct 2031 ms 213912 KB Output is correct
7 Correct 2024 ms 214452 KB Output is correct
8 Correct 1993 ms 214604 KB Output is correct
9 Correct 152 ms 10316 KB Output is correct
10 Correct 1067 ms 210160 KB Output is correct
11 Correct 1014 ms 210184 KB Output is correct
12 Correct 1286 ms 215292 KB Output is correct
13 Correct 1518 ms 213432 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1162 ms 143280 KB Output is correct
2 Correct 774 ms 42052 KB Output is correct
3 Correct 1341 ms 143096 KB Output is correct
4 Correct 1174 ms 143240 KB Output is correct
5 Correct 156 ms 10296 KB Output is correct
6 Correct 1231 ms 143556 KB Output is correct
7 Correct 1057 ms 143100 KB Output is correct
8 Correct 994 ms 142744 KB Output is correct
9 Correct 881 ms 144712 KB Output is correct
10 Correct 873 ms 144580 KB Output is correct
11 Correct 876 ms 140900 KB Output is correct
12 Correct 843 ms 139480 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2434 ms 419944 KB Output is correct
2 Correct 140 ms 10316 KB Output is correct
3 Correct 209 ms 51704 KB Output is correct
4 Correct 129 ms 48556 KB Output is correct
5 Correct 1326 ms 414960 KB Output is correct
6 Correct 2270 ms 420216 KB Output is correct
7 Correct 1259 ms 414816 KB Output is correct
8 Correct 1105 ms 215412 KB Output is correct
9 Correct 1109 ms 215208 KB Output is correct
10 Correct 987 ms 215616 KB Output is correct
11 Correct 1689 ms 317592 KB Output is correct
12 Correct 1756 ms 317572 KB Output is correct
13 Correct 1556 ms 318184 KB Output is correct
14 Correct 1275 ms 414900 KB Output is correct
15 Correct 1283 ms 415168 KB Output is correct
16 Correct 2329 ms 416336 KB Output is correct
17 Correct 2630 ms 415912 KB Output is correct
18 Correct 2702 ms 417484 KB Output is correct
19 Correct 2463 ms 416504 KB Output is correct
20 Correct 1806 ms 352464 KB Output is correct
21 Correct 1749 ms 352304 KB Output is correct
22 Correct 2225 ms 400388 KB Output is correct
23 Correct 1223 ms 334272 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1694 ms 213904 KB Output is correct
2 Correct 1688 ms 213784 KB Output is correct
3 Correct 1688 ms 213756 KB Output is correct
4 Correct 1684 ms 213824 KB Output is correct
5 Correct 1743 ms 213764 KB Output is correct
6 Correct 2031 ms 213912 KB Output is correct
7 Correct 2024 ms 214452 KB Output is correct
8 Correct 1993 ms 214604 KB Output is correct
9 Correct 152 ms 10316 KB Output is correct
10 Correct 1067 ms 210160 KB Output is correct
11 Correct 1014 ms 210184 KB Output is correct
12 Correct 1286 ms 215292 KB Output is correct
13 Correct 1518 ms 213432 KB Output is correct
14 Correct 1162 ms 143280 KB Output is correct
15 Correct 774 ms 42052 KB Output is correct
16 Correct 1341 ms 143096 KB Output is correct
17 Correct 1174 ms 143240 KB Output is correct
18 Correct 156 ms 10296 KB Output is correct
19 Correct 1231 ms 143556 KB Output is correct
20 Correct 1057 ms 143100 KB Output is correct
21 Correct 994 ms 142744 KB Output is correct
22 Correct 881 ms 144712 KB Output is correct
23 Correct 873 ms 144580 KB Output is correct
24 Correct 876 ms 140900 KB Output is correct
25 Correct 843 ms 139480 KB Output is correct
26 Correct 1616 ms 214036 KB Output is correct
27 Correct 1895 ms 213708 KB Output is correct
28 Correct 1607 ms 213852 KB Output is correct
29 Correct 1358 ms 212452 KB Output is correct
30 Correct 1721 ms 214168 KB Output is correct
31 Correct 1764 ms 213996 KB Output is correct
32 Correct 1859 ms 214264 KB Output is correct
33 Correct 1763 ms 213892 KB Output is correct
34 Correct 1592 ms 213676 KB Output is correct
35 Correct 1687 ms 213692 KB Output is correct
36 Correct 1507 ms 212452 KB Output is correct
37 Correct 1465 ms 212480 KB Output is correct
38 Correct 1471 ms 212444 KB Output is correct
39 Correct 1235 ms 214440 KB Output is correct
40 Correct 1217 ms 214540 KB Output is correct
41 Correct 1137 ms 214200 KB Output is correct
42 Correct 1299 ms 202796 KB Output is correct
43 Correct 1137 ms 203632 KB Output is correct
44 Correct 1238 ms 201776 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 50 ms 5844 KB Output is correct
4 Correct 13 ms 5512 KB Output is correct
5 Correct 48 ms 5324 KB Output is correct
6 Correct 44 ms 5404 KB Output is correct
7 Correct 46 ms 5280 KB Output is correct
8 Correct 50 ms 5352 KB Output is correct
9 Correct 60 ms 5332 KB Output is correct
10 Correct 48 ms 5364 KB Output is correct
11 Correct 44 ms 5328 KB Output is correct
12 Correct 52 ms 5324 KB Output is correct
13 Correct 48 ms 5332 KB Output is correct
14 Correct 49 ms 5424 KB Output is correct
15 Correct 49 ms 5324 KB Output is correct
16 Correct 50 ms 5288 KB Output is correct
17 Correct 52 ms 5280 KB Output is correct
18 Correct 1694 ms 213904 KB Output is correct
19 Correct 1688 ms 213784 KB Output is correct
20 Correct 1688 ms 213756 KB Output is correct
21 Correct 1684 ms 213824 KB Output is correct
22 Correct 1743 ms 213764 KB Output is correct
23 Correct 2031 ms 213912 KB Output is correct
24 Correct 2024 ms 214452 KB Output is correct
25 Correct 1993 ms 214604 KB Output is correct
26 Correct 152 ms 10316 KB Output is correct
27 Correct 1067 ms 210160 KB Output is correct
28 Correct 1014 ms 210184 KB Output is correct
29 Correct 1286 ms 215292 KB Output is correct
30 Correct 1518 ms 213432 KB Output is correct
31 Correct 1162 ms 143280 KB Output is correct
32 Correct 774 ms 42052 KB Output is correct
33 Correct 1341 ms 143096 KB Output is correct
34 Correct 1174 ms 143240 KB Output is correct
35 Correct 156 ms 10296 KB Output is correct
36 Correct 1231 ms 143556 KB Output is correct
37 Correct 1057 ms 143100 KB Output is correct
38 Correct 994 ms 142744 KB Output is correct
39 Correct 881 ms 144712 KB Output is correct
40 Correct 873 ms 144580 KB Output is correct
41 Correct 876 ms 140900 KB Output is correct
42 Correct 843 ms 139480 KB Output is correct
43 Correct 2434 ms 419944 KB Output is correct
44 Correct 140 ms 10316 KB Output is correct
45 Correct 209 ms 51704 KB Output is correct
46 Correct 129 ms 48556 KB Output is correct
47 Correct 1326 ms 414960 KB Output is correct
48 Correct 2270 ms 420216 KB Output is correct
49 Correct 1259 ms 414816 KB Output is correct
50 Correct 1105 ms 215412 KB Output is correct
51 Correct 1109 ms 215208 KB Output is correct
52 Correct 987 ms 215616 KB Output is correct
53 Correct 1689 ms 317592 KB Output is correct
54 Correct 1756 ms 317572 KB Output is correct
55 Correct 1556 ms 318184 KB Output is correct
56 Correct 1275 ms 414900 KB Output is correct
57 Correct 1283 ms 415168 KB Output is correct
58 Correct 2329 ms 416336 KB Output is correct
59 Correct 2630 ms 415912 KB Output is correct
60 Correct 2702 ms 417484 KB Output is correct
61 Correct 2463 ms 416504 KB Output is correct
62 Correct 1806 ms 352464 KB Output is correct
63 Correct 1749 ms 352304 KB Output is correct
64 Correct 2225 ms 400388 KB Output is correct
65 Correct 1223 ms 334272 KB Output is correct
66 Correct 1616 ms 214036 KB Output is correct
67 Correct 1895 ms 213708 KB Output is correct
68 Correct 1607 ms 213852 KB Output is correct
69 Correct 1358 ms 212452 KB Output is correct
70 Correct 1721 ms 214168 KB Output is correct
71 Correct 1764 ms 213996 KB Output is correct
72 Correct 1859 ms 214264 KB Output is correct
73 Correct 1763 ms 213892 KB Output is correct
74 Correct 1592 ms 213676 KB Output is correct
75 Correct 1687 ms 213692 KB Output is correct
76 Correct 1507 ms 212452 KB Output is correct
77 Correct 1465 ms 212480 KB Output is correct
78 Correct 1471 ms 212444 KB Output is correct
79 Correct 1235 ms 214440 KB Output is correct
80 Correct 1217 ms 214540 KB Output is correct
81 Correct 1137 ms 214200 KB Output is correct
82 Correct 1299 ms 202796 KB Output is correct
83 Correct 1137 ms 203632 KB Output is correct
84 Correct 1238 ms 201776 KB Output is correct
85 Correct 2825 ms 418160 KB Output is correct
86 Correct 248 ms 51952 KB Output is correct
87 Correct 172 ms 48600 KB Output is correct
88 Correct 1786 ms 413904 KB Output is correct
89 Correct 2946 ms 418112 KB Output is correct
90 Correct 1696 ms 416132 KB Output is correct
91 Correct 1679 ms 216656 KB Output is correct
92 Correct 1588 ms 216516 KB Output is correct
93 Correct 2036 ms 217024 KB Output is correct
94 Correct 2195 ms 319048 KB Output is correct
95 Correct 2321 ms 319420 KB Output is correct
96 Correct 2371 ms 320060 KB Output is correct
97 Correct 1351 ms 417412 KB Output is correct
98 Correct 1332 ms 414872 KB Output is correct
99 Correct 2676 ms 418460 KB Output is correct
100 Correct 2718 ms 417748 KB Output is correct
101 Correct 2712 ms 419520 KB Output is correct
102 Correct 2902 ms 418480 KB Output is correct
103 Correct 2704 ms 354364 KB Output is correct
104 Correct 2633 ms 354156 KB Output is correct
105 Correct 2275 ms 353056 KB Output is correct
106 Correct 1905 ms 318560 KB Output is correct
107 Correct 1945 ms 355524 KB Output is correct
108 Correct 2768 ms 402372 KB Output is correct
109 Correct 1755 ms 335000 KB Output is correct