oj.uz

Submission #126082

# Submission time Handle Problem Language Result Execution time Memory
126082 2019-07-07T02:47:07 Z nxteru Wombats (IOI13_wombats) C++14
12 / 100
 322 ms 262148 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000001
struct node{
	int n,d[200][200];
	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[200][200];
		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][200],w[5000][200],n,m,p[200];
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

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.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 45816 KB Output is correct
2 Correct 37 ms 45844 KB Output is correct
3 Correct 37 ms 45944 KB Output is correct
4 Correct 157 ms 199800 KB Output is correct
5 Correct 156 ms 199800 KB Output is correct
6 Correct 159 ms 199672 KB Output is correct
7 Correct 157 ms 199768 KB Output is correct
8 Correct 149 ms 191720 KB Output is correct
9 Correct 170 ms 199584 KB Output is correct
10 Correct 176 ms 191876 KB Output is correct
11 Correct 235 ms 200732 KB Output is correct
12 Correct 156 ms 199672 KB Output is correct

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 322 ms 262148 KB Execution killed with signal 9 (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 Runtime error 224 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

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