oj.uz

답안 #198735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198735 2020-01-27T13:39:41 Z arnold518 웜뱃 (IOI13_wombats) C++14
55 / 100
 8552 ms 262144 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXR = 5000;
const int MAXC = 200;
const int INF = 987654321;

int R, C, H[MAXR+10][MAXC+10], V[MAXR+10][MAXC+10];

struct Node
{
	vector<vector<int>> V;
	Node() { V=vector<vector<int>>(C, vector<int>(C)); }
};
Node tree[MAXR*4+10];

void add(Node &now, Node &lc, Node &rc, int pos)
{
	int i, j, k;
	now=Node();
	for(i=0; i<C; i++)
	{
		for(j=0; j<C; j++)
		{
			int t=INF;
			for(k=0; k<C; k++) t=min(t, lc.V[i][k]+rc.V[k][j]+V[pos][k]);
			now.V[i][j]=t;
		}
	}
}

void init(int node, int tl, int tr)
{
	if(tl==tr)
	{
		int i, j;
		tree[node]=Node();
		for(i=0; i<C; i++)
		{
			int s=0;
			for(j=i+1; j<C; j++)
			{
				s+=H[tl][j-1];
				tree[node].V[i][j]=tree[node].V[j][i]=s;
			}
		}
		return;
	}
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);
	add(tree[node], tree[node*2], tree[node*2+1], mid);
}

void init(int _R, int _C, int _H[5000][200], int _V[5000][200])
{
	int i, j;
	R=_R; C=_C;
	for(i=0; i<R; i++) for(j=0; j+1<C; j++) H[i][j]=_H[i][j];
	for(i=0; i+1<R; i++) for(j=0; j<C; j++) V[i][j]=_V[i][j];

	init(1, 0, R-1);
}

void updateH(int node, int tl, int tr, int y)
{
	if(tl==tr)
	{
		int i, j;
		for(i=0; i<C; i++)
		{
			int s=0;
			for(j=i+1; j<C; j++)
			{
				s+=H[tl][j-1];
				tree[node].V[i][j]=tree[node].V[j][i]=s;
			}
		}
		return;
	}
	int mid=tl+tr>>1;
	if(y<=mid) updateH(node*2, tl, mid, y);
	else updateH(node*2+1, mid+1, tr, y);
	add(tree[node], tree[node*2], tree[node*2+1], mid);
}

void updateV(int node, int tl, int tr, int y)
{
	int mid=tl+tr>>1;
	if(y==mid) { add(tree[node], tree[node*2], tree[node*2+1], mid); return; }
	if(y<=mid) updateV(node*2, tl, mid, y);
	else updateV(node*2+1, mid+1, tr, y);
	add(tree[node], tree[node*2], tree[node*2+1], mid);
}

void changeH(int P, int Q, int W)
{
	H[P][Q]=W;
	updateH(1, 0, R-1, P);
}

void changeV(int P, int Q, int W)
{
	V[P][Q]=W;
	updateV(1, 0, R-1, P);
}

int escape(int V1, int V2)
{
	return tree[1].V[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 init(int, int, int)':
wombats.cpp:54:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
wombats.cpp: In function 'void updateH(int, int, int, int)':
wombats.cpp:86:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
wombats.cpp: In function 'void updateV(int, int, int, int)':
wombats.cpp:94:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 9592 KB Output is correct
2 Correct 14 ms 9464 KB Output is correct
3 Correct 101 ms 12284 KB Output is correct
4 Correct 14 ms 9464 KB Output is correct
5 Correct 14 ms 9464 KB Output is correct
6 Correct 7 ms 760 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 6 ms 760 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 955 ms 9772 KB Output is correct
2 Correct 881 ms 9720 KB Output is correct
3 Correct 1008 ms 9848 KB Output is correct
4 Correct 894 ms 9976 KB Output is correct
5 Correct 929 ms 9848 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 6 ms 760 KB Output is correct
8 Correct 5 ms 760 KB Output is correct
9 Correct 4345 ms 9872 KB Output is correct
10 Correct 6 ms 760 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 18168 KB Output is correct
2 Correct 22 ms 18168 KB Output is correct
3 Correct 22 ms 18168 KB Output is correct
4 Correct 75 ms 19596 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 938 ms 9720 KB Output is correct
2 Correct 870 ms 9592 KB Output is correct
3 Correct 998 ms 10052 KB Output is correct
4 Correct 923 ms 9976 KB Output is correct
5 Correct 927 ms 9720 KB Output is correct
6 Correct 20 ms 18168 KB Output is correct
7 Correct 22 ms 18168 KB Output is correct
8 Correct 21 ms 18168 KB Output is correct
9 Correct 62 ms 19576 KB Output is correct
10 Correct 14 ms 9464 KB Output is correct
11 Correct 13 ms 9464 KB Output is correct
12 Correct 106 ms 12284 KB Output is correct
13 Correct 13 ms 9464 KB Output is correct
14 Correct 13 ms 9464 KB Output is correct
15 Correct 6 ms 760 KB Output is correct
16 Correct 6 ms 760 KB Output is correct
17 Correct 6 ms 760 KB Output is correct
18 Correct 6 ms 1016 KB Output is correct
19 Correct 6 ms 1016 KB Output is correct
20 Correct 6 ms 1016 KB Output is correct
21 Correct 6 ms 1016 KB Output is correct
22 Correct 6 ms 888 KB Output is correct
23 Correct 6 ms 1064 KB Output is correct
24 Correct 6 ms 1016 KB Output is correct
25 Correct 91 ms 3448 KB Output is correct
26 Correct 6 ms 1020 KB Output is correct
27 Correct 4319 ms 9824 KB Output is correct
28 Runtime error 3992 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 948 ms 9720 KB Output is correct
2 Correct 875 ms 9720 KB Output is correct
3 Correct 1006 ms 9848 KB Output is correct
4 Correct 902 ms 9976 KB Output is correct
5 Correct 928 ms 9724 KB Output is correct
6 Correct 20 ms 18168 KB Output is correct
7 Correct 21 ms 18168 KB Output is correct
8 Correct 24 ms 18172 KB Output is correct
9 Correct 66 ms 19576 KB Output is correct
10 Correct 14 ms 9464 KB Output is correct
11 Correct 14 ms 9464 KB Output is correct
12 Correct 105 ms 12360 KB Output is correct
13 Correct 17 ms 9464 KB Output is correct
14 Correct 19 ms 9464 KB Output is correct
15 Runtime error 8552 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -