oj.uz

답안 #227217

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
227217 2020-04-26T14:17:45 Z kig9981 웜뱃 (IOI13_wombats) C++17
39 / 100
 1020 ms 100856 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#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=20, SZ=1<<8;
int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
 
void set_md(int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(s==e) return;
	set_md(2*bit,s,m);
	set_md(2*bit+1,m+1,e);
	md[bit]=min((m+1)*B-1,N-1);
}
 
int get_cost(int h, int s, int e)
{
	if(s>e) swap(s,e);
	return PS[h][e]-PS[h][s];
}
 
void dnc(int h, 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]+get_cost(h,i,m2)<D[m]+get_cost(h,m,m2)) m=i;
	D2[m2]=D[m]+get_cost(h,m,m2);
	dnc(h,s1,m,s2,m2-1);
	dnc(h,m,e1,m2+1,e2);
}
 
void dijk(int b)
{
	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]=D2[j]+V[b*B+i-1][j];
			}
			else {
				for(int j=0;j<M;j++) D[j]=(r!=j)*0x3fffffff;
			}
			dnc(b*B+i,0,M-1,0,M-1);
		}
		for(int j=0;j<M;j++) tree[SZ+b][r][j]=D2[j];
	}
}
 
void combine(int p, int l, int r)
{
	for(int i=0;i<M;i++) {
		int k=0;
		for(int j=1;j<M;j++) if(tree[l][i][k]+V[md[p]][k]+tree[r][k][0]>tree[l][i][j]+V[md[p]][j]+tree[r][j][0]) k=j;
		for(int j=0;j<M;j++) {
			while(k+1<M && tree[l][i][k]+V[md[p]][k]+tree[r][k][j]>tree[l][i][k+1]+V[md[p]][k+1]+tree[r][k+1][j]) k++;
			tree[p][i][j]=min(tree[l][i][k]+V[md[p]][k]+tree[r][k][j],0x3f3f3f3f);
		}
	}
}
 
void init(int R, int C, int (*H)[200], int (*V)[200])
{
	N=R; M=C; memset(tree,0x3f,sizeof(tree));
	for(int i=0;i<N;i++) for(int j=0;j<M-1;j++) {
		::H[i][j]=H[i][j];
		PS[i][j+1]=PS[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<SZ;i++) {
		if(i*B<N) dijk(i);
		else for(int j=0;j<M;j++) tree[SZ+i][j][j]=0;
	}
	set_md();
	for(int i=SZ;--i;) combine(i,2*i,2*i+1);
}
 
void changeH(int P, int Q, int W)
{
    H[P][Q]=W;
	for(int j=0;j<M;j++) PS[P][j+1]=PS[P][j]+H[P][j];
	dijk(P/B);
	for(int n=SZ+P/B;n>>=1;) combine(n,2*n,2*n+1);
}
 
void changeV(int P, int Q, int W)
{
    V[P][Q]=W;
	if(P/B==(P+1)/B) dijk(P/B);
	for(int n=SZ+P/B;n>>=1;) combine(n,2*n,2*n+1);
}
 
int escape(int V1, int V2)
{
	return tree[1][V1][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

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 88312 KB Output is correct
2 Correct 47 ms 88312 KB Output is correct
3 Correct 139 ms 89976 KB Output is correct
4 Correct 49 ms 88312 KB Output is correct
5 Correct 48 ms 88440 KB Output is correct
6 Correct 41 ms 80504 KB Output is correct
7 Correct 42 ms 80504 KB Output is correct
8 Correct 42 ms 80504 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 80512 KB Output is correct
2 Correct 64 ms 80504 KB Output is correct
3 Correct 50 ms 80504 KB Output is correct
4 Correct 45 ms 80632 KB Output is correct
5 Correct 50 ms 80632 KB Output is correct
6 Correct 44 ms 80632 KB Output is correct
7 Correct 44 ms 80632 KB Output is correct
8 Correct 46 ms 80504 KB Output is correct
9 Correct 49 ms 80504 KB Output is correct
10 Correct 45 ms 80632 KB Output is correct
11 Correct 133 ms 81656 KB Output is correct
12 Correct 43 ms 80632 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1010 ms 81016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 100088 KB Output is correct
2 Correct 63 ms 100088 KB Output is correct
3 Correct 55 ms 100088 KB Output is correct
4 Correct 114 ms 100856 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 998 ms 80944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1020 ms 80996 KB Output isn't correct
2 Halted 0 ms 0 KB -