Submission #126093

#	Time	Username	Problem	Language	Result	Execution time	Memory
126093		nxteru	Wombats (IOI13_wombats)	C++14	12 / 100	336 ms	262148 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000001
struct node{
	int n,d[100][100];
	void ini(int x){
		n=x;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(i==j)d[i][j]=0;
				else d[i][j]=INF;
			}
		}
	}
	node plus(node &q){
		node res;
		res.ini(n);
		int a[100][100];
		for(int i=n-1;i>-n;i--){
			for(int j=max(-i,0);i+j<n&&j<n;j++){
				int x,y;
				if(j-1>=0)x=a[i+j][j-1];
				else x=0;
				if(i+j+1<n)y=a[i+j+1][j];
				else y=n-1;
				for(int k=x;k<=y;k++)if(d[i+j][k]+q.d[k][j]<d[i+j][x]+q.d[x][j])x=k;
				a[i+j][j]=x;
				res.d[i+j][j]=min(d[i+j][x]+q.d[x][j],INF);
			}
		}
		return res;
	}
};
struct SEG{
	int n,k,id[1<<14];
	node seg[10011];
	void ini(int x){
		n=x;
		for(int i=0;i<1<<14;i++)id[i]=-1;
		k=0;
		for(int i=0;i<5000;i++){
			int a=i+(1<<13)-1;
			if(id[a]==-1)id[a]=k++;
			while(a>0){
				a=(a-1)/2;
				if(id[a]==-1)id[a]=k++;
				if(id[a*2+1]==-1)id[a*2+1]=k++;
				if(id[a*2+2]==-1)id[a*2+2]=k++;
			}
		}
		for(int i=0;i<k;i++)seg[i].ini(n);
	}
	void up(int a,node &q){
		a+=(1<<13)-1;
		seg[id[a]]=q;
		while(a>0){
			a=(a-1)/2;
			seg[id[a]]=seg[id[a*2+1]].plus(seg[id[a*2+2]]);
		}
	}
	int dis(int a,int b){
		return seg[id[0]].d[a][b];
	}
};
int h[5000][100],w[5000][100],n,m,p[100];
SEG s;
void change(int x){
	p[0]=0;
	for(int i=1;i<m;i++)p[i]=p[i-1]+h[x][i-1];
	node res;
	res.ini(m);
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			res.d[i][j]=p[max(i,j)]-p[min(i,j)]+w[x][j];
		}
	}
	s.up(x,res);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
   n=R,m=C;
   s.ini(m);
   for(int i=0;i<n;i++)for(int j=0;j<m-1;j++)h[i][j]=H[i][j];
   for(int i=0;i<n-1;i++)for(int j=0;j<m;j++)w[i][j]=V[i][j];
   for(int i=0;i<n;i++)change(i);
}
void changeH(int a, int b, int x) {
    h[a][b]=x;
    change(a);
}
 
void changeV(int a, int b, int x) {
    w[a][b]=x;
    change(a);
}
 
int escape(int a, int b) {
    return s.dis(a,b);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

• Subtask 1: 0 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24