oj.uz

답안 #56508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56508 2018-07-11T14:21:53 Z hamzqq9 웜뱃 (IOI13_wombats) C++14
55 / 100
 20000 ms 247996 KB 
#include "wombats.h"
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)>>1)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 2000000001
#define N 1000000005
#define LOG 20
#define magic 100
#define MAX 1000005
#define KOK 350
#define EPS 0.000000000001
#define pw(x) (1<<(x))
#define PI 3.1415926535
using namespace std;
 
 
struct SEG {
 
	int res[100][100];
 
} S[5000*2+10];
 
bool flag=false;
short int H[5000][100],V[5000][100];
short int R,C;

SEG LL,RR,RES;
 
SEG merge(SEG A,SEG B) {
 
	for(short int i=0;i<C;i++) {
 
		for(short int j=0;j<C;j++) {
 
			RES.res[i][j]=inf;
 
			for(short int k=0;k<C;k++) {
 
				umin(RES.res[i][j],A.res[i][k]+B.res[k][j]);
 
			}
 
		}
 
	}
 
	return RES;
 
}

int pre[3][100];
 
SEG create2(short int bas,short int son) {
 
	for(short int i=1;i<C;i++) {
 
		pre[0][i]=pre[0][i-1]+H[bas][i-1];
 
		pre[1][i]=pre[1][i-1]+H[bas+1][i-1];
 
      	if(bas+2<=son) pre[2][i]=pre[2][i-1]+H[bas+2][i-1];
 
	}
 
	if(bas+2>son) {
 
		for(short int i=0;i<C;i++) {
 
			for(short int j=0;j<C;j++) {
 
				RES.res[i][j]=inf;
 
				for(short int k=0;k<C;k++) {
 
					umin(RES.res[i][j],V[bas][k]+abs(pre[0][k]-pre[0][i])+abs(pre[1][k]-pre[1][j]));
 
				}
 
				//printf("%d %d %d %d\n",bas,i,j,RES.res[i][j]);
 
			}
 
		}
 
		return RES;
	
	}
	else {
 
		for(short int i=0;i<C;i++) {
 
			for(short int j=0;j<C;j++) {
 
				LL.res[i][j]=inf;
				RR.res[i][j]=inf;
 
				for(short int k=0;k<C;k++) {
 
					umin(LL.res[i][j],V[bas][k]+abs(pre[0][k]-pre[0][i])+abs(pre[1][k]-pre[1][j]));
 
					umin(RR.res[i][j],V[bas+1][k]+abs(pre[1][k]-pre[1][i])+abs(pre[2][k]-pre[2][j]));
 
				}
 
				//printf("%d %d %d %d\n",bas,i,j,RES.res[i][j]);
 
			}
 
		}	
 
		return merge(LL,RR);
	
	}
 
}
 
void up(short int node,short int bas,short int son,short int x,short int y) {
 
	if(bas>y || son<=x) return ;
 
	if(bas+2>=son) {
 
		S[node]=create2(bas,son);
 
		return ;
 
	}
 
	up(node<<1,bas,orta,x,y);
	up((node<<1)+1,orta,son,x,y);
 
	S[node]=merge(S[node<<1],S[(node<<1)+1]);
 
}
 
void build(short int node,short int bas,short int son) {
 
	if(bas+2>=son) {
 
		S[node]=create2(bas,son);
 
		return ;
 
	}
 
	build(node*2,bas,orta);
	build(node*2+1,orta,son);
 
	S[node]=merge(S[node*2],S[node*2+1]);
 
}
 
void init(int R, int C, int H[5000][200], int V[5000][200]) {
 
	::R=R;
	::C=C;
 
	for(int i=0;i<R;i++) {
 
		for(int j=0;j<C;j++) {
 
			::H[i][j]=H[i][j];
			::V[i][j]=V[i][j];
 
		}
 
	}
 
	build(1,0,R-1);
 
}
 
void changeH(int P, int Q, int W) {
    
	H[P][Q]=W;
 
	if(flag) return ;
 
	up(1,0,R-1,P-1,P);
 
}
 
void changeV(int P, int Q, int W) {
    
	V[P][Q]=W;
 
	if(flag) return ;
 
	up(1,0,R-1,P,P);
 
}
 
int shp(int x,int y) {
 
 
 
}
 
