oj.uz

Submission #636219

# Submission time Handle Problem Language Result Execution time Memory
636219 2022-08-28T14:31:11 Z kig9981 Thousands Islands (IOI22_islands) C++17
100 / 100
 500 ms 70020 KB 
#include "islands.h"
#include <variant>
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

const int SZ=1<<17;
vector<pair<int,int>> adj[100000];
vector<int> tadj[100000], radj[100000], S, Q[100000], FQ[100000], CQ[100000], ans;
set<pair<int,int>> FE;
map<pair<int,int>,int> E, SE;
int node_cnt, W[100000], num[100000], hld[100000], R[100000], parent[100000], depth[100000], D[100000];
bool chk[100000], DE[100000];
pair<int,int> tree[2*SZ], lazy[2*SZ];

void solution1(int a, int b, int e);
void solution2(int a, int b, pair<int,int> c);
void solution3(pair<int,int> a, pair<int,int> b);
void solution4(int a, int b);

pair<int,int> get_max(pair<int,int> a, pair<int,int> b)
{
	if(a==make_pair(-1,-1)) return b;
	if(b==make_pair(-1,-1)) return a;
	return depth[a.first]>depth[b.first] ? a:b;
}

void lazy_propagation(int bit, int s, int e)
{
	if(lazy[bit]==make_pair(-1,-1)) return;
	tree[bit]=get_max(tree[bit],lazy[bit]);
	if(s<e) {
		lazy[2*bit]=get_max(lazy[2*bit],lazy[bit]);
		lazy[2*bit+1]=get_max(lazy[2*bit+1],lazy[bit]);
	}
	lazy[bit]={-1,-1};
}

void update(int n1, int n2, pair<int,int> v, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1) return;
	if(n1<=s && e<=n2) {
		lazy[bit]=v;
		lazy_propagation(bit,s,e);
		return;
	}
	update(n1,n2,v,2*bit,s,m);
	update(n1,n2,v,2*bit+1,m+1,e);
	tree[bit]=get_max(tree[2*bit],tree[2*bit+1]);
}

pair<int,int> query(int n1, int n2, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1) return {-1,-1};
	if(n1<=s && e<=n2) return tree[bit];
	return get_max(query(n1,n2,2*bit,s,m),query(n1,n2,2*bit+1,m+1,e));
}

void dfs(int c)
{
	S.push_back(c);
	W[c]=chk[c]=true;
	for(auto[n,e]: adj[c]) {
		if(E.count({c,n})) SE[{c,n}]=e;
		else E[{c,n}]=e;
		if(W[n]==0) {
			tadj[c].push_back(n);
			parent[n]=c;
			D[n]=depth[n]=depth[c]+1;
			dfs(n);
			W[c]+=W[n];
		}
		else if(chk[n]) Q[S[depth[n]+1]].push_back(c);
		else if(FE.find({c,n})!=FE.end()) FQ[c].push_back(n);
		else CQ[c].push_back(n);
	}
	for(auto n: radj[c]) if(chk[n]) FE.emplace(n,c);
	chk[c]=false;
	S.pop_back();
}

void dfs2(int c)
{
	int mx=-1;
	num[c]=node_cnt++;
	S.push_back(c);
	for(auto n: Q[c]) {
		if(D[c]==D[parent[c]]) {
			solution1(parent[c],n,SE[{parent[c],c}]);
			return;
		}
		if(DE[parent[c]]) {
			solution4(parent[c],n);
			return;
		}
		auto q=query(num[c],num[c]+W[c]-1);
		if(q!=make_pair(-1,-1)) {
			solution3(q,make_pair(parent[c],n));
			return;
		}
		update(0,num[c]-1,make_pair(parent[c],n));
		update(num[c]+W[c],SZ-1,make_pair(parent[c],n));
	}
	for(auto n: tadj[c]) if(mx==-1 || W[mx]<W[n]) mx=n;
	if(mx==-1) {
		S.pop_back();
		R[c]=node_cnt-1;
		return;
	}
	hld[mx]=hld[c];
	DE[mx]=DE[c];
	if(SE.count({c,mx})) {
		D[mx]=D[c];
		DE[mx]=true;
	}
	dfs2(mx);
	if(ans.size()) return;
	for(auto n: tadj[c]) if(mx!=n) {
		DE[n]=DE[c];
		if(SE.count({c,n})) {
			D[n]=D[c];
			DE[n]=true;
		}
		dfs2(hld[n]=n);
		if(ans.size()) return;
	}
	R[c]=node_cnt-1;
	S.pop_back();
}

