oj.uz

Submission #56505

# Submission time Handle Problem Language Result Execution time Memory
56505 2018-07-11T14:10:00 Z hamzqq9 Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 257116 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)/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,int son) {

	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];

      	if(bas+2<=son) pre[2][i]=pre[2][i-1]+H[bas+2][i-1];

	}

	if(bas+2>son) {

		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,son);

		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,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];

		}

	}
	
	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:250:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 243960 KB Output is correct
2 Correct 316 ms 243972 KB Output is correct
3 Correct 489 ms 245632 KB Output is correct
4 Correct 369 ms 245632 KB Output is correct
5 Correct 370 ms 245632 KB Output is correct
6 Correct 3 ms 245632 KB Output is correct
7 Correct 3 ms 245632 KB Output is correct
8 Correct 2 ms 245632 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2575 ms 245632 KB Output is correct
2 Correct 2177 ms 245632 KB Output is correct
3 Correct 2551 ms 245632 KB Output is correct
4 Correct 2146 ms 245632 KB Output is correct
5 Correct 2473 ms 245632 KB Output is correct
6 Correct 2 ms 245632 KB Output is correct
7 Correct 3 ms 245632 KB Output is correct
8 Correct 2 ms 245632 KB Output is correct
9 Correct 11295 ms 245632 KB Output is correct
10 Correct 2 ms 245632 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 248280 KB Output is correct
2 Correct 372 ms 248280 KB Output is correct
3 Correct 359 ms 248280 KB Output is correct
4 Correct 387 ms 249112 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2512 ms 249112 KB Output is correct
2 Correct 2260 ms 249112 KB Output is correct
3 Correct 2994 ms 249112 KB Output is correct
4 Correct 2360 ms 249112 KB Output is correct
5 Correct 2478 ms 249112 KB Output is correct
6 Correct 327 ms 249112 KB Output is correct
7 Correct 317 ms 249112 KB Output is correct
8 Correct 392 ms 249112 KB Output is correct
9 Correct 438 ms 249820 KB Output is correct
10 Correct 365 ms 249820 KB Output is correct
11 Correct 370 ms 249820 KB Output is correct
12 Correct 401 ms 249820 KB Output is correct
13 Correct 347 ms 249820 KB Output is correct
14 Correct 329 ms 249820 KB Output is correct
15 Correct 2 ms 249820 KB Output is correct
16 Correct 3 ms 249820 KB Output is correct
17 Correct 2 ms 249820 KB Output is correct
18 Correct 4 ms 249820 KB Output is correct
19 Correct 5 ms 249820 KB Output is correct
20 Correct 5 ms 249820 KB Output is correct
21 Correct 5 ms 249820 KB Output is correct
22 Correct 5 ms 249820 KB Output is correct
23 Correct 4 ms 249820 KB Output is correct
24 Correct 4 ms 249820 KB Output is correct
25 Correct 84 ms 249820 KB Output is correct
26 Correct 5 ms 249820 KB Output is correct
27 Correct 11116 ms 249820 KB Output is correct
28 Execution timed out 20057 ms 256264 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2142 ms 256264 KB Output is correct
2 Correct 2325 ms 256264 KB Output is correct
3 Correct 2515 ms 256264 KB Output is correct
4 Correct 2448 ms 256264 KB Output is correct
5 Correct 2507 ms 256264 KB Output is correct
6 Correct 312 ms 256264 KB Output is correct
7 Correct 309 ms 256264 KB Output is correct
8 Correct 348 ms 256264 KB Output is correct
9 Correct 372 ms 257116 KB Output is correct
10 Correct 334 ms 257116 KB Output is correct
11 Correct 363 ms 257116 KB Output is correct
12 Correct 435 ms 257116 KB Output is correct
13 Correct 352 ms 257116 KB Output is correct
14 Correct 379 ms 257116 KB Output is correct
15 Runtime error 363 ms 257116 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -