oj.uz

답안 #227216

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
227216 2020-04-26T14:15:01 Z kig9981 웜뱃 (IOI13_wombats) C++17
39 / 100
 996 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]=tree[l][i][k]+V[md[p]][k]+tree[r][k][j];
		}
	}
}
 
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 46 ms 88312 KB Output is correct
3 Correct 129 ms 89976 KB Output is correct
4 Correct 47 ms 88312 KB Output is correct
5 Correct 47 ms 88312 KB Output is correct
6 Correct 42 ms 80504 KB Output is correct
7 Correct 43 ms 80632 KB Output is correct
8 Correct 41 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 44 ms 80632 KB Output is correct
3 Correct 43 ms 80432 KB Output is correct
4 Correct 43 ms 80632 KB Output is correct
5 Correct 49 ms 80632 KB Output is correct
6 Correct 43 ms 80632 KB Output is correct
7 Correct 43 ms 80632 KB Output is correct
8 Correct 44 ms 80640 KB Output is correct
9 Correct 44 ms 80504 KB Output is correct
10 Correct 44 ms 80632 KB Output is correct
11 Correct 130 ms 81528 KB Output is correct
12 Correct 44 ms 80640 KB Output is correct

Subtask #3
0 / 16.0

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

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 100096 KB Output is correct
2 Correct 54 ms 100216 KB Output is correct
3 Correct 61 ms 100088 KB Output is correct
4 Correct 97 ms 100856 KB Output is correct

Subtask #5
0 / 21.0

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

Subtask #6
0 / 24.0

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