oj.uz

Submission #487089

# Submission time Handle Problem Language Result Execution time Memory
487089 2021-11-14T04:28:41 Z wwdd Road Closures (APIO21_roads) C++14
100 / 100
 736 ms 518684 KB 
//wtf is this
#include "roads.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
const ll INFL = 1e18;
const ll BIG = 1e10;

class ST {
	private:
	struct NO {
		NO *lf,*rt;
		ll su, kt;
		NO() {
			su = kt = 0;
			lf = rt = nullptr;
		}
		NO(ll val) {
			su = val;
			kt = 1;
			lf = rt = nullptr;
		}
	};
	ll get(NO* no, ll l, ll r, ll q) {
		if(no->kt < q) {
			return INFL;
		}
		if(q <= 0) {return 0;}
		if(l == r) {
			return l*q;
		}
		ll m = (l+r)/2;
		ll ans = 0;
		if(no->lf != nullptr) {
			if(no->lf->kt >= q) {
				return get(no->lf,l,m,q);
			} else {
				ans += no->lf->su;
				q -= no->lf->kt;
			}
		}
		if(no->rt != nullptr) {
			ans += get(no->rt,m+1,r,q);
		}
		return ans;
	}
	vector<NO*> st;
	ll subz,sukt;
	void ens(NO* no, ll l, ll r, ll val, ll num) {
		no->su += val*num;
		no->kt += num;
		if(l == r) {
			return;
		}
		ll m = (l+r)/2;
		if(val <= m) {
			if(no->lf == nullptr) {
				NO* nx = new NO();
				st.push_back(nx);
				no->lf = nx;
			}
			ens(no->lf,l,m,val,num);
		} else {
			if(no->rt == nullptr) {
				NO* nx = new NO();
				st.push_back(nx);
				no->rt = nx;
			}
			ens(no->rt,m+1,r,val,num);
		}
	}
	ll ls, rs;
	public:
	ST(ll ls_, ll rs_) {
		ls = ls_;
		rs = rs_;
		st.push_back(new NO());
		sukt = subz = 0;
	}
	ll get(ll q) {
		ll ad = subz;
		q -= sukt;
		return ad+get(st.front(),ls,rs,q);
	}
	void ens(ll val) {
		if(val < 0) {
			subz += val;
			sukt++;
		} else {
			ens(st.front(),ls,rs,val,1);
		}
	}
	void del(ll val) {
		if(val < 0) {
			subz -= val;
			sukt--;
		} else {
			ens(st.front(),ls,rs,val,-1);
		}
	}
};

vl degs;
vector<vector<ii>> h;
vector<ST> wos;
vl lov;
pl dfs(ll u, ll p, int deg) {
	lov[u] = deg;
	ll ad = 0;
	vector<pl> difs;
	ll rek = degs[u]-deg;
	for(int i=0;i<h[u].size();i++) {
		int v = h[u][i].first;
		ll c = h[u][i].second;
		if(v == p) {
			wos[u].del(c);
			difs.emplace_back(c,-INFL);
			continue;
		}
		pl res = dfs(v,u,deg);
		if(res.first >= INFL) {
			difs.emplace_back(c,-INFL);
			wos[u].del(c);
			rek--;
			ad += c+res.second;
		} else {
			difs.emplace_back(c,c+res.second-res.first);
			wos[u].del(c);
			wos[u].ens(c+res.second-res.first);
			ad += res.first;
		}
	}
	pl ans = {wos[u].get(rek)+ad,wos[u].get(rek-1)+ad};
	for(const auto& it: difs) {
		if(it.second > -INFL) {
			wos[u].del(it.second);
		}
		wos[u].ens(it.first);
	}
	return ans;
}
vector<vector<ii> > g;
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
		std::vector<int> V,
		std::vector<int> W) {
	ll sus = 0;
	int M = U.size();
	degs.assign(N,0);
	g.resize(N);
	for(int i=0;i<M;i++) {
		int u = U[i];
		int v = V[i];
		int c = W[i];
		g[u].emplace_back(v,c);
		g[v].emplace_back(u,c);
		sus += c;
		degs[u]++;
		degs[v]++;
	}
	vector<ii> ord;
	for(int i=0;i<N;i++) {
		ord.emplace_back(degs[i],i);
	}
	sort(ord.begin(),ord.end());
	vi rord(N);
	for(int i=0;i<ord.size();i++) {
		rord[ord[i].second] = i;
	}
	int pt = N-1;
	for(int i=0;i<N;i++) {
		wos.emplace_back(0,BIG);
	}
	for(int i=0;i<N;i++) {
		for(const auto& eg: g[i]) {
			int c = eg.second;
			wos[i].ens(c);
		}
	}
	h.resize(N);
	lov.assign(N,N);
	vector<ll> ans(N);
	for(int dv=N-1;dv>=1;dv--) {
		while(pt >= 0 && degs[ord[pt].second] > dv) {
			int u = ord[pt].second;
			for(const auto& eg: g[u]) {
				int v = eg.first;
				int c = eg.second;
				if(rord[v] > rord[u]) {
					h[u].emplace_back(v,c);
					h[v].emplace_back(u,c);
				}
			}
			pt--;
		}
		ll res = 0;
		for(int i=N-1;i>pt;i--) {
			int u = ord[i].second;
			if(lov[u] > dv) {
				res += dfs(u,u,dv).first;
			}
		}
		ans[dv] = res;
	}
	ans[0] = sus;
	return ans;
}

