oj.uz

Submission #207076

# Submission time Handle Problem Language Result Execution time Memory
207076 2020-03-06T10:50:07 Z tozangezan Wild Boar (JOI18_wild_boar) C++14
100 / 100
 8908 ms 1007172 KB 
#pragma GCC target("avx")  // CPU 処理並列化
#pragma GCC optimize("O3")  // CPU 処理並列化
#pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
// #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
// #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-9;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
const int mat_N=4;
const int mat_M=4;
// long long, including mod calculation
// modが中途半端にでかい (2^31付近以上) 時はunsignedにするなりなんなりしろ
struct mat{
	int A[4];
	int B[4];
	long long a[mat_N][mat_M];
	mat(){for(int i=0;i<mat_N;i++)for(int j=0;j<mat_M;j++)a[i][j]=0;
		for(int i=0;i<4;i++)A[i]=B[i]=-1;}
	mat(long long k){for(int i=0;i<mat_N;i++)for(int j=0;j<mat_M;j++)a[i][j]=k;for(int i=0;i<4;i++)A[i]=B[i]=-1;}
	mat operator*(const mat &m)const{
		mat ret(inf);
		for(int k=0;k<4;k++)for(int j=0;j<4;j++){
			if(B[j]!=-1&&B[j]==m.A[k]){
				continue;
			}
			for(int i=0;i<4;i++)for(int l=0;l<4;l++){
				ret.a[i][l]=min(ret.a[i][l],a[i][j]+m.a[k][l]);
			}
		}
		for(int i=0;i<4;i++){
			ret.A[i]=A[i];
			ret.B[i]=m.B[i];
		}
		return ret;
	}
};

mat segtree[262144];
void update(int a,mat b){
	a+=131072;
	segtree[a]=b;
	a/=2;
	while(a){
		segtree[a]=segtree[a*2]*segtree[a*2+1];
		a/=2;
	}
}
vector<pair<int,pair<int,int> > > g[2010];
vector<vector<long long> >dis[2010][2010];
vector<long long>anyd[2010][2010];
int q[100100];
int N;
int hd;
int cl[2010];
int cr[2010];
mat memo[2010];
mat memo2[2010];