void query(int a, int b, pair<int,int> v)
{
	while(hld[a]!=hld[b]) {
		update(num[hld[b]],num[b],v);
		b=parent[hld[b]];
	}
	update(num[a],num[b],v);
}

void dfs3(int c)
{
	for(auto n: tadj[c]) if(parent[n]==c) {
		dfs3(n);
		if(ans.size()) return;
	}
	for(auto n: Q[c]) query(0,n,make_pair(parent[c],n));
	for(auto n: FQ[c]) {
		auto q=query(num[n],num[n]);
		if(q!=make_pair(-1,-1) && depth[c]<=depth[q.first]) {
			solution2(c,n,q);
			return;
		}
	}
	for(auto n: CQ[c]) {
		auto q=query(num[n],num[n]);
		if(q!=make_pair(-1,-1)) {
			solution2(c,n,q);
			return;
		}
	}
}

variant<bool,vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V)
{
	ans.clear(); S.clear(); E.clear(); SE.clear();
	for(int i=0;i<N;i++) {
		adj[i].clear(); Q[i].clear(); FQ[i].clear(); CQ[i].clear();
		tadj[i].clear(); radj[i].clear();
		W[i]=chk[i]=DE[i]=false;
	}
	for(int i=2*SZ;--i;) tree[i]=lazy[i]={-1,-1};
	for(int i=0;i<M;i++) {
		adj[U[i]].emplace_back(V[i],i);
		radj[V[i]].push_back(U[i]);
	}
	dfs(0); dfs2(0);
	if(ans.empty()) {
		for(int i=2*SZ;--i;) tree[i]=lazy[i]={-1,-1};
		dfs3(0);
		if(ans.size()) return ans;
		return false;
	}
	return ans;
}

void solution1(int a, int b, int e)
{
	vector<int> ZA, A, temp;
	A.push_back(a); A.push_back(b); ZA.push_back(a);
	for(int i=a;i;i=parent[i]) ZA.push_back(parent[i]);
	reverse(ZA.begin(),ZA.end());
	swap(temp,ZA); ZA.clear();
	for(int i=1;i<temp.size();i++) ZA.push_back(E[{temp[i-1],temp[i]}]);
	for(int i=b;i!=a;i=parent[i]) A.push_back(parent[i]);
	reverse(A.begin(),A.end());
	swap(temp,A); A.clear();
	for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
	for(auto a: ZA) ans.push_back(a);
	for(auto a: A) ans.push_back(a);
	ans.push_back(e); ans.push_back(A[0]); A[0]=e;
	reverse(A.begin(),A.end()); reverse(ZA.begin(),ZA.end());
	for(auto a: A) ans.push_back(a);
	for(auto a: ZA) ans.push_back(a);
}