Compilation message

roads.cpp: In function 'pl dfs(ll, ll, int)':
roads.cpp:119:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for(int i=0;i<h[u].size();i++) {
      |              ~^~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:173:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |  for(int i=0;i<ord.size();i++) {
      |              ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 8 ms 6724 KB Output is correct
3 Correct 9 ms 7236 KB Output is correct
4 Correct 6 ms 5036 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 676 KB Output is correct
8 Correct 5 ms 4252 KB Output is correct
9 Correct 6 ms 4940 KB Output is correct
10 Correct 1 ms 672 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 171 ms 143288 KB Output is correct
13 Correct 283 ms 237584 KB Output is correct
14 Correct 374 ms 277628 KB Output is correct
15 Correct 426 ms 312524 KB Output is correct
16 Correct 420 ms 313900 KB Output is correct
17 Correct 277 ms 241240 KB Output is correct
18 Correct 0 ms 292 KB Output is correct
19 Correct 247 ms 217432 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 604 ms 444564 KB Output is correct
3 Correct 629 ms 453716 KB Output is correct
4 Correct 736 ms 518684 KB Output is correct
5 Correct 516 ms 367660 KB Output is correct
6 Correct 12 ms 9540 KB Output is correct
7 Correct 14 ms 10208 KB Output is correct
8 Correct 8 ms 6888 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 2 ms 1100 KB Output is correct
11 Correct 1 ms 972 KB Output is correct
12 Correct 260 ms 171200 KB Output is correct
13 Correct 474 ms 283192 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 370 ms 244396 KB Output is correct
16 Correct 414 ms 271304 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 2 ms 1028 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 2 ms 1100 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 2 ms 1100 KB Output is correct
11 Correct 2 ms 1100 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Correct 1 ms 972 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 716 KB Output is correct
18 Correct 1 ms 716 KB Output is correct
19 Correct 1 ms 716 KB Output is correct
20 Correct 1 ms 672 KB Output is correct
21 Correct 0 ms 236 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 2 ms 1028 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 2 ms 1100 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 2 ms 1100 KB Output is correct
11 Correct 2 ms 1100 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Correct 1 ms 972 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 716 KB Output is correct
18 Correct 1 ms 716 KB Output is correct
19 Correct 1 ms 716 KB Output is correct
20 Correct 1 ms 672 KB Output is correct
21 Correct 0 ms 236 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 8 ms 5964 KB Output is correct
24 Correct 14 ms 9360 KB Output is correct
25 Correct 6 ms 4556 KB Output is correct
26 Correct 8 ms 5196 KB Output is correct
27 Correct 14 ms 8360 KB Output is correct
28 Correct 8 ms 5032 KB Output is correct
29 Correct 17 ms 8780 KB Output is correct
30 Correct 12 ms 8652 KB Output is correct
31 Correct 7 ms 5196 KB Output is correct
32 Correct 7 ms 5068 KB Output is correct
33 Correct 14 ms 9520 KB Output is correct
34 Correct 16 ms 10316 KB Output is correct
35 Correct 10 ms 6792 KB Output is correct
36 Correct 9 ms 6724 KB Output is correct
37 Correct 10 ms 7224 KB Output is correct
38 Correct 8 ms 5068 KB Output is correct
39 Correct 0 ms 204 KB Output is correct
40 Correct 0 ms 204 KB Output is correct
41 Correct 1 ms 972 KB Output is correct
42 Correct 1 ms 1100 KB Output is correct
43 Correct 1 ms 716 KB Output is correct
44 Correct 1 ms 1100 KB Output is correct
45 Correct 2 ms 844 KB Output is correct
46 Correct 1 ms 1100 KB Output is correct
47 Correct 1 ms 1100 KB Output is correct
48 Correct 2 ms 1100 KB Output is correct
49 Correct 1 ms 972 KB Output is correct
50 Correct 1 ms 716 KB Output is correct
51 Correct 1 ms 932 KB Output is correct
52 Correct 1 ms 716 KB Output is correct
53 Correct 9 ms 4232 KB Output is correct
54 Correct 8 ms 5324 KB Output is correct
55 Correct 9 ms 5040 KB Output is correct
56 Correct 7 ms 4236 KB Output is correct
57 Correct 6 ms 5068 KB Output is correct
58 Correct 1 ms 460 KB Output is correct
59 Correct 1 ms 716 KB Output is correct
60 Correct 1 ms 716 KB Output is correct
61 Correct 1 ms 716 KB Output is correct
62 Correct 1 ms 716 KB Output is correct
63 Correct 0 ms 204 KB Output is correct
64 Correct 7 ms 5040 KB Output is correct
65 Correct 8 ms 5168 KB Output is correct
66 Correct 7 ms 5068 KB Output is correct
67 Correct 6 ms 5060 KB Output is correct
68 Correct 6 ms 5068 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 234896 KB Output is correct
2 Correct 429 ms 230760 KB Output is correct
3 Correct 341 ms 241204 KB Output is correct
4 Correct 439 ms 242956 KB Output is correct
5 Correct 333 ms 241372 KB Output is correct
6 Correct 331 ms 240812 KB Output is correct
7 Correct 377 ms 241676 KB Output is correct
8 Correct 267 ms 222268 KB Output is correct
9 Correct 478 ms 231844 KB Output is correct
10 Correct 423 ms 236064 KB Output is correct
11 Correct 351 ms 241172 KB Output is correct
12 Correct 299 ms 240796 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 374 ms 244512 KB Output is correct
15 Correct 430 ms 271268 KB Output is correct
16 Correct 7 ms 5068 KB Output is correct
17 Correct 8 ms 5068 KB Output is correct
18 Correct 7 ms 5068 KB Output is correct
19 Correct 6 ms 5068 KB Output is correct
20 Correct 7 ms 5068 KB Output is correct
21 Correct 250 ms 217332 KB Output is correct

Subtask #6
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 234896 KB Output is correct
2 Correct 429 ms 230760 KB Output is correct
3 Correct 341 ms 241204 KB Output is correct
4 Correct 439 ms 242956 KB Output is correct
5 Correct 333 ms 241372 KB Output is correct
6 Correct 331 ms 240812 KB Output is correct
7 Correct 377 ms 241676 KB Output is correct
8 Correct 267 ms 222268 KB Output is correct
9 Correct 478 ms 231844 KB Output is correct
10 Correct 423 ms 236064 KB Output is correct
11 Correct 351 ms 241172 KB Output is correct
12 Correct 299 ms 240796 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 374 ms 244512 KB Output is correct
15 Correct 430 ms 271268 KB Output is correct
16 Correct 7 ms 5068 KB Output is correct
17 Correct 8 ms 5068 KB Output is correct
18 Correct 7 ms 5068 KB Output is correct
19 Correct 6 ms 5068 KB Output is correct
20 Correct 7 ms 5068 KB Output is correct
21 Correct 250 ms 217332 KB Output is correct
22 Correct 0 ms 292 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 1 ms 224 KB Output is correct
25 Correct 396 ms 217704 KB Output is correct
26 Correct 349 ms 196492 KB Output is correct
27 Correct 466 ms 253464 KB Output is correct
28 Correct 369 ms 238784 KB Output is correct
29 Correct 320 ms 220248 KB Output is correct
30 Correct 310 ms 228972 KB Output is correct
31 Correct 310 ms 234756 KB Output is correct
32 Correct 412 ms 223912 KB Output is correct
33 Correct 262 ms 224636 KB Output is correct
34 Correct 395 ms 245268 KB Output is correct
35 Correct 525 ms 262536 KB Output is correct
36 Correct 332 ms 238700 KB Output is correct
37 Correct 303 ms 237976 KB Output is correct
38 Correct 260 ms 171276 KB Output is correct
39 Correct 429 ms 283108 KB Output is correct
40 Correct 6 ms 4172 KB Output is correct
41 Correct 8 ms 5296 KB Output is correct
42 Correct 6 ms 5036 KB Output is correct
43 Correct 4 ms 4300 KB Output is correct
44 Correct 6 ms 4944 KB Output is correct
45 Correct 1 ms 460 KB Output is correct
46 Correct 1 ms 716 KB Output is correct
47 Correct 1 ms 672 KB Output is correct
48 Correct 1 ms 716 KB Output is correct
49 Correct 1 ms 716 KB Output is correct
50 Correct 163 ms 143208 KB Output is correct
51 Correct 289 ms 237624 KB Output is correct
52 Correct 417 ms 234868 KB Output is correct
53 Correct 407 ms 230824 KB Output is correct
54 Correct 347 ms 241188 KB Output is correct
55 Correct 434 ms 243088 KB Output is correct
56 Correct 330 ms 241292 KB Output is correct
57 Correct 324 ms 240812 KB Output is correct
58 Correct 376 ms 241644 KB Output is correct
59 Correct 243 ms 222404 KB Output is correct
60 Correct 462 ms 231940 KB Output is correct
61 Correct 429 ms 236016 KB Output is correct
62 Correct 322 ms 241060 KB Output is correct
63 Correct 294 ms 240836 KB Output is correct
64 Correct 0 ms 292 KB Output is correct
65 Correct 397 ms 244540 KB Output is correct
66 Correct 426 ms 271356 KB Output is correct
67 Correct 7 ms 5068 KB Output is correct
68 Correct 7 ms 5068 KB Output is correct
69 Correct 6 ms 5068 KB Output is correct
70 Correct 6 ms 5068 KB Output is correct
71 Correct 7 ms 5036 KB Output is correct
72 Correct 245 ms 217324 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 8 ms 6724 KB Output is correct
3 Correct 9 ms 7236 KB Output is correct
4 Correct 6 ms 5036 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 676 KB Output is correct
8 Correct 5 ms 4252 KB Output is correct
9 Correct 6 ms 4940 KB Output is correct
10 Correct 1 ms 672 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 171 ms 143288 KB Output is correct
13 Correct 283 ms 237584 KB Output is correct
14 Correct 374 ms 277628 KB Output is correct
15 Correct 426 ms 312524 KB Output is correct
16 Correct 420 ms 313900 KB Output is correct
17 Correct 277 ms 241240 KB Output is correct
18 Correct 0 ms 292 KB Output is correct
19 Correct 247 ms 217432 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 604 ms 444564 KB Output is correct
22 Correct 629 ms 453716 KB Output is correct
23 Correct 736 ms 518684 KB Output is correct
24 Correct 516 ms 367660 KB Output is correct
25 Correct 12 ms 9540 KB Output is correct
26 Correct 14 ms 10208 KB Output is correct
27 Correct 8 ms 6888 KB Output is correct
28 Correct 2 ms 1100 KB Output is correct
29 Correct 2 ms 1100 KB Output is correct
30 Correct 1 ms 972 KB Output is correct
31 Correct 260 ms 171200 KB Output is correct
32 Correct 474 ms 283192 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 370 ms 244396 KB Output is correct
35 Correct 414 ms 271304 KB Output is correct
36 Correct 0 ms 204 KB Output is correct
37 Correct 0 ms 296 KB Output is correct
38 Correct 0 ms 204 KB Output is correct
39 Correct 2 ms 1028 KB Output is correct
40 Correct 2 ms 1100 KB Output is correct
41 Correct 1 ms 716 KB Output is correct
42 Correct 2 ms 1100 KB Output is correct
43 Correct 1 ms 844 KB Output is correct
44 Correct 2 ms 1100 KB Output is correct
45 Correct 2 ms 1100 KB Output is correct
46 Correct 2 ms 1100 KB Output is correct
47 Correct 2 ms 972 KB Output is correct
48 Correct 2 ms 716 KB Output is correct
49 Correct 1 ms 972 KB Output is correct
50 Correct 1 ms 716 KB Output is correct
51 Correct 1 ms 460 KB Output is correct
52 Correct 1 ms 716 KB Output is correct
53 Correct 1 ms 716 KB Output is correct
54 Correct 1 ms 716 KB Output is correct
55 Correct 1 ms 672 KB Output is correct
56 Correct 0 ms 236 KB Output is correct
57 Correct 1 ms 204 KB Output is correct
58 Correct 8 ms 5964 KB Output is correct
59 Correct 14 ms 9360 KB Output is correct
60 Correct 6 ms 4556 KB Output is correct
61 Correct 8 ms 5196 KB Output is correct
62 Correct 14 ms 8360 KB Output is correct
63 Correct 8 ms 5032 KB Output is correct
64 Correct 17 ms 8780 KB Output is correct
65 Correct 12 ms 8652 KB Output is correct
66 Correct 7 ms 5196 KB Output is correct
67 Correct 7 ms 5068 KB Output is correct
68 Correct 14 ms 9520 KB Output is correct
69 Correct 16 ms 10316 KB Output is correct
70 Correct 10 ms 6792 KB Output is correct
71 Correct 9 ms 6724 KB Output is correct
72 Correct 10 ms 7224 KB Output is correct
73 Correct 8 ms 5068 KB Output is correct
74 Correct 0 ms 204 KB Output is correct
75 Correct 0 ms 204 KB Output is correct
76 Correct 1 ms 972 KB Output is correct
77 Correct 1 ms 1100 KB Output is correct
78 Correct 1 ms 716 KB Output is correct
79 Correct 1 ms 1100 KB Output is correct
80 Correct 2 ms 844 KB Output is correct
81 Correct 1 ms 1100 KB Output is correct
82 Correct 1 ms 1100 KB Output is correct
83 Correct 2 ms 1100 KB Output is correct
84 Correct 1 ms 972 KB Output is correct
85 Correct 1 ms 716 KB Output is correct
86 Correct 1 ms 932 KB Output is correct
87 Correct 1 ms 716 KB Output is correct
88 Correct 9 ms 4232 KB Output is correct
89 Correct 8 ms 5324 KB Output is correct
90 Correct 9 ms 5040 KB Output is correct
91 Correct 7 ms 4236 KB Output is correct
92 Correct 6 ms 5068 KB Output is correct
93 Correct 1 ms 460 KB Output is correct
94 Correct 1 ms 716 KB Output is correct
95 Correct 1 ms 716 KB Output is correct
96 Correct 1 ms 716 KB Output is correct
97 Correct 1 ms 716 KB Output is correct
98 Correct 0 ms 204 KB Output is correct
99 Correct 7 ms 5040 KB Output is correct
100 Correct 8 ms 5168 KB Output is correct
101 Correct 7 ms 5068 KB Output is correct
102 Correct 6 ms 5060 KB Output is correct
103 Correct 6 ms 5068 KB Output is correct
104 Correct 443 ms 234896 KB Output is correct
105 Correct 429 ms 230760 KB Output is correct
106 Correct 341 ms 241204 KB Output is correct
107 Correct 439 ms 242956 KB Output is correct
108 Correct 333 ms 241372 KB Output is correct
109 Correct 331 ms 240812 KB Output is correct
110 Correct 377 ms 241676 KB Output is correct
111 Correct 267 ms 222268 KB Output is correct
112 Correct 478 ms 231844 KB Output is correct
113 Correct 423 ms 236064 KB Output is correct
114 Correct 351 ms 241172 KB Output is correct
115 Correct 299 ms 240796 KB Output is correct
116 Correct 0 ms 204 KB Output is correct
117 Correct 374 ms 244512 KB Output is correct
118 Correct 430 ms 271268 KB Output is correct
119 Correct 7 ms 5068 KB Output is correct
120 Correct 8 ms 5068 KB Output is correct
121 Correct 7 ms 5068 KB Output is correct
122 Correct 6 ms 5068 KB Output is correct
123 Correct 7 ms 5068 KB Output is correct
124 Correct 250 ms 217332 KB Output is correct
125 Correct 0 ms 292 KB Output is correct
126 Correct 0 ms 204 KB Output is correct
127 Correct 1 ms 224 KB Output is correct
128 Correct 396 ms 217704 KB Output is correct
129 Correct 349 ms 196492 KB Output is correct
130 Correct 466 ms 253464 KB Output is correct
131 Correct 369 ms 238784 KB Output is correct
132 Correct 320 ms 220248 KB Output is correct
133 Correct 310 ms 228972 KB Output is correct
134 Correct 310 ms 234756 KB Output is correct
135 Correct 412 ms 223912 KB Output is correct
136 Correct 262 ms 224636 KB Output is correct
137 Correct 395 ms 245268 KB Output is correct
138 Correct 525 ms 262536 KB Output is correct
139 Correct 332 ms 238700 KB Output is correct
140 Correct 303 ms 237976 KB Output is correct
141 Correct 260 ms 171276 KB Output is correct
142 Correct 429 ms 283108 KB Output is correct
143 Correct 6 ms 4172 KB Output is correct
144 Correct 8 ms 5296 KB Output is correct
145 Correct 6 ms 5036 KB Output is correct
146 Correct 4 ms 4300 KB Output is correct
147 Correct 6 ms 4944 KB Output is correct
148 Correct 1 ms 460 KB Output is correct
149 Correct 1 ms 716 KB Output is correct
150 Correct 1 ms 672 KB Output is correct
151 Correct 1 ms 716 KB Output is correct
152 Correct 1 ms 716 KB Output is correct
153 Correct 163 ms 143208 KB Output is correct
154 Correct 289 ms 237624 KB Output is correct
155 Correct 417 ms 234868 KB Output is correct
156 Correct 407 ms 230824 KB Output is correct
157 Correct 347 ms 241188 KB Output is correct
158 Correct 434 ms 243088 KB Output is correct
159 Correct 330 ms 241292 KB Output is correct
160 Correct 324 ms 240812 KB Output is correct
161 Correct 376 ms 241644 KB Output is correct
162 Correct 243 ms 222404 KB Output is correct
163 Correct 462 ms 231940 KB Output is correct
164 Correct 429 ms 236016 KB Output is correct
165 Correct 322 ms 241060 KB Output is correct
166 Correct 294 ms 240836 KB Output is correct
167 Correct 0 ms 292 KB Output is correct
168 Correct 397 ms 244540 KB Output is correct
169 Correct 426 ms 271356 KB Output is correct
170 Correct 7 ms 5068 KB Output is correct
171 Correct 7 ms 5068 KB Output is correct
172 Correct 6 ms 5068 KB Output is correct
173 Correct 6 ms 5068 KB Output is correct
174 Correct 7 ms 5036 KB Output is correct
175 Correct 245 ms 217324 KB Output is correct
176 Correct 0 ms 204 KB Output is correct
177 Correct 714 ms 459120 KB Output is correct
178 Correct 543 ms 349596 KB Output is correct
179 Correct 354 ms 240408 KB Output is correct
180 Correct 612 ms 382544 KB Output is correct
181 Correct 338 ms 242188 KB Output is correct
182 Correct 329 ms 237216 KB Output is correct
183 Correct 402 ms 250100 KB Output is correct
184 Correct 556 ms 359224 KB Output is correct
185 Correct 525 ms 353684 KB Output is correct
186 Correct 471 ms 338528 KB Output is correct
187 Correct 405 ms 308548 KB Output is correct
188 Correct 413 ms 234264 KB Output is correct
189 Correct 447 ms 265672 KB Output is correct
190 Correct 585 ms 378140 KB Output is correct
191 Correct 335 ms 241432 KB Output is correct
192 Correct 432 ms 320328 KB Output is correct
193 Correct 490 ms 356860 KB Output is correct
194 Correct 332 ms 242728 KB Output is correct
195 Correct 577 ms 444416 KB Output is correct
196 Correct 629 ms 453760 KB Output is correct
197 Correct 698 ms 518620 KB Output is correct
198 Correct 508 ms 367640 KB Output is correct
199 Correct 7 ms 5964 KB Output is correct
200 Correct 12 ms 9292 KB Output is correct
201 Correct 6 ms 4556 KB Output is correct
202 Correct 7 ms 5204 KB Output is correct
203 Correct 11 ms 8376 KB Output is correct
204 Correct 6 ms 5068 KB Output is correct
205 Correct 12 ms 8792 KB Output is correct
206 Correct 11 ms 8652 KB Output is correct
207 Correct 7 ms 5216 KB Output is correct
208 Correct 6 ms 5036 KB Output is correct
209 Correct 12 ms 9444 KB Output is correct
210 Correct 13 ms 10316 KB Output is correct
211 Correct 9 ms 6868 KB Output is correct
212 Correct 8 ms 6724 KB Output is correct
213 Correct 8 ms 7236 KB Output is correct
214 Correct 6 ms 5068 KB Output is correct
215 Correct 0 ms 204 KB Output is correct
216 Correct 1 ms 288 KB Output is correct
217 Correct 1 ms 972 KB Output is correct
218 Correct 1 ms 1100 KB Output is correct
219 Correct 1 ms 716 KB Output is correct
220 Correct 1 ms 1112 KB Output is correct
221 Correct 1 ms 844 KB Output is correct
222 Correct 1 ms 1100 KB Output is correct
223 Correct 1 ms 1100 KB Output is correct
224 Correct 1 ms 1100 KB Output is correct
225 Correct 1 ms 972 KB Output is correct
226 Correct 1 ms 716 KB Output is correct
227 Correct 1 ms 972 KB Output is correct
228 Correct 1 ms 716 KB Output is correct
229 Correct 384 ms 217716 KB Output is correct
230 Correct 350 ms 196520 KB Output is correct
231 Correct 448 ms 253476 KB Output is correct
232 Correct 343 ms 238744 KB Output is correct
233 Correct 312 ms 220324 KB Output is correct
234 Correct 312 ms 229032 KB Output is correct
235 Correct 313 ms 234760 KB Output is correct
236 Correct 398 ms 223904 KB Output is correct
237 Correct 257 ms 224724 KB Output is correct
238 Correct 390 ms 245340 KB Output is correct
239 Correct 518 ms 262564 KB Output is correct
240 Correct 337 ms 238856 KB Output is correct
241 Correct 290 ms 237972 KB Output is correct
242 Correct 260 ms 171248 KB Output is correct
243 Correct 437 ms 283192 KB Output is correct
244 Correct 6 ms 4172 KB Output is correct
245 Correct 7 ms 5352 KB Output is correct
246 Correct 6 ms 5064 KB Output is correct
247 Correct 5 ms 4300 KB Output is correct
248 Correct 8 ms 4940 KB Output is correct
249 Correct 1 ms 460 KB Output is correct
250 Correct 1 ms 716 KB Output is correct
251 Correct 1 ms 716 KB Output is correct
252 Correct 1 ms 716 KB Output is correct
253 Correct 1 ms 716 KB Output is correct
254 Correct 169 ms 143336 KB Output is correct
255 Correct 276 ms 237612 KB Output is correct
256 Correct 375 ms 277756 KB Output is correct
257 Correct 412 ms 312612 KB Output is correct
258 Correct 414 ms 313868 KB Output is correct
259 Correct 275 ms 241228 KB Output is correct
260 Correct 412 ms 235136 KB Output is correct
261 Correct 406 ms 230804 KB Output is correct
262 Correct 343 ms 241296 KB Output is correct
263 Correct 438 ms 242996 KB Output is correct
264 Correct 335 ms 241316 KB Output is correct
265 Correct 323 ms 240784 KB Output is correct
266 Correct 376 ms 241832 KB Output is correct
267 Correct 245 ms 222264 KB Output is correct
268 Correct 448 ms 231712 KB Output is correct
269 Correct 406 ms 236032 KB Output is correct
270 Correct 323 ms 241156 KB Output is correct
271 Correct 292 ms 240788 KB Output is correct
272 Correct 0 ms 204 KB Output is correct
273 Correct 358 ms 244376 KB Output is correct
274 Correct 408 ms 271340 KB Output is correct
275 Correct 7 ms 5068 KB Output is correct
276 Correct 7 ms 5068 KB Output is correct
277 Correct 6 ms 5068 KB Output is correct
278 Correct 7 ms 5068 KB Output is correct
279 Correct 7 ms 5068 KB Output is correct
280 Correct 237 ms 217388 KB Output is correct