#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)/2)
#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+100];
bool flag=false;
int H[5000][100],V[5000][100];
int R,C;
SEG merge(SEG A,SEG B) {
SEG RES;
for(int i=0;i<C;i++) {
for(int j=0;j<C;j++) {
RES.res[i][j]=inf;
for(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(int bas) {
pre[0][0]=pre[1][0]=0;
for(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];
pre[2][i]=pre[2][i-1]+H[bas+2][i-1];
}
if(bas+2==R) {
SEG RES;
for(int i=0;i<C;i++) {
for(int j=0;j<C;j++) {
RES.res[i][j]=inf;
for(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 {
SEG L,R;
for(int i=0;i<C;i++) {
for(int j=0;j<C;j++) {
L.res[i][j]=inf;
for(int k=0;k<C;k++) {
umin(L.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]);
}
}
for(int i=0;i<C;i++) {
for(int j=0;j<C;j++) {
R.res[i][j]=inf;
for(int k=0;k<C;k++) {
umin(R.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(L,R);
}
}
void up(int node,int bas,int son,int x,int y) {
if(bas>y || son<x) return ;
if(bas+2>=son) {
S[node]=create2(bas);
return ;
}
up(node*2,bas,orta,x,y);
up(node*2+1,orta,son,x,y);
S[node]=merge(S[node*2],S[node*2+1]);
}
void build(int node,int bas,int son) {
if(bas+2>=son) {
S[node]=create2(bas);
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];
}
}
if(C>200) {
flag=1;
return ;
}
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+1);
}
void changeV(int P, int Q, int W) {
V[P][Q]=W;
if(flag) return ;
up(1,0,R-1,P,P+1);
}
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:252:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
317 ms |
243832 KB |
Output is correct |
| 2 |
Incorrect |
358 ms |
243920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
243920 KB |
Output is correct |
| 2 |
Correct |
2 ms |
243920 KB |
Output is correct |
| 3 |
Correct |
2 ms |
243920 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
243920 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2858 ms |
243920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
326 ms |
248208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3108 ms |
248208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3320 ms |
248208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