void solution2(int a, int b, pair<int,int> c)
{
	vector<int> L, LA, LB, A, B, temp;
	int l, x=a, y=c.first;
	if(depth[x]<depth[y]) swap(x,y);
	while(depth[x]!=depth[y]) x=parent[x];
	while(x!=y) {
		x=parent[x];
		y=parent[y];
	}
	L.push_back(l=x);
	for(int i=l;i;i=parent[i]) L.push_back(parent[i]);
	reverse(L.begin(),L.end());
	swap(temp,L); L.clear();
	for(int i=1;i<temp.size();i++) L.push_back(E[{temp[i-1],temp[i]}]);
	if(depth[c.first]<=depth[b]) {
		LA.push_back(x=c.first); LB.push_back(b); LB.push_back(a);
		for(int i=x;i!=l;i=parent[i]) LA.push_back(parent[i]);
		reverse(LA.begin(),LA.end());
		swap(temp,LA); LA.clear();
		for(int i=1;i<temp.size();i++) LA.push_back(E[{temp[i-1],temp[i]}]);
		for(int i=a;i!=l;i=parent[i]) LB.push_back(parent[i]);
		reverse(LB.begin(),LB.end());
		swap(temp,LB); LB.clear();
		for(int i=1;i<temp.size();i++) LB.push_back(E[{temp[i-1],temp[i]}]);
		A.push_back(x); A.push_back(c.second);
		for(int i=c.second;i!=x;i=parent[i]) A.push_back(parent[i]);
		reverse(A.begin(),A.end());
		for(int i=1;i<A.size();i++) if(A[i]==b) {
			for(int j=i;j<A.size();j++) B.push_back(A[j]);
			for(int j=1;j<=i;j++) B.push_back(A[j]);
			break;
		}
		swap(temp,A); A.clear();
		for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
		swap(temp,B); B.clear();
		for(int i=1;i<temp.size();i++) B.push_back(E[{temp[i-1],temp[i]}]);
		for(auto a: L) ans.push_back(a);
		for(auto a: LA) ans.push_back(a);
		for(auto a: A) ans.push_back(a);
		reverse(LA.begin(),LA.end());
		for(auto a: LA) ans.push_back(a);
		for(auto a: LB) ans.push_back(a);
		reverse(B.begin(),B.end());
		for(auto a: B) ans.push_back(a);
		reverse(LB.begin(),LB.end());
		for(auto a: LB) ans.push_back(a);
		reverse(L.begin(),L.end());
		for(auto a: L) ans.push_back(a);
	}
	else {
		bool r=false;
		LA.push_back(x=c.first); LB.push_back(b); LB.push_back(a);
		for(int i=a;i!=l;i=parent[i]) LB.push_back(parent[i]);
		reverse(LB.begin(),LB.end());
		swap(temp,LB); LB.clear();
		for(int i=1;i<temp.size();i++) LB.push_back(E[{temp[i-1],temp[i]}]);
		for(int i=x;i!=l;i=parent[i]) LA.push_back(parent[i]);
		reverse(LA.begin(),LA.end());
		swap(temp,LA); LA.clear();
		for(int i=1;i<temp.size();i++) {
			LA.push_back(E[{temp[i-1],temp[i]}]);
			if(r) LB.push_back(E[{temp[i-1],temp[i]}]);
			if(temp[i]==b) r=true;
		}
		A.push_back(x); A.push_back(c.second);
		for(int i=c.second;i!=x;i=parent[i]) A.push_back(parent[i]);
		reverse(A.begin(),A.end());
		swap(temp,A); A.clear();
		for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
		for(auto a: L) ans.push_back(a);
		for(auto a: LA) ans.push_back(a);
		for(auto a: A) ans.push_back(a);
		reverse(LA.begin(),LA.end());
		for(auto a: LA) ans.push_back(a);
		for(auto a: LB) ans.push_back(a);
		reverse(A.begin(),A.end());
		for(auto a: A) ans.push_back(a);
		reverse(LB.begin(),LB.end());
		for(auto a: LB) ans.push_back(a);
		reverse(L.begin(),L.end());
		for(auto a: L) ans.push_back(a);
	}
}

