oj.uz

Submission #227192

# Submission time Handle Problem Language Result Execution time Memory
227192 2020-04-26T12:35:49 Z kig9981 Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 16812 KB 
#include "wombats.h"
#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 B=1000;
int N, M, H[5000][200], V[5000][200], C[6][200][200], D[200], D2[200];

void dijk(int b)
{
	priority_queue<pair<int,int>> Q;
	for(int r=0;r<M;r++) {
		for(int i=0;i<B && b*B+i<N;i++) {
			if(i) {
				for(int j=0;j<M;j++) {
					D[j]+=V[b*B+i-1][j];
					Q.emplace(-D[j],j);
				}
			}
			else {
				for(int j=0;j<M;j++) {
					if(r==j) Q.emplace(D[j]=0,j);
					else D[j]=0x7fffffff;
				}
			}
			while(!Q.empty()) {
				auto[t,c]=Q.top();
				Q.pop();
				if(-t!=D[c]) continue;
				if(c && D[c-1]>D[c]+H[b*B+i][c-1]) {
					D[c-1]=D[c]+H[b*B+i][c-1];
					Q.emplace(-D[c-1],c-1);
				}
				if(c+1<M && D[c+1]>D[c]+H[b*B+i][c]) {
					D[c+1]=D[c]+H[b*B+i][c];
					Q.emplace(-D[c+1],c+1);
				}
			}
		}
		for(int j=0;j<M;j++) C[b][r][j]=D[j];
	}
}

void init(int R, int C, int (*H)[200], int (*V)[200])
{
	N=R; M=C;
	for(int i=0;i<N;i++) for(int j=0;j<M-1;j++) ::H[i][j]=H[i][j];
	for(int i=0;i<N-1;i++) for(int j=0;j<M;j++) ::V[i][j]=V[i][j];
	for(int i=0;i*B<N;i++) dijk(i);
}

void changeH(int P, int Q, int W)
{
    H[P][Q]=W;
	dijk(P/B);
}

void changeV(int P, int Q, int W)
{
    V[P][Q]=W;
	if(P/B==(P+1)/B) dijk(P/B);
}

void dnc(int b, int s1, int e1, int s2, int e2)
{
	int m2=(s2+e2)>>1, m=s1;
	if(s2>e2) return;
	for(int i=s1+1;i<=e1;i++) if(D[i]+C[b][i][m2]<D[m]+C[b][m][m2]) m=i;
	D2[m2]=D[m]+C[b][m][m2];
	dnc(b,s1,m,s2,m2-1);
	dnc(b,m,e1,m2+1,e2);
}

int escape(int V1, int V2)
{
	for(int b=0;b*B<N;b++) {
		if(b) {
			for(int j=0;j<M;j++) D[j]=D2[j]+V[b*B-1][j];
		}
		else {
			for(int j=0;j<M;j++) D[j]=(V1!=j)*0x3fffffff;
		}
		dnc(b,0,M-1,0,M-1);
	}
	return D2[V2];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8192 KB Output is correct
2 Correct 17 ms 8192 KB Output is correct
3 Correct 115 ms 9848 KB Output is correct
4 Correct 17 ms 8192 KB Output is correct
5 Correct 17 ms 8192 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 177 ms 1404 KB Output is correct
12 Correct 6 ms 384 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11969 ms 788 KB Output is correct
2 Correct 7605 ms 896 KB Output is correct
3 Correct 11903 ms 792 KB Output is correct
4 Correct 12059 ms 796 KB Output is correct
5 Correct 11717 ms 888 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Execution timed out 20059 ms 888 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 16000 KB Output is correct
2 Correct 84 ms 16044 KB Output is correct
3 Correct 76 ms 16000 KB Output is correct
4 Correct 126 ms 16760 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12042 ms 888 KB Output is correct
2 Correct 7670 ms 760 KB Output is correct
3 Correct 11913 ms 888 KB Output is correct
4 Correct 12044 ms 792 KB Output is correct
5 Correct 11652 ms 800 KB Output is correct
6 Correct 76 ms 16000 KB Output is correct
7 Correct 82 ms 16000 KB Output is correct
8 Correct 83 ms 16000 KB Output is correct
9 Correct 130 ms 16760 KB Output is correct
10 Correct 17 ms 8192 KB Output is correct
11 Correct 18 ms 8192 KB Output is correct
12 Correct 115 ms 9848 KB Output is correct
13 Correct 17 ms 8192 KB Output is correct
14 Correct 19 ms 8320 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 6 ms 384 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 512 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 6 ms 384 KB Output is correct
24 Correct 6 ms 512 KB Output is correct
25 Correct 171 ms 1532 KB Output is correct
26 Correct 6 ms 384 KB Output is correct
27 Execution timed out 20079 ms 888 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11975 ms 916 KB Output is correct
2 Correct 7611 ms 888 KB Output is correct
3 Correct 11894 ms 792 KB Output is correct
4 Correct 12037 ms 796 KB Output is correct
5 Correct 11581 ms 888 KB Output is correct
6 Correct 76 ms 16000 KB Output is correct
7 Correct 85 ms 16172 KB Output is correct
8 Correct 74 ms 16000 KB Output is correct
9 Correct 130 ms 16760 KB Output is correct
10 Correct 17 ms 8192 KB Output is correct
11 Correct 17 ms 8192 KB Output is correct
12 Correct 115 ms 9848 KB Output is correct
13 Correct 17 ms 8192 KB Output is correct
14 Correct 17 ms 8192 KB Output is correct
15 Correct 15932 ms 16812 KB Output is correct
16 Execution timed out 20090 ms 16560 KB Time limit exceeded
17 Halted 0 ms 0 KB -