int escape(int V1, int V2) {
 
	if(flag) return shp(V1,V2);
 
	return S[1].res[V1][V2];
 
}
/*
int h[5000][200],v[5000][200];
 
int main() {
 
	freopen("sample.in","r",stdin);
 
	int r,c;
 
	scanf("%d %d",&r,&c);
 
	for(int i=0;i<r;i++) {
 
		for(int j=0;j<c-1;j++) {
 
			scanf("%d",&h[i][j]);
 
		}
 
	}
 
	for(int i=0;i<r-1;i++) {
 
		for(int j=0;j<c;j++) {
 
			scanf("%d",&v[i][j]);
 
		}
 
	}
 
	init(r,c,h,v);
 
	int q;
 
	scanf("%d",&q);
 
	while(q--) {
 
		int t,x,y,z;
 
		scanf("%d",&t);
 
		if(t==1) {
 
			scanf("%d %d %d",&x,&y,&z);
 
			changeH(x,y,z);
 
		}
		else if(t==2){
 
			scanf("%d %d %d",&x,&y,&z);
 
			changeV(x,y,z);
 
		}
		else {
 
			scanf("%d %d",&x,&y);
 
			printf("%d\n",escape(x,y));
 
		}
 
	}
 
}*/

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;
      ^~~
wombats.cpp: In function 'int shp(int, int)':
wombats.cpp:224:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 328 ms 242936 KB Output is correct
2 Correct 318 ms 242936 KB Output is correct
3 Correct 395 ms 244488 KB Output is correct
4 Correct 351 ms 244488 KB Output is correct
5 Correct 358 ms 244488 KB Output is correct
6 Correct 2 ms 244488 KB Output is correct
7 Correct 2 ms 244488 KB Output is correct
8 Correct 3 ms 244488 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 244488 KB Output is correct
2 Correct 2 ms 244488 KB Output is correct
3 Correct 2 ms 244488 KB Output is correct
4 Correct 5 ms 244488 KB Output is correct
5 Correct 4 ms 244488 KB Output is correct
6 Correct 5 ms 244488 KB Output is correct
7 Correct 5 ms 244488 KB Output is correct
8 Correct 5 ms 244488 KB Output is correct
9 Correct 4 ms 244488 KB Output is correct
10 Correct 5 ms 244488 KB Output is correct
11 Correct 93 ms 244488 KB Output is correct
12 Correct 6 ms 244488 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1728 ms 244488 KB Output is correct
2 Correct 1518 ms 244488 KB Output is correct
3 Correct 1834 ms 244488 KB Output is correct
4 Correct 1455 ms 244488 KB Output is correct
5 Correct 1554 ms 244488 KB Output is correct
6 Correct 3 ms 244488 KB Output is correct
7 Correct 2 ms 244488 KB Output is correct
8 Correct 2 ms 244488 KB Output is correct
9 Correct 7206 ms 244488 KB Output is correct
10 Correct 2 ms 244488 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 337 ms 247084 KB Output is correct
2 Correct 364 ms 247180 KB Output is correct
3 Correct 366 ms 247232 KB Output is correct
4 Correct 409 ms 247928 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1684 ms 247928 KB Output is correct
2 Correct 1390 ms 247928 KB Output is correct
3 Correct 1873 ms 247928 KB Output is correct
4 Correct 1504 ms 247928 KB Output is correct
5 Correct 1835 ms 247928 KB Output is correct
6 Correct 365 ms 247928 KB Output is correct
7 Correct 398 ms 247928 KB Output is correct
8 Correct 398 ms 247928 KB Output is correct
9 Correct 388 ms 247956 KB Output is correct
10 Correct 358 ms 247956 KB Output is correct
11 Correct 343 ms 247956 KB Output is correct
12 Correct 459 ms 247956 KB Output is correct
13 Correct 413 ms 247956 KB Output is correct
14 Correct 386 ms 247956 KB Output is correct
15 Correct 2 ms 247956 KB Output is correct
16 Correct 2 ms 247956 KB Output is correct
17 Correct 3 ms 247956 KB Output is correct
18 Correct 5 ms 247956 KB Output is correct
19 Correct 6 ms 247956 KB Output is correct
20 Correct 6 ms 247956 KB Output is correct
21 Correct 6 ms 247956 KB Output is correct
22 Correct 4 ms 247956 KB Output is correct
23 Correct 4 ms 247956 KB Output is correct
24 Correct 5 ms 247956 KB Output is correct
25 Correct 107 ms 247956 KB Output is correct
26 Correct 6 ms 247956 KB Output is correct
27 Correct 7628 ms 247956 KB Output is correct
28 Execution timed out 20019 ms 247956 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1685 ms 247956 KB Output is correct
2 Correct 1652 ms 247956 KB Output is correct
3 Correct 2116 ms 247956 KB Output is correct
4 Correct 1810 ms 247956 KB Output is correct
5 Correct 1718 ms 247956 KB Output is correct
6 Correct 354 ms 247956 KB Output is correct
7 Correct 341 ms 247956 KB Output is correct
8 Correct 349 ms 247956 KB Output is correct
9 Correct 427 ms 247996 KB Output is correct
10 Correct 392 ms 247996 KB Output is correct
11 Correct 377 ms 247996 KB Output is correct
12 Correct 406 ms 247996 KB Output is correct
13 Correct 382 ms 247996 KB Output is correct
14 Correct 332 ms 247996 KB Output is correct
15 Execution timed out 20081 ms 247996 KB Time limit exceeded
16 Halted 0 ms 0 KB -