제출 #198735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
198735		arnold518	웜뱃 (IOI13_wombats)	C++14	55 / 100	8552 ms	262144 KiB

wombats

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

컴파일 시 표준 에러 (stderr) 메시지

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24