답안 #854229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
854229	2023-09-26T11:59:55 Z	maroonrk	수천개의 섬 (IOI22_islands)	C++17	100 / 100	294 ms	86020 KB

islands

#include "islands.h"
#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
//#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

pi readpi(int off=0){
	int a,b;cin>>a>>b;
	return pi(a+off,b+off);
}

template<class t>
void print_single(t x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

template<class t,class u>
void print_single(const pair<t,u>&p,int suc=1){
	print_single(p.a,2);
	print_single(p.b,suc);
}

template<class T>
void print_single(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print_single(v[i],i==int(v.size())-1?suc:2);
}

template<class T>
void print_offset(const vector<T>&v,ll off,int suc=1){
	rep(i,v.size())
		print_single(v[i]+off,i==int(v.size())-1?suc:2);
}

template<class T,size_t N>
void print_single(const array<T,N>&v,int suc=1){
	rep(i,N)
		print_single(v[i],i==int(N)-1?suc:2);
}

template<class T>
void print(const T&t){
	print_single(t);
}

template<class T,class ...Args>
void print(const T&t,const Args&...args){
	print_single(t,2);
	print(args...);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

void YES(bool ex=true){
	cout<<"YES\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void NO(bool ex=true){
	cout<<"NO\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void Yes(bool ex=true){
	cout<<"Yes\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void No(bool ex=true){
	cout<<"No\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
//#define CAPITAL
/*
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<"\n";
	#else
	cout<<"Yes"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<"\n";
	#else
	cout<<"No"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}*/
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<"\n";
	#else
	cout<<"Possible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<"\n";
	#else
	cout<<"Impossible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int topbit(ull t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int botbit(ull a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
int popcount(ull t){
	return __builtin_popcountll(t);
}
int bitparity(ll t){
	return __builtin_parityll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
ll mask(int i){
	return (ll(1)<<i)-1;
}
ull umask(int i){
	return (ull(1)<<i)-1;
}
ll minp2(ll n){
	if(n<=1)return 1;
	else return ll(1)<<(topbit(n-1)+1);
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	//#ifdef LOCAL
	static mt19937_64 gen;
	/*#else
	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
	#endif*/
	return uniform_int_distribution<ll>(l, r)(gen);
}

ll rand_int(ll k){ //[0,k)
	return rand_int(0,k-1);
}

template<class t>
void myshuffle(vc<t>&a){
	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}

template<class t>
int lwb(const vc<t>&v,const t&a){
	return lower_bound(all(v),a)-v.bg;
}
template<class t>
bool bis(const vc<t>&v,const t&a){
	return binary_search(all(v),a);
}

vvc<int> readGraph(int n,int m){
	vvc<int> g(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		//sc.read(a,b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	return g;
}

vvc<int> readTree(int n){
	return readGraph(n,n-1);
}

template<class t>
vc<t> presum(const vc<t>&a){
	vc<t> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
vc<ll> presum(const vi&a){
	vc<ll> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
//BIT で数列を管理するときに使う (CF850C)
template<class t>
vc<t> predif(vc<t> a){
	gnr(i,1,si(a))a[i]-=a[i-1];
	return a;
}
template<class t>
vvc<ll> imos(const vvc<t>&a){
	int n=si(a),m=si(a[0]);
	vvc<ll> b(n+1,vc<ll>(m+1));
	rep(i,n)rep(j,m)
		b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j];
	return b;
}

//verify してないや
void transvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void transvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[j][i]=a[i][j];
	}
	a.swap(b);
	transvvc(n,m,args...);
}
//CF854E
void rotvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[m-1-j][i]=a[i][j];
	}
	a.swap(b);
	rotvvc(n,m,args...);
}

//ソートして i 番目が idx[i]
//CF850C
template<class t>
vi sortidx(const vc<t>&a){
	int n=si(a);
	vi idx(n);iota(all(idx),0);
	sort(all(idx),[&](int i,int j){return a[i]<a[j];});
	return idx;
}
//vs[i]=a[idx[i]]
//例えば sortidx で得た idx を使えば単にソート列になって返ってくる
//CF850C
template<class t>
vc<t> a_idx(const vc<t>&a,const vi&idx){
	int n=si(a);
	assert(si(idx)==n);
	vc<t> vs(n);
	rep(i,n)vs[i]=a[idx[i]];
	return vs;
}
//CF850C
vi invperm(const vi&p){
	int n=si(p);
	vi q(n);
	rep(i,n)q[p[i]]=i;
	return q;
}

template<class t,class s=t>
s SUM(const vc<t>&a){
	return accumulate(all(a),s(0));
}

template<class t>
t MAX(const vc<t>&a){
	return *max_element(all(a));
}

template<class t>
pair<t,int> MAXi(const vc<t>&a){
	auto itr=max_element(all(a));
	return mp(*itr,itr-a.bg);
}

template<class t>
t MIN(const vc<t>&a){
	return *min_element(all(a));
}

template<class t>
pair<t,int> MINi(const vc<t>&a){
	auto itr=min_element(all(a));
	return mp(*itr,itr-a.bg);
}

vi vid(int n){
	vi res(n);iota(all(res),0);
	return res;
}

template<class S>
void soin(S&s){
	sort(all(s));
}

template<class S>
S soout(S s){
	soin(s);
	return s;
}

template<class S>
void rein(S&s){
	reverse(all(s));
}

template<class S>
S reout(S s){
	rein(s);
	return s;
}

template<class t,class u>
pair<t,u>&operator+=(pair<t,u>&a,pair<t,u> b){
	a.a+=b.a;a.b+=b.b;return a;}
template<class t,class u>
pair<t,u>&operator-=(pair<t,u>&a,pair<t,u> b){
	a.a-=b.a;a.b-=b.b;return a;}
template<class t,class u>
pair<t,u> operator+(pair<t,u> a,pair<t,u> b){return mp(a.a+b.a,a.b+b.b);}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a,pair<t,u> b){return mp(a.a-b.a,a.b-b.b);}

template<class t>
t gpp(vc<t>&vs){
	assert(si(vs));
	t res=move(vs.back());
	vs.pop_back();
	return res;
}

template<class t>
void pb(vc<t>&a,const vc<t>&b){
	a.insert(a.ed,all(b));
}

template<class t>
vc<t> cat(vc<t> a,const vc<t>&b){
	pb(a,b);
	return a;
}

template<class t,class u>
vc<t>& operator+=(vc<t>&a,u x){
	for(auto&v:a)v+=x;
	return a;
}

template<class t,class u>
vc<t> operator+(vc<t> a,u x){
	return a+=x;
}

template<class t,class u>
vc<t>& operator-=(vc<t>&a,u x){
	for(auto&v:a)v-=x;
	return a;
}

template<class t,class u>
vc<t>& operator-(vc<t> a,u x){
	return a-=x;
}

//CCPC Finals 2021 H
//Multiuni2023-3 E
struct dominator_tree{
	int n;
	vvc<int> g,rG,bct;
	vi idom,semi,us,id,rId,par,mn,anc;
	dominator_tree(int nn):n(nn),
		g(n),rG(n),bct(n),
		idom(n,-1),semi(n),us(n),id(n,-1),rId(n),par(n,-1),mn(n),anc(n,-1){
		iota(all(semi),0);
		iota(all(mn),0);
	}
	void ae(int a,int b){
		if(a==b)return;
		g[a].pb(b);
		rG[b].pb(a);
	}
	int find(int v){
		if(anc[v]==-1)
			return v;
		int a=find(anc[v]);
		if(id[semi[mn[anc[v]]]]<id[semi[mn[v]]])
			mn[v]=mn[anc[v]];
		return anc[v]=a;
	}
	void link(int c,int p){
		anc[c]=p;
	}
	void dfs(int v,int p,int& i){
		if(id[v]!=-1)
			return;
		id[v]=i;
		rId[i++]=v;
		par[v]=p;
		for(int c:g[v])
			dfs(c,v,i);
	}
	//return idom or -1 if unreachable from the root
	vi calc(int root){
		int sz=0;
		dfs(root,-1,sz);
		for(int i=sz-1;i>0;i--){
			int w=rId[i];
			for(int v:rG[w])if(id[v]!=-1){
				find(v);
				if(id[semi[mn[v]]]<id[semi[w]])
					semi[w]=semi[mn[v]];
			}
			bct[semi[w]].pb(w);
			for(int v:bct[par[w]]){
				find(v);
				us[v]=mn[v];
			}
			bct[par[w]].clear();
			link(w,par[w]);
		}
		rng(i,1,sz){
			int w=rId[i];
			if(semi[w]==semi[us[w]])
				idom[w]=semi[w];
			else
				idom[w]=idom[us[w]];
		}
		return idom;
	}
};

//dep,par は not verified
//yukicoder no.1024
//https://www.codechef.com/LTIME110A/problems/TREEQUER
//IOI2022 Islands
template<class E>
struct treedfs{
	const vvc<E>&g;
	const int n;
	int cnt;
	vi par,dep,in,out,ni;
	void dfs(int v,int p,int d){
		par[v]=p;
		dep[v]=d;
		in[v]=cnt++;
		for(auto e:g[v])if(e!=p)
			dfs(e,v,d+1);
		out[v]=cnt;
	}
	treedfs(const vvc<E>&gg,int r):g(gg),n(si(g)),cnt(0),par(n),dep(n,-1),in(n,-1),out(n,-1){
		dfs(r,-1,0);
		//not necessarily connected
		ni.resize(cnt);
		rep(i,n)if(in[i]!=-1)ni[in[i]]=i;
	}
	bool asde(int a,int b){
		return in[a]<=in[b]&&out[b]<=out[a];
	}
};

//CF869B
//複数始点
template<class E>
tuple<vi,vi,vc<E>> bfs(const vvc<E>&g,vi rs){
	int n=si(g);
	vi dist(n,-1),from(n,-1);
	vc<E> use(n);
	vi q(n);
	int b=0,e=0;
	auto reach=[&](int v,int d,int f,E u){
		if(dist[v]!=-1)return;
		dist[v]=d;
		from[v]=f;
		use[v]=u;
		q[e++]=v;
	};
	for(auto r:rs)reach(r,0,-1,E());
	while(b<e){
		int v=q[b++];
		for(auto to:g[v])
			reach(to,dist[v]+1,v,to);
	}
	return mt(move(dist),move(from),move(use));
}

bool dbg=false;

struct E{
	int to,id;
	operator int()const{return to;}
};

std::variant<bool, std::vector<int>> find_journey(
	int n, int m, std::vector<int> U, std::vector<int> V) {
	vvc<E> g(n);
	rep(i,m)g[U[i]].pb({V[i],i});
	
	int twocyc[2]{-1,-1};
	
	vi pv(n,-1),pe(n,-1),dep(n,-1),ord;
	{
		vi vis(n,0),bw(n,-1);
		vi ls;
		auto dfs=[&](auto self,int v,int p,int e,int d)->void{
			assert(vis[v]==0);
			assert(dep[v]==-1);
			vis[v]=1;
			ls.pb(v);
			pv[v]=p;
			pe[v]=e;
			dep[v]=d;
			ord.pb(v);
			int x[2]{-1,-1};
			for(auto [to,id]:g[v]){
				if(dep[to]==-1){
					self(self,to,v,id,d+1);
					int y=bw[to];
					rep(k,2)if(x[k]<y)swap(x[k],y);
				}else if(vis[to]==1){
					bw[ls[dep[to]+1]]=id;
				}else{
					//do nothing
				}
			}
			ls.pop_back();
			rep(k,2)chmax(bw[v],x[k]);
			if(x[0]!=-1&&x[1]!=-1){
				rep(k,2)twocyc[k]=x[k];
			}
			vis[v]=2;
		};
		dfs(dfs,0,-1,-1,0);
	}
	
	auto getcycle=[&](int c){
		vi res{c};
		for(int i=U[c];i!=V[c];i=pv[i]){
			res.pb(pe[i]);
		}
		return reout(res);
	};
	
	vc<bool> avail(m,true);
	auto getwalk=[&](vi cyc){
		vi pos(n,-1);
		rep(i,si(cyc))pos[U[cyc[i]]]=i;
		vc<bool> vis(n);
		
		vi cur;
		auto dfs=[&](auto self,int v)->bool{
			assert(!vis[v]);
			vis[v]=true;
			int step=rand_int(0,si(g[v]));
			myshuffle(g[v]);
			rep(_,si(g[v])+1){
				if(_==step){
					if(pos[v]!=-1){
						rep(i,si(cyc))cur.pb(cyc[(pos[v]+i)%si(cyc)]);
						return true;
					}
				}
				if(_<si(g[v])){
					auto [to,id]=g[v][_];
					if(avail[id]){
						if(!vis[to]){
							cur.pb(id);
							if(self(self,to)){
								cur.pb(id);
								return true;
							}else{
								cur.pop_back();
							}
						}
					}
				}
			}
			return false;
		};
		bool res=dfs(dfs,0);
		assert(res);
		return cur;
	};
	
	auto mg=[&](vi a,vi b){
		assert(a!=b);
		for(auto v:b){
			if(si(a)&&a.back()==v)a.pop_back();
			else a.pb(v);
		}
		return a;
	};
	
	if(twocyc[0]!=-1&&twocyc[1]!=-1){
		vi cyc[2];
		rep(k,2)cyc[k]=getcycle(twocyc[k]);
		
		rep(k,2)for(auto i:cyc[k])avail[i]=false;
		vi x=getwalk(cyc[0]);
		vi y=getwalk(cyc[1]);
		
		return mg(mg(x,y),mg(reout(x),reout(y)));
	}
	
	dominator_tree dt(n*2);
	vi bef(n,-1);
	vc<pi> arc;
	int s=n;
	{
		vi vis(n);
		vi ls;
		auto dfs=[&](auto self,int v,int d)->void{
			assert(!vis[v]);
			vis[v]=1;
			for(auto [to,id]:g[v]){
				if(!vis[to]){
					int e=s++;
					dt.ae(v,e);
					dt.ae(e,to);
					ls.pb(e);
					bef[to]=e;
					self(self,to,d+1);
					ls.pop_back();
				}else{
					dt.ae(v,to);
					if(vis[to]==1){
						arc.eb(id,ls[dep[to]]);
					}
				}
			}
			vis[v]=2;
		};
		dfs(dfs,0,0);
	}
	
	vi idom=dt.calc(0);
	vvc<int> t(s);
	rep(i,s)if(idom[i]!=-1)t[idom[i]].pb(i);
	
	treedfs<int> w(t,0);
	
	int singlecyc=-1;
	
	vc<bool> uni(n,true);
	for(auto i:ord)if(i){
		uni[i]=uni[pv[i]];
		if(idom[i]!=bef[i])uni[i]=false;
	}
	
	for(auto [i,pre]:arc){
		if(!w.asde(pre,U[i]))singlecyc=i;
		if(!uni[V[i]])singlecyc=i;
	}
	
	if(singlecyc==-1){
		return false;
	}
	
	vi cyc=getcycle(singlecyc);
	for(auto i:cyc)avail[i]=false;
	vi x=getwalk(cyc);
	vi y;
	do{y=getwalk(cyc);}while(x==y);
	
	return mg(x,reout(y));
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	41 ms	8504 KB	Output is correct

Subtask #2

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	50 ms	7108 KB	Output is correct

Subtask #3

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	2 ms	1112 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	600 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	2 ms	1112 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	21 ms	3420 KB	Output is correct
18	Correct	17 ms	2908 KB	Output is correct
19	Correct	0 ms	600 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	37 ms	7120 KB	Output is correct

Subtask #4

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	30 ms	6716 KB	Output is correct
4	Correct	34 ms	7116 KB	Output is correct
5	Correct	2 ms	1116 KB	Output is correct
6	Correct	2 ms	1116 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	2 ms	1116 KB	Output is correct
11	Correct	2 ms	1116 KB	Output is correct
12	Correct	2 ms	1116 KB	Output is correct
13	Correct	2 ms	1188 KB	Output is correct
14	Correct	2 ms	1116 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct
16	Correct	2 ms	1112 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	1 ms	568 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	31 ms	7632 KB	Output is correct
21	Correct	32 ms	6480 KB	Output is correct
22	Correct	1 ms	1112 KB	Output is correct
23	Correct	1 ms	604 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	1 ms	344 KB	Output is correct
26	Correct	2 ms	1116 KB	Output is correct
27	Correct	33 ms	6048 KB	Output is correct
28	Correct	33 ms	8140 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	34 ms	8424 KB	Output is correct
31	Correct	1 ms	348 KB	Output is correct
32	Correct	35 ms	7624 KB	Output is correct
33	Correct	34 ms	7252 KB	Output is correct
34	Correct	21 ms	3416 KB	Output is correct
35	Correct	1 ms	860 KB	Output is correct
36	Correct	28 ms	6616 KB	Output is correct
37	Correct	34 ms	8076 KB	Output is correct
38	Correct	1 ms	800 KB	Output is correct
39	Correct	26 ms	6516 KB	Output is correct
40	Correct	2 ms	1116 KB	Output is correct
41	Correct	35 ms	8528 KB	Output is correct
42	Correct	46 ms	5972 KB	Output is correct
43	Correct	1 ms	344 KB	Output is correct
44	Correct	2 ms	856 KB	Output is correct
45	Correct	2 ms	1116 KB	Output is correct
46	Correct	17 ms	2868 KB	Output is correct

Subtask #5

45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	41 ms	8504 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	50 ms	7108 KB	Output is correct
14	Correct	1 ms	600 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	2 ms	1112 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	600 KB	Output is correct
21	Correct	0 ms	344 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	2 ms	1112 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	1 ms	604 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	21 ms	3420 KB	Output is correct
31	Correct	17 ms	2908 KB	Output is correct
32	Correct	0 ms	600 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Correct	37 ms	7120 KB	Output is correct
37	Correct	1 ms	348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	0 ms	348 KB	Output is correct
40	Correct	1 ms	344 KB	Output is correct
41	Correct	14 ms	3584 KB	Output is correct
42	Correct	2 ms	860 KB	Output is correct
43	Correct	81 ms	38580 KB	Output is correct
44	Correct	92 ms	35164 KB	Output is correct
45	Correct	102 ms	39080 KB	Output is correct
46	Correct	0 ms	348 KB	Output is correct
47	Correct	0 ms	348 KB	Output is correct
48	Correct	0 ms	348 KB	Output is correct
49	Correct	2 ms	1116 KB	Output is correct
50	Correct	294 ms	86020 KB	Output is correct
51	Correct	217 ms	72112 KB	Output is correct
52	Correct	197 ms	74184 KB	Output is correct
53	Correct	291 ms	78856 KB	Output is correct
54	Correct	202 ms	70600 KB	Output is correct
55	Correct	204 ms	73020 KB	Output is correct
56	Correct	235 ms	72660 KB	Output is correct
57	Correct	42 ms	9668 KB	Output is correct
58	Correct	80 ms	21604 KB	Output is correct
59	Correct	198 ms	58984 KB	Output is correct
60	Correct	75 ms	41536 KB	Output is correct
61	Correct	53 ms	35732 KB	Output is correct
62	Correct	12 ms	14836 KB	Output is correct
63	Correct	51 ms	35440 KB	Output is correct
64	Correct	19 ms	3544 KB	Output is correct
65	Correct	1 ms	348 KB	Output is correct
66	Correct	1 ms	348 KB	Output is correct
67	Correct	57 ms	16628 KB	Output is correct
68	Correct	34 ms	8656 KB	Output is correct
69	Correct	93 ms	50868 KB	Output is correct
70	Correct	2 ms	1116 KB	Output is correct
71	Correct	101 ms	30780 KB	Output is correct
72	Correct	0 ms	348 KB	Output is correct
73	Correct	144 ms	42936 KB	Output is correct
74	Correct	229 ms	78496 KB	Output is correct
75	Correct	3 ms	860 KB	Output is correct
76	Correct	96 ms	36936 KB	Output is correct
77	Correct	180 ms	81452 KB	Output is correct
78	Correct	75 ms	41540 KB	Output is correct
79	Correct	0 ms	344 KB	Output is correct
80	Correct	211 ms	65072 KB	Output is correct
81	Correct	1 ms	604 KB	Output is correct
82	Correct	29 ms	7364 KB	Output is correct
83	Correct	1 ms	344 KB	Output is correct
84	Correct	0 ms	348 KB	Output is correct
85	Correct	29 ms	11264 KB	Output is correct
86	Correct	1 ms	604 KB	Output is correct
87	Correct	11 ms	23140 KB	Output is correct
88	Correct	2 ms	1372 KB	Output is correct
89	Correct	76 ms	41464 KB	Output is correct
90	Correct	52 ms	35904 KB	Output is correct
91	Correct	203 ms	66824 KB	Output is correct
92	Correct	1 ms	344 KB	Output is correct