void solution3(pair<int,int> a, pair<int,int> b)
{
	vector<int> L, LA, LB, A, B, temp;
	int l, x=a.first, y=b.first;
	if(depth[x]<depth[y]) swap(x,y);
	while(depth[x]!=depth[y]) x=parent[x];
	while(x!=y) {
		x=parent[x];
		y=parent[y];
	}
	L.push_back(l=x);
	for(int i=l;i;i=parent[i]) L.push_back(parent[i]);
	reverse(L.begin(),L.end());
	swap(temp,L); L.clear();
	for(int i=1;i<temp.size();i++) L.push_back(E[{temp[i-1],temp[i]}]);
	A.push_back(x=a.first); B.push_back(y=b.first);
	A.push_back(a.second); B.push_back(b.second);
	LA.push_back(x); LB.push_back(y);
	for(int i=x;i!=l;i=parent[i]) LA.push_back(parent[i]);
	for(int i=y;i!=l;i=parent[i]) LB.push_back(parent[i]);
	reverse(LA.begin(),LA.end()); reverse(LB.begin(),LB.end());
	swap(temp,LA); LA.clear();
	for(int i=1;i<temp.size();i++) LA.push_back(E[{temp[i-1],temp[i]}]);
	swap(temp,LB); LB.clear();
	for(int i=1;i<temp.size();i++) LB.push_back(E[{temp[i-1],temp[i]}]);
	for(int i=a.second;i!=x;i=parent[i]) A.push_back(parent[i]);
	for(int i=b.second;i!=y;i=parent[i]) B.push_back(parent[i]);
	reverse(A.begin(),A.end()); reverse(B.begin(),B.end());
	swap(temp,A); A.clear();
	for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
	swap(temp,B); B.clear();
	for(int i=1;i<temp.size();i++) B.push_back(E[{temp[i-1],temp[i]}]);
	for(auto a: L) ans.push_back(a);
	for(auto a: LA) ans.push_back(a);
	for(auto a: A) ans.push_back(a);
	reverse(LA.begin(),LA.end());
	for(auto a: LA) ans.push_back(a);
	for(auto a: LB) ans.push_back(a);
	for(auto a: B) ans.push_back(a);
	reverse(LB.begin(),LB.end());
	for(auto a: LB) ans.push_back(a);
	reverse(LA.begin(),LA.end());
	for(auto a: LA) ans.push_back(a);
	reverse(A.begin(),A.end());
	for(auto a: A) ans.push_back(a);
	reverse(LA.begin(),LA.end());
	for(auto a: LA) ans.push_back(a);
	reverse(LB.begin(),LB.end());
	for(auto a: LB) ans.push_back(a);
	reverse(B.begin(),B.end());
	for(auto a: B) ans.push_back(a);
	reverse(LB.begin(),LB.end());
	for(auto a: LB) ans.push_back(a);
	reverse(L.begin(),L.end());
	for(auto a: L) ans.push_back(a);
}

void solution4(int a, int b)
{
	vector<int> ZA, A, temp;
	int r=-1, rp=-1;
	A.push_back(a); A.push_back(b); ZA.push_back(a);
	for(int i=a;i;i=parent[i]) ZA.push_back(parent[i]);
	reverse(ZA.begin(),ZA.end());
	swap(temp,ZA); ZA.clear();
	for(int i=1;i<temp.size();i++) {
		ZA.push_back(E[{temp[i-1],temp[i]}]);
		if(r==-1 && SE.count({temp[i-1],temp[i]})) {
			r=SE[{temp[i-1],temp[i]}];
			rp=ZA.size()-1;
		}
	}
	for(int i=b;i!=a;i=parent[i]) A.push_back(parent[i]);
	reverse(A.begin(),A.end());
	swap(temp,A); A.clear();
	for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
	for(auto a: ZA) ans.push_back(a);
	for(auto a: A) ans.push_back(a);
	for(int i=ZA.size();--i>=rp;) ans.push_back(ZA[i]);
	ZA[rp]=r;
	for(int i=rp;i<ZA.size();i++) ans.push_back(ZA[i]);
	reverse(A.begin(),A.end()); reverse(ZA.begin(),ZA.end());
	for(auto a: A) ans.push_back(a);
	for(auto a: ZA) ans.push_back(a);
}

Compilation message

