oj.uz

Submission #123068

# Submission time Handle Problem Language Result Execution time Memory
123068 2019-06-30T07:24:42 Z MAMBA Wombats (IOI13_wombats) C++14
0 / 100
 641 ms 72828 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for (int i = j ; i < (int)k; i++)

inline bool smin(int &l, int r) {
	if (r < l) return l = r, true;
	return false;
}

inline bool smax(int &l ,int r) {
	if (l < r) return l = r , true;
	return false;
}

const int LEN = 350;
const int MAXN = 5000 / LEN + 10;

int R , C;
int dist[MAXN][2][202][202];
int H[5000][200];
int V[5000][200];

struct segment {
	int d[202][202];	
	segment() {
		memset(d , 63 , sizeof(d));
	}
} seg[MAXN << 2];

void solve(int So , int Z, const segment &L, const segment &R , segment &res, int l , int r, int s , int t) {
	if (l >= r) return;
	int mid = l + r >> 1;

	int best = s;
	int val = 1e9 + 10;

	rep(i , s , t + 1)
		if (smin(val , L.d[So][i] +  V[Z][i] + R.d[i][mid]))
			best = i;
	res.d[So][mid] = val;
	solve(So , Z , L , R , res , l , mid , s , best);
	solve(So , Z , L , R , res , mid + 1 , r , best , t);
}

inline void merge(segment &res , const segment &l, const segment &r, int mid) {
	rep(so , 0 , C) 
		solve(so, mid * LEN - 1 , l , r , res, 0 , C, 0 , C - 1);
}


void build(int l = 0, int r = (R - 1) / LEN + 1, int id = 1) {
	if (l == r - 1) {
		rep(i , 0 , C)
			rep(j , 0 , C)
				seg[id].d[i][j] = dist[id][0][i][j];
		return;
	}
	int mid = l + r >> 1;
	build(l , mid , id << 1);
	build(mid , r ,id << 1 | 1);
	merge(seg[id] , seg[id << 1] ,  seg[id << 1 | 1] , mid);
}

void segUpt(int pos , int l = 0, int r = (R - 1) / LEN + 1, int id = 1) {
	if (l == r - 1) {
		rep(i , 0 , C)
			rep(j , 0 , C)
				seg[id].d[i][j] = dist[id][0][i][j];
		return;
	}
	int mid = l +r >> 1;
	if (pos < mid) segUpt(pos , l, mid , id << 1);
	else segUpt(pos , mid , r, id << 1 | 1);
	merge(seg[id] , seg[id << 1] ,  seg[id << 1 | 1] , mid);

}

inline void build_len(int id) {
	memset(dist[id] , 63 , sizeof(dist[id]));
	rep(i , 0 , C) {
		dist[id][0][i][i] = 0;
		rep(j , i + 1, C)
			dist[id][0][i][j] = dist[id][0][j][i] = dist[id][0][i][j - 1] + H[id * LEN][j - 1];
	}
	for (int i = id * LEN + 1; i < min(R , (id + 1) * LEN); i++) {
		memset(dist[id][1] , 63 , sizeof(dist[id][1]));
		rep(x , 0 , C) {
			for (int y = 0; y < C; y++) {
				smin(dist[id][1][x][y] , dist[id][0][x][y] + V[i - 1][y]);
				if (y)
					smin(dist[id][1][x][y] , dist[id][1][x][y - 1] + H[id][y - 1]);
			}
			for (int y = C - 1; ~y; y--) 
				if (y + 1 != C)
					smin(dist[id][1][x][y] , dist[id][1][x][y + 1] + H[id][y]);
		}
		rep(x , 0 , C) rep(y , 0 , C) dist[id][0][x][y] = dist[id][1][x][y];
	}
}

void init(int R_, int C_, int H_[5000][200], int V_[5000][200]) {
    // TODO : init sqrt decomposition then segment build
	R = R_ , C = C_;
	rep(i , 0 , R)
		rep(j , 0 , C - 1)
			H[i][j] = H_[i][j];
	rep(i , 0 , R - 1)
		rep(j , 0 , C)
			V[i][j] = V_[i][j];

	for (int i = 0; i * LEN  < R; i++)
		build_len(i);
	build();
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
	build_len(P / LEN);
	segUpt(P / LEN);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
	build_len((P + 1) / LEN);
	segUpt(P / LEN);
}

int escape(int V1, int V2) {
    return seg[1].d[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;
      ^~~
wombats.cpp: In function 'void solve(int, int, const segment&, const segment&, segment&, int, int, int, int)':
wombats.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wombats.cpp: In function 'void build(int, int, int)':
wombats.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wombats.cpp: In function 'void segUpt(int, int, int, int)':
wombats.cpp:74:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l +r >> 1;
            ~~^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 109 ms 57084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16120 KB Output is correct
2 Incorrect 14 ms 15992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 613 ms 16380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 118 ms 72828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 641 ms 16280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 621 ms 16368 KB Output isn't correct
2 Halted 0 ms 0 KB -