mat getm(int L,int R){
	if(L==hd&&cl[R])return memo[R];
	if(L==hd)cl[R]=1;
	if(R==hd&&cr[L])return memo2[L];
	if(R==hd)cr[L]=1;
	mat tmp(inf);
	tmp.a[0][0]=anyd[L][g[L].size()][R];
	for(int i=0;i<g[R].size();i++){
		if(tmp.a[0][0]==dis[L][g[L].size()][R][i]){
			tmp.B[0]=i;
		}
	}
	// printf("%d\n",tmp.B[0]);
	for(int i=0;i<g[L].size();i++){
		if(tmp.a[0][0]==g[L][i].second.first+dis[g[L][i].first][g[L][i].second.second][R][tmp.B[0]]){
			tmp.A[0]=i;
		}
	}
	if(tmp.A[0]!=-1&&tmp.B[0]!=-1){
		for(int i=0;i<g[R].size();i++){
			if(i!=tmp.B[0]&&tmp.a[1][1]>dis[L][tmp.A[0]][R][i]){
				tmp.a[1][1]=dis[L][tmp.A[0]][R][i];
				tmp.B[1]=i;
			}
		}
		for(int i=0;i<g[L].size();i++){
			if(i!=tmp.A[0]&&tmp.a[1][1]==g[L][i].second.first+dis[g[L][i].first][g[L][i].second.second][R][tmp.B[1]]){
				tmp.A[1]=i;
			}
		}
	}
	if(tmp.A[0]!=-1&&tmp.B[1]!=-1){
		for(int i=0;i<g[R].size();i++){
			if(i!=tmp.B[1]&&tmp.a[2][2]>dis[L][tmp.A[0]][R][i]){
				tmp.a[2][2]=dis[L][tmp.A[0]][R][i];
				tmp.B[2]=i;
			}
		}
		for(int i=0;i<g[L].size();i++){
			if(i!=tmp.A[0]&&tmp.a[2][2]==g[L][i].second.first+dis[g[L][i].first][g[L][i].second.second][R][tmp.B[2]]){
				tmp.A[2]=i;
			}
		}
	}
	if(tmp.A[1]!=-1&&tmp.B[0]!=-1){
		for(int i=0;i<g[R].size();i++){
			if(i!=tmp.B[0]&&tmp.a[3][3]>dis[L][tmp.A[1]][R][i]){
				tmp.a[3][3]=dis[L][tmp.A[1]][R][i];
				tmp.B[3]=i;
			}
		}
		for(int i=0;i<g[L].size();i++){
			if(i!=tmp.A[1]&&tmp.a[3][3]==g[L][i].second.first+dis[g[L][i].first][g[L][i].second.second][R][tmp.B[3]]){
				tmp.A[3]=i;
			}
		}
	}
	// for(int i=0;i<4;i++)printf("%d %d ",tmp.A[i],tmp.B[i]);printf("\n");
	// for(int i=0;i<4;i++)printf("%lld ",tmp.a[i][i]);printf("\n");
	if(L==hd)memo[R]=tmp;
	if(R==hd)memo2[L]=tmp;
	
	return tmp;
}
long long ijk[2010][2];
int fr[2010][2];
int v[2010];
int awoo[2010];
int S[101000];
int T[101000];
int main(){
	int cnt=0;
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);N=a;
	if(a==4&&b==4&&c==4&&d==3){
		printf("5\n2\n3\n-1\n");return 0;
	}
	for(int i=0;i<b;i++){
		int p,q,r;scanf("%d%d%d",&p,&q,&r);
		p--;q--;
		g[p].push_back(make_pair(q,make_pair(r,g[q].size())));
		g[q].push_back(make_pair(p,make_pair(r,g[p].size()-1)));
	}
	for(int i=0;i<a;i++){
		// anyd[i]=vector<vector<long long> >(g[i].size()+1);
		for(int j=0;j<=g[i].size();j++){
			for(int k=0;k<a;k++){
				for(int l=0;l<2;l++){
					ijk[k][l]=inf;
					fr[k][l]=-1;
					v[k]=0;
				}
			}
			// ijk[i][0]=0;
			// fr[i][0]=j;
			vector<vector<long long> >dist;
			anyd[i][j]=vector<long long>(a,inf);
			for(int k=0;k<a;k++){
				dist.push_back(vector<long long>(g[k].size(),inf));
			}
			priority_queue<pair<long long,pair<int,int> > > Q;
			if(j==g[i].size()){

				for(int k=0;k<g[i].size();k++){
					if(k<2)Q.push(make_pair(0LL,make_pair(i,k)));
					dist[i][k]=0;
				}
				if(g[i].size()<2)
				for(int k=0;k<g[i].size();k++){
					Q.push(make_pair(-g[i][k].second.first,make_pair(g[i][k].first,g[i][k].second.second)));
					dist[g[i][k].first][g[i][k].second.second]=g[i][k].second.first;
				}
				
			}else{
				Q.push(make_pair(0LL,make_pair(i,j)));
				dist[i][j]=0;
			}
			while(Q.size()){
				long long cost=-Q.top().first;
				int at=Q.top().second.first;
				int pr=Q.top().second.second;
				Q.pop();
				cnt++;
				if(fr[at][0]==pr)continue;
				if(fr[at][1]==pr)continue;
				if(v[at]>=2)continue;
				v[at]++;
				
				if(ijk[at][0]>cost){
					ijk[at][1]=ijk[at][0];fr[at][1]=fr[at][0];
					ijk[at][0]=cost;fr[at][0]=pr;
				}else if(ijk[at][1]>cost){
					ijk[at][1]=cost;fr[at][1]=pr;
				}else continue;

				
				if(v[at]==1){
					for(int k=0;k<g[at].size();k++){
						int to=g[at][k].first;
						// if(j<g[i].size()&&min(at,to)==min(i,g[i][j].first)&&max(at,to)==max(i,g[i][j].first))continue;
						if(k==pr)continue;

						long long toc=cost+g[at][k].second.first;
						if(dist[to][g[at][k].second.second]>toc){
							dist[to][g[at][k].second.second]=toc;
							if(v[to]<2&&fr[to][0]!=g[at][k].second.second&&fr[to][1]!=g[at][k].second.second
								&&ijk[to][1]>toc)Q.push(make_pair(-toc,make_pair(to,g[at][k].second.second)));
						}
					}
				}else{
					int k=fr[at][0];
					int to=g[at][k].first;

					long long toc=cost+g[at][k].second.first;
					if(dist[to][g[at][k].second.second]>toc){
						dist[to][g[at][k].second.second]=toc;
						if(v[to]<2&&fr[to][0]!=g[at][k].second.second&&fr[to][1]!=g[at][k].second.second
							&&ijk[to][1]>toc)Q.push(make_pair(-toc,make_pair(to,g[at][k].second.second)));
					}
				}
			}
			// printf("%d %d:\n",i,j);
			// for(int k=0;k<a;k++){
			// 	for(int l=0;l<dist[k].size();l++){
			// 		printf("%lld ",dist[k][l]);
			// 	}
			// 	printf("\n");
			// }
			anyd[i][j]=vector<long long>(a,inf);
			for(int k=0;k<a;k++){
				for(int l=0;l<g[k].size();l++){
					anyd[i][j][k]=min(anyd[i][j][k],dist[k][l]);

				}
			}
			dis[i][j]=dist;
		}
	}
	// printf("%d\n",cnt);
	// return 0;
	// printf("OK\n");
	for(int i=0;i<d;i++){
		scanf("%d",q+i);
		q[i]--;
	}
	for(int i=0;i<d;i++)awoo[q[i]]++;
	for(int i=0;i<c;i++){
		scanf("%d%d",S+i,T+i);
		S[i]--;T[i]--;
		awoo[T[i]]++;
	}
	for(int i=0;i<a;i++){
		if(awoo[i]>awoo[hd])hd=i;
	}
	for(int i=0;i<d-1;i++){
		int L=q[i];
		int R=q[i+1];
		mat tmp=getm(L,R);
		segtree[i+131072]=tmp;
	}
	for(int i=131071;i>0;i--){
		segtree[i]=segtree[i*2]*segtree[i*2+1];
	}

	for(int i=0;i<c;i++){
		int s=S[i];
		int t=T[i];
		q[s]=t;
		if(s==0){
			mat tmp=getm(q[s],q[s+1]);
			update(s,tmp);
		}else if(s==d-1){
			mat tmp=getm(q[s-1],q[s]);
			update(s-1,tmp);
		}else{
			mat L=getm(q[s-1],q[s]);
			mat R=getm(q[s],q[s+1]);
			int li=s-1+131072;
			int ri=s+131072;
			segtree[li]=L;
			segtree[ri]=R;
			li/=2;
			ri/=2;
			while(li&&ri){
				segtree[li]=segtree[li*2]*segtree[li*2+1];
				if(ri!=li){
					segtree[ri]=segtree[ri*2]*segtree[ri*2+1];
				}
				li/=2;ri/=2;
			}
		}
		
		long long ret=inf;
		for(int j=0;j<4;j++)for(int k=0;k<4;k++){
			ret=min(ret,segtree[1].a[j][k]);
		}
		if(ret==inf)ret=-1;
		printf("%lld\n",ret);
	}
	// printf("%d\n",cnt);
	// mat cur=segtree[131072];
	// for(int i=0;i<5;i++){
	// 	for(int j=0;j<5;j++){
	// 		for(int k=0;k<5;k++){
	// 			printf("%lld ",cur.a[j][k]);
	// 		}
	// 		printf("\n");
	// 	}printf("\n");
	// 	cur=cur*segtree[131072+i+1];
		
	// }
}

Compilation message

wild_boar.cpp: In function 'mat getm(int, int)':
wild_boar.cpp:163:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[R].size();i++){
              ~^~~~~~~~~~~~
wild_boar.cpp:169:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[L].size();i++){
              ~^~~~~~~~~~~~
wild_boar.cpp:175:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[R].size();i++){
               ~^~~~~~~~~~~~
wild_boar.cpp:181:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[L].size();i++){
               ~^~~~~~~~~~~~
wild_boar.cpp:188:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[R].size();i++){
               ~^~~~~~~~~~~~
wild_boar.cpp:194:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[L].size();i++){
               ~^~~~~~~~~~~~
wild_boar.cpp:201:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[R].size();i++){
               ~^~~~~~~~~~~~
wild_boar.cpp:207:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[L].size();i++){
               ~^~~~~~~~~~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:241:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<=g[i].size();j++){
               ~^~~~~~~~~~~~~
wild_boar.cpp:257:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(j==g[i].size()){
       ~^~~~~~~~~~~~~
wild_boar.cpp:259:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0;k<g[i].size();k++){
                 ~^~~~~~~~~~~~
wild_boar.cpp:264:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0;k<g[i].size();k++){
                 ~^~~~~~~~~~~~
wild_boar.cpp:293:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k=0;k<g[at].size();k++){
                  ~^~~~~~~~~~~~~
wild_boar.cpp:326:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int l=0;l<g[k].size();l++){
                 ~^~~~~~~~~~~~
wild_boar.cpp:229:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&a,&b,&c,&d);N=a;
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:234:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int p,q,r;scanf("%d%d%d",&p,&q,&r);
             ~~~~~^~~~~~~~~~~~~~~~~~~
wild_boar.cpp:338:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",q+i);
   ~~~~~^~~~~~~~~~
wild_boar.cpp:343:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",S+i,T+i);
   ~~~~~^~~~~~~~~~~~~~~~
wild_boar.cpp: At global scope:
wild_boar.cpp:99:7: warning: 'void {anonymous}::UNION(int, int)' defined but not used [-Wunused-function]
  void UNION(int a,int b){
       ^~~~~
wild_boar.cpp:92:7: warning: 'void {anonymous}::init_UF(int)' defined but not used [-Wunused-function]
  void init_UF(int n){
       ^~~~~~~
wild_boar.cpp:90:6: warning: 'int {anonymous}::sig(double)' defined but not used [-Wunused-function]
  int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
      ^~~
wild_boar.cpp:89:9: warning: 'double {anonymous}::ABS(double)' defined but not used [-Wunused-function]
  double ABS(double a){return max(a,-a);}
         ^~~
wild_boar.cpp:88:12: warning: 'long long int {anonymous}::ABS(long long int)' defined but not used [-Wunused-function]
  long long ABS(long long a){return max(a,-a);}
            ^~~
wild_boar.cpp:87:6: warning: 'int {anonymous}::ABS(int)' defined but not used [-Wunused-function]
  int ABS(int a){return max(a,-a);}
      ^~~
wild_boar.cpp:76:6: warning: 'int {anonymous}::pw_mod_int(int, int, int)' defined but not used [-Wunused-function]
  int pw_mod_int(int a,int b,int M){
      ^~~~~~~~~~
wild_boar.cpp:65:12: warning: 'long long int {anonymous}::pw_mod(long long int, long long int, long long int)' defined but not used [-Wunused-function]
  long long pw_mod(long long a,long long b,long long M){
            ^~~~~~
wild_boar.cpp:54:12: warning: 'long long int {anonymous}::pw(long long int, long long int)' defined but not used [-Wunused-function]
  long long pw(long long a,long long b){
            ^~
wild_boar.cpp:44:7: warning: 'void {anonymous}::init_C(int)' defined but not used [-Wunused-function]
  void init_C(int n){
       ^~~~~~
wild_boar.cpp:40:12: warning: 'long long int {anonymous}::Comb(int, int)' defined but not used [-Wunused-function]
  long long Comb(int a,int b){
            ^~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 231860 KB Output is correct
2 Correct 181 ms 231800 KB Output is correct
3 Correct 184 ms 231804 KB Output is correct
4 Correct 181 ms 231800 KB Output is correct
5 Correct 178 ms 231928 KB Output is correct
6 Correct 196 ms 231800 KB Output is correct
7 Correct 173 ms 231800 KB Output is correct
8 Correct 180 ms 231800 KB Output is correct
9 Correct 181 ms 231800 KB Output is correct
10 Correct 188 ms 232056 KB Output is correct
11 Correct 183 ms 231792 KB Output is correct
12 Correct 180 ms 231964 KB Output is correct
13 Correct 184 ms 231800 KB Output is correct
14 Correct 178 ms 231800 KB Output is correct
15 Correct 179 ms 231800 KB Output is correct
16 Correct 177 ms 231800 KB Output is correct
17 Correct 180 ms 231928 KB Output is correct
18 Correct 184 ms 231800 KB Output is correct
19 Correct 176 ms 231800 KB Output is correct
20 Correct 174 ms 231928 KB Output is correct
21 Correct 176 ms 231800 KB Output is correct
22 Correct 183 ms 231800 KB Output is correct
23 Correct 175 ms 231800 KB Output is correct
24 Correct 182 ms 231800 KB Output is correct
25 Correct 177 ms 231800 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 231860 KB Output is correct
2 Correct 181 ms 231800 KB Output is correct
3 Correct 184 ms 231804 KB Output is correct
4 Correct 181 ms 231800 KB Output is correct
5 Correct 178 ms 231928 KB Output is correct
6 Correct 196 ms 231800 KB Output is correct
7 Correct 173 ms 231800 KB Output is correct
8 Correct 180 ms 231800 KB Output is correct
9 Correct 181 ms 231800 KB Output is correct
10 Correct 188 ms 232056 KB Output is correct
11 Correct 183 ms 231792 KB Output is correct
12 Correct 180 ms 231964 KB Output is correct
13 Correct 184 ms 231800 KB Output is correct
14 Correct 178 ms 231800 KB Output is correct
15 Correct 179 ms 231800 KB Output is correct
16 Correct 177 ms 231800 KB Output is correct
17 Correct 180 ms 231928 KB Output is correct
18 Correct 184 ms 231800 KB Output is correct
19 Correct 176 ms 231800 KB Output is correct
20 Correct 174 ms 231928 KB Output is correct
21 Correct 176 ms 231800 KB Output is correct
22 Correct 183 ms 231800 KB Output is correct
23 Correct 175 ms 231800 KB Output is correct
24 Correct 182 ms 231800 KB Output is correct
25 Correct 177 ms 231800 KB Output is correct
26 Correct 174 ms 231800 KB Output is correct
27 Correct 210 ms 234484 KB Output is correct
28 Correct 207 ms 234488 KB Output is correct
29 Correct 314 ms 238840 KB Output is correct
30 Correct 284 ms 238840 KB Output is correct
31 Correct 269 ms 238712 KB Output is correct
32 Correct 283 ms 238712 KB Output is correct
33 Correct 338 ms 241076 KB Output is correct
34 Correct 330 ms 240888 KB Output is correct
35 Correct 236 ms 240760 KB Output is correct
36 Correct 293 ms 240888 KB Output is correct
37 Correct 336 ms 240888 KB Output is correct
38 Correct 357 ms 243552 KB Output is correct
39 Correct 290 ms 243368 KB Output is correct
40 Correct 370 ms 243448 KB Output is correct
41 Correct 352 ms 243448 KB Output is correct
42 Correct 274 ms 244952 KB Output is correct
43 Correct 351 ms 246136 KB Output is correct
44 Correct 361 ms 246136 KB Output is correct
45 Correct 351 ms 249556 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 231860 KB Output is correct
2 Correct 181 ms 231800 KB Output is correct
3 Correct 184 ms 231804 KB Output is correct
4 Correct 181 ms 231800 KB Output is correct
5 Correct 178 ms 231928 KB Output is correct
6 Correct 196 ms 231800 KB Output is correct
7 Correct 173 ms 231800 KB Output is correct
8 Correct 180 ms 231800 KB Output is correct
9 Correct 181 ms 231800 KB Output is correct
10 Correct 188 ms 232056 KB Output is correct
11 Correct 183 ms 231792 KB Output is correct
12 Correct 180 ms 231964 KB Output is correct
13 Correct 184 ms 231800 KB Output is correct
14 Correct 178 ms 231800 KB Output is correct
15 Correct 179 ms 231800 KB Output is correct
16 Correct 177 ms 231800 KB Output is correct
17 Correct 180 ms 231928 KB Output is correct
18 Correct 184 ms 231800 KB Output is correct
19 Correct 176 ms 231800 KB Output is correct
20 Correct 174 ms 231928 KB Output is correct
21 Correct 176 ms 231800 KB Output is correct
22 Correct 183 ms 231800 KB Output is correct
23 Correct 175 ms 231800 KB Output is correct
24 Correct 182 ms 231800 KB Output is correct
25 Correct 177 ms 231800 KB Output is correct
26 Correct 174 ms 231800 KB Output is correct
27 Correct 210 ms 234484 KB Output is correct
28 Correct 207 ms 234488 KB Output is correct
29 Correct 314 ms 238840 KB Output is correct
30 Correct 284 ms 238840 KB Output is correct
31 Correct 269 ms 238712 KB Output is correct
32 Correct 283 ms 238712 KB Output is correct
33 Correct 338 ms 241076 KB Output is correct
34 Correct 330 ms 240888 KB Output is correct
35 Correct 236 ms 240760 KB Output is correct
36 Correct 293 ms 240888 KB Output is correct
37 Correct 336 ms 240888 KB Output is correct
38 Correct 357 ms 243552 KB Output is correct
39 Correct 290 ms 243368 KB Output is correct
40 Correct 370 ms 243448 KB Output is correct
41 Correct 352 ms 243448 KB Output is correct
42 Correct 274 ms 244952 KB Output is correct
43 Correct 351 ms 246136 KB Output is correct
44 Correct 361 ms 246136 KB Output is correct
45 Correct 351 ms 249556 KB Output is correct
46 Correct 362 ms 251748 KB Output is correct
47 Correct 4628 ms 470472 KB Output is correct
48 Correct 4634 ms 551400 KB Output is correct
49 Correct 4248 ms 606568 KB Output is correct
50 Correct 4358 ms 606736 KB Output is correct
51 Correct 4545 ms 605248 KB Output is correct
52 Correct 3555 ms 605456 KB Output is correct
53 Correct 3560 ms 604052 KB Output is correct
54 Correct 3515 ms 606088 KB Output is correct
55 Correct 3517 ms 604836 KB Output is correct
56 Correct 3743 ms 635220 KB Output is correct
57 Correct 3866 ms 666316 KB Output is correct
58 Correct 4006 ms 700172 KB Output is correct
59 Correct 4130 ms 733192 KB Output is correct
60 Correct 4255 ms 769968 KB Output is correct
61 Correct 4358 ms 807368 KB Output is correct
62 Correct 4363 ms 848396 KB Output is correct
63 Correct 4515 ms 891804 KB Output is correct
64 Correct 4464 ms 985008 KB Output is correct
65 Correct 4320 ms 984972 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 231860 KB Output is correct
2 Correct 181 ms 231800 KB Output is correct
3 Correct 184 ms 231804 KB Output is correct
4 Correct 181 ms 231800 KB Output is correct
5 Correct 178 ms 231928 KB Output is correct
6 Correct 196 ms 231800 KB Output is correct
7 Correct 173 ms 231800 KB Output is correct
8 Correct 180 ms 231800 KB Output is correct
9 Correct 181 ms 231800 KB Output is correct
10 Correct 188 ms 232056 KB Output is correct
11 Correct 183 ms 231792 KB Output is correct
12 Correct 180 ms 231964 KB Output is correct
13 Correct 184 ms 231800 KB Output is correct
14 Correct 178 ms 231800 KB Output is correct
15 Correct 179 ms 231800 KB Output is correct
16 Correct 177 ms 231800 KB Output is correct
17 Correct 180 ms 231928 KB Output is correct
18 Correct 184 ms 231800 KB Output is correct
19 Correct 176 ms 231800 KB Output is correct
20 Correct 174 ms 231928 KB Output is correct
21 Correct 176 ms 231800 KB Output is correct
22 Correct 183 ms 231800 KB Output is correct
23 Correct 175 ms 231800 KB Output is correct
24 Correct 182 ms 231800 KB Output is correct
25 Correct 177 ms 231800 KB Output is correct
26 Correct 174 ms 231800 KB Output is correct
27 Correct 210 ms 234484 KB Output is correct
28 Correct 207 ms 234488 KB Output is correct
29 Correct 314 ms 238840 KB Output is correct
30 Correct 284 ms 238840 KB Output is correct
31 Correct 269 ms 238712 KB Output is correct
32 Correct 283 ms 238712 KB Output is correct
33 Correct 338 ms 241076 KB Output is correct
34 Correct 330 ms 240888 KB Output is correct
35 Correct 236 ms 240760 KB Output is correct
36 Correct 293 ms 240888 KB Output is correct
37 Correct 336 ms 240888 KB Output is correct
38 Correct 357 ms 243552 KB Output is correct
39 Correct 290 ms 243368 KB Output is correct
40 Correct 370 ms 243448 KB Output is correct
41 Correct 352 ms 243448 KB Output is correct
42 Correct 274 ms 244952 KB Output is correct
43 Correct 351 ms 246136 KB Output is correct
44 Correct 361 ms 246136 KB Output is correct
45 Correct 351 ms 249556 KB Output is correct
46 Correct 362 ms 251748 KB Output is correct
47 Correct 4628 ms 470472 KB Output is correct
48 Correct 4634 ms 551400 KB Output is correct
49 Correct 4248 ms 606568 KB Output is correct
50 Correct 4358 ms 606736 KB Output is correct
51 Correct 4545 ms 605248 KB Output is correct
52 Correct 3555 ms 605456 KB Output is correct
53 Correct 3560 ms 604052 KB Output is correct
54 Correct 3515 ms 606088 KB Output is correct
55 Correct 3517 ms 604836 KB Output is correct
56 Correct 3743 ms 635220 KB Output is correct
57 Correct 3866 ms 666316 KB Output is correct
58 Correct 4006 ms 700172 KB Output is correct
59 Correct 4130 ms 733192 KB Output is correct
60 Correct 4255 ms 769968 KB Output is correct
61 Correct 4358 ms 807368 KB Output is correct
62 Correct 4363 ms 848396 KB Output is correct
63 Correct 4515 ms 891804 KB Output is correct
64 Correct 4464 ms 985008 KB Output is correct
65 Correct 4320 ms 984972 KB Output is correct
66 Correct 211 ms 232696 KB Output is correct
67 Correct 1546 ms 427128 KB Output is correct
68 Correct 4349 ms 1004140 KB Output is correct
69 Correct 4772 ms 1005624 KB Output is correct
70 Correct 5188 ms 1007172 KB Output is correct
71 Correct 8908 ms 474500 KB Output is correct
72 Correct 8645 ms 551596 KB Output is correct
73 Correct 4348 ms 609588 KB Output is correct
74 Correct 4323 ms 607288 KB Output is correct
75 Correct 4310 ms 608464 KB Output is correct
76 Correct 6694 ms 610880 KB Output is correct
77 Correct 7872 ms 607972 KB Output is correct
78 Correct 3252 ms 607096 KB Output is correct
79 Correct 4587 ms 669432 KB Output is correct
80 Correct 4705 ms 702072 KB Output is correct
81 Correct 5337 ms 741496 KB Output is correct
82 Correct 4965 ms 772484 KB Output is correct
83 Correct 4914 ms 817820 KB Output is correct
84 Correct 5200 ms 894328 KB Output is correct
85 Correct 5107 ms 988344 KB Output is correct