islands.cpp: In function 'void solution1(int, int, int)':
islands.cpp:205:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |  for(int i=1;i<temp.size();i++) ZA.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp:209:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |  for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp: In function 'void solution2(int, int, std::pair<int, int>)':
islands.cpp:232:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  232 |  for(int i=1;i<temp.size();i++) L.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp:238:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  238 |   for(int i=1;i<temp.size();i++) LA.push_back(E[{temp[i-1],temp[i]}]);
      |               ~^~~~~~~~~~~~
islands.cpp:242:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  242 |   for(int i=1;i<temp.size();i++) LB.push_back(E[{temp[i-1],temp[i]}]);
      |               ~^~~~~~~~~~~~
islands.cpp:246:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  246 |   for(int i=1;i<A.size();i++) if(A[i]==b) {
      |               ~^~~~~~~~~
islands.cpp:247:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  247 |    for(int j=i;j<A.size();j++) B.push_back(A[j]);
      |                ~^~~~~~~~~
islands.cpp:252:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  252 |   for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
      |               ~^~~~~~~~~~~~
islands.cpp:254:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  254 |   for(int i=1;i<temp.size();i++) B.push_back(E[{temp[i-1],temp[i]}]);
      |               ~^~~~~~~~~~~~
islands.cpp:274:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  274 |   for(int i=1;i<temp.size();i++) LB.push_back(E[{temp[i-1],temp[i]}]);
      |               ~^~~~~~~~~~~~
islands.cpp:278:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  278 |   for(int i=1;i<temp.size();i++) {
      |               ~^~~~~~~~~~~~
islands.cpp:287:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  287 |   for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
      |               ~^~~~~~~~~~~~
islands.cpp: In function 'void solution3(std::pair<int, int>, std::pair<int, int>)':
islands.cpp:317:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  317 |  for(int i=1;i<temp.size();i++) L.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp:325:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  325 |  for(int i=1;i<temp.size();i++) LA.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp:327:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  327 |  for(int i=1;i<temp.size();i++) LB.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp:332:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  332 |  for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp:334:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  334 |  for(int i=1;i<temp.size();i++) B.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp: In function 'void solution4(int, int)':
islands.cpp:368:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  368 |  for(int i=1;i<temp.size();i++) {
      |              ~^~~~~~~~~~~~
islands.cpp:378:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  378 |  for(int i=1;i<temp.size();i++) A.push_back(E[{temp[i-1],temp[i]}]);
      |              ~^~~~~~~~~~~~
islands.cpp:383:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  383 |  for(int i=rp;i<ZA.size();i++) ans.push_back(ZA[i]);
      |               ~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18516 KB Output is correct
2 Correct 10 ms 18516 KB Output is correct
3 Correct 10 ms 18452 KB Output is correct
4 Correct 11 ms 18516 KB Output is correct
5 Correct 10 ms 18516 KB Output is correct
6 Correct 10 ms 18516 KB Output is correct
7 Correct 48 ms 25552 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18544 KB Output is correct
2 Correct 10 ms 18516 KB Output is correct
3 Correct 11 ms 18496 KB Output is correct
4 Correct 11 ms 18444 KB Output is correct
5 Correct 11 ms 18460 KB Output is correct
6 Correct 198 ms 38224 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19156 KB Output is correct
2 Correct 10 ms 18516 KB Output is correct
3 Correct 10 ms 18512 KB Output is correct
4 Correct 11 ms 18544 KB Output is correct
5 Correct 13 ms 19028 KB Output is correct
6 Correct 10 ms 18516 KB Output is correct
7 Correct 11 ms 18516 KB Output is correct
8 Correct 10 ms 18516 KB Output is correct
9 Correct 10 ms 18516 KB Output is correct
10 Correct 13 ms 18900 KB Output is correct
11 Correct 10 ms 18516 KB Output is correct
12 Correct 13 ms 19084 KB Output is correct
13 Correct 11 ms 18536 KB Output is correct
14 Correct 10 ms 18516 KB Output is correct
15 Correct 11 ms 18580 KB Output is correct
16 Correct 11 ms 18532 KB Output is correct
17 Correct 87 ms 30932 KB Output is correct
18 Correct 71 ms 28780 KB Output is correct
19 Correct 10 ms 18516 KB Output is correct
20 Correct 10 ms 18516 KB Output is correct
21 Correct 10 ms 18548 KB Output is correct
22 Correct 10 ms 18460 KB Output is correct
23 Correct 200 ms 38312 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18516 KB Output is correct
2 Correct 12 ms 18828 KB Output is correct
3 Correct 52 ms 24768 KB Output is correct
4 Correct 69 ms 28956 KB Output is correct
5 Correct 14 ms 19028 KB Output is correct
6 Correct 14 ms 19084 KB Output is correct
7 Correct 10 ms 18496 KB Output is correct
8 Correct 10 ms 18516 KB Output is correct
9 Correct 10 ms 18520 KB Output is correct
10 Correct 13 ms 19052 KB Output is correct
11 Correct 14 ms 19116 KB Output is correct
12 Correct 13 ms 19104 KB Output is correct
13 Correct 13 ms 19156 KB Output is correct
14 Correct 13 ms 19028 KB Output is correct
15 Correct 14 ms 19216 KB Output is correct
16 Correct 12 ms 18912 KB Output is correct
17 Correct 10 ms 18484 KB Output is correct
18 Correct 12 ms 18908 KB Output is correct
19 Correct 11 ms 18644 KB Output is correct
20 Correct 110 ms 26220 KB Output is correct
21 Correct 77 ms 30028 KB Output is correct
22 Correct 12 ms 19028 KB Output is correct
23 Correct 12 ms 18588 KB Output is correct
24 Correct 11 ms 18516 KB Output is correct
25 Correct 11 ms 18644 KB Output is correct
26 Correct 12 ms 19012 KB Output is correct
27 Correct 78 ms 30220 KB Output is correct
28 Correct 83 ms 31364 KB Output is correct
29 Correct 10 ms 18520 KB Output is correct
30 Correct 171 ms 37580 KB Output is correct
31 Correct 10 ms 18516 KB Output is correct
32 Correct 82 ms 31416 KB Output is correct
33 Correct 62 ms 25872 KB Output is correct
34 Correct 77 ms 29708 KB Output is correct
35 Correct 11 ms 18772 KB Output is correct
36 Correct 76 ms 30156 KB Output is correct
37 Correct 112 ms 36860 KB Output is correct
38 Correct 11 ms 18516 KB Output is correct
39 Correct 122 ms 31792 KB Output is correct
40 Correct 12 ms 18900 KB Output is correct
41 Correct 168 ms 37612 KB Output is correct
42 Correct 90 ms 32008 KB Output is correct
43 Correct 12 ms 18512 KB Output is correct
44 Correct 14 ms 19008 KB Output is correct
45 Correct 12 ms 19028 KB Output is correct
46 Correct 64 ms 27744 KB Output is correct

Subtask #5
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18516 KB Output is correct
2 Correct 10 ms 18516 KB Output is correct
3 Correct 10 ms 18452 KB Output is correct
4 Correct 11 ms 18516 KB Output is correct
5 Correct 10 ms 18516 KB Output is correct
6 Correct 10 ms 18516 KB Output is correct
7 Correct 48 ms 25552 KB Output is correct
8 Correct 10 ms 18544 KB Output is correct
9 Correct 10 ms 18516 KB Output is correct
10 Correct 11 ms 18496 KB Output is correct
11 Correct 11 ms 18444 KB Output is correct
12 Correct 11 ms 18460 KB Output is correct
13 Correct 198 ms 38224 KB Output is correct
14 Correct 13 ms 19156 KB Output is correct
15 Correct 10 ms 18516 KB Output is correct
16 Correct 10 ms 18512 KB Output is correct
17 Correct 11 ms 18544 KB Output is correct
18 Correct 13 ms 19028 KB Output is correct
19 Correct 10 ms 18516 KB Output is correct
20 Correct 11 ms 18516 KB Output is correct
21 Correct 10 ms 18516 KB Output is correct
22 Correct 10 ms 18516 KB Output is correct
23 Correct 13 ms 18900 KB Output is correct
24 Correct 10 ms 18516 KB Output is correct
25 Correct 13 ms 19084 KB Output is correct
26 Correct 11 ms 18536 KB Output is correct
27 Correct 10 ms 18516 KB Output is correct
28 Correct 11 ms 18580 KB Output is correct
29 Correct 11 ms 18532 KB Output is correct
30 Correct 87 ms 30932 KB Output is correct
31 Correct 71 ms 28780 KB Output is correct
32 Correct 10 ms 18516 KB Output is correct
33 Correct 10 ms 18516 KB Output is correct
34 Correct 10 ms 18548 KB Output is correct
35 Correct 10 ms 18460 KB Output is correct
36 Correct 200 ms 38312 KB Output is correct
37 Correct 10 ms 18516 KB Output is correct
38 Correct 10 ms 18516 KB Output is correct
39 Correct 10 ms 18516 KB Output is correct
40 Correct 11 ms 18600 KB Output is correct
41 Correct 63 ms 21972 KB Output is correct
42 Correct 14 ms 18964 KB Output is correct
43 Correct 195 ms 44168 KB Output is correct
44 Correct 193 ms 41500 KB Output is correct
45 Correct 172 ms 44360 KB Output is correct
46 Correct 9 ms 18516 KB Output is correct
47 Correct 10 ms 18460 KB Output is correct
48 Correct 10 ms 18516 KB Output is correct
49 Correct 11 ms 18964 KB Output is correct
50 Correct 276 ms 60952 KB Output is correct
51 Correct 489 ms 66192 KB Output is correct
52 Correct 477 ms 67740 KB Output is correct
53 Correct 430 ms 70020 KB Output is correct
54 Correct 500 ms 64732 KB Output is correct
55 Correct 475 ms 66948 KB Output is correct
56 Correct 459 ms 65600 KB Output is correct
57 Correct 371 ms 47936 KB Output is correct
58 Correct 271 ms 51772 KB Output is correct
59 Correct 395 ms 51424 KB Output is correct
60 Correct 190 ms 35812 KB Output is correct
61 Correct 97 ms 28756 KB Output is correct
62 Correct 22 ms 20812 KB Output is correct
63 Correct 92 ms 28020 KB Output is correct
64 Correct 72 ms 25928 KB Output is correct
65 Correct 9 ms 18516 KB Output is correct
66 Correct 11 ms 18516 KB Output is correct
67 Correct 408 ms 52908 KB Output is correct
68 Correct 178 ms 38624 KB Output is correct
69 Correct 134 ms 38084 KB Output is correct
70 Correct 13 ms 18900 KB Output is correct
71 Correct 242 ms 39980 KB Output is correct
72 Correct 10 ms 18516 KB Output is correct
73 Correct 331 ms 47564 KB Output is correct
74 Correct 289 ms 55324 KB Output is correct
75 Correct 17 ms 19468 KB Output is correct
76 Correct 111 ms 35656 KB Output is correct
77 Correct 229 ms 57824 KB Output is correct
78 Correct 192 ms 35948 KB Output is correct
79 Correct 10 ms 18516 KB Output is correct
80 Correct 404 ms 51544 KB Output is correct
81 Correct 11 ms 18900 KB Output is correct
82 Correct 99 ms 25532 KB Output is correct
83 Correct 10 ms 18644 KB Output is correct
84 Correct 10 ms 18516 KB Output is correct
85 Correct 113 ms 35092 KB Output is correct
86 Correct 11 ms 18772 KB Output is correct
87 Correct 12 ms 19028 KB Output is correct
88 Correct 14 ms 18900 KB Output is correct
89 Correct 191 ms 35972 KB Output is correct
90 Correct 94 ms 28772 KB Output is correct
91 Correct 378 ms 53716 KB Output is correct
92 Correct 11 ms 18516 KB Output is correct