oj.uz

Submission #69878

# Submission time Handle Problem Language Result Execution time Memory
69878 2018-08-21T19:02:56 Z FLDutchman Wombats (IOI13_wombats) C++14
34 / 100
 20000 ms 24272 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define FOR(i,l,r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define pb push_back
#define mp make_pair

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const int NMAX = 1e5+10;

int H[5000][200], V[5000][200];
int R, C;

int precomp[2][2];
vvi dist;

vii adj(int r, int c){
	vii n;
	if(r < R-1) n.pb(mp(r+1 + R*c, V[r][c]));
	if(c > 0) n.pb( mp(r+R*(c-1), H[r][c-1]) );
	if(c < C-1) n.pb( mp( r+R*(c+1), H[r][c]) );
	return n;
}

void dijkstra(int r, int c){
	dist.assign(R, vi(C, 2e9));
	priority_queue<ii, vii, greater<ii>> q;
	q.push({0, r + R * c});
	//cerr<<r<<" "<<c<<endl;
	dist[r][c] = 0;
	while(!q.empty()){
		ii p = q.top(); q.pop();
		int d = p.fst, u = p.snd;
		int r = u%R, c = u/R;
		if(dist[r][c] < d) continue;
		for(ii p: adj(r, c)) {
			int v = p.fst, l = p.snd;
			//cout << l << endl;
			int &D = dist[v%R][v/R];
			if(d + l < D) {
				D = d + l;
				q.push({D, v});
			}
		}
	}
}

void recomp(){
	if(C == 2){
		dijkstra(0, 0);
		precomp[0][0] = dist[R-1][0];
		precomp[0][1] = dist[R-1][1];
		dijkstra(0, 1);
		precomp[1][0] = dist[R-1][0];
		precomp[1][1] = dist[R-1][1];
	}
}

void init(int r, int c, int h[5000][200], int v[5000][200]) {
	FOR(i, 0, r) FOR(j, 0, c) {H[i][j] = h[i][j]; V[i][j] = v[i][j];}
	R = r;
	C = c;
	dist.assign(R, vi(C, 2e9));
	recomp();
}

void changeH(int P, int Q, int W) {
	H[P][Q] = W;
	recomp();
}

void changeV(int P, int Q, int W) {
	V[P][Q] = W;
    recomp();
}

int escape(int V1, int V2) {
	if(C == 2) {
		return precomp[V1][V2];
	}

	dijkstra(0, V1);
	/*FOR(i, 0, R) {
		FOR(j, 0, C) cout << dist[i][j] << " ";
		cout << endl;
	}*/
    return dist[R-1][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;
      ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 12536 KB Output is correct
2 Correct 221 ms 12544 KB Output is correct
3 Execution timed out 20100 ms 13760 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13760 KB Output is correct
2 Correct 3 ms 13760 KB Output is correct
3 Correct 3 ms 13760 KB Output is correct
4 Correct 59 ms 13760 KB Output is correct
5 Correct 56 ms 13760 KB Output is correct
6 Correct 46 ms 13760 KB Output is correct
7 Correct 59 ms 13760 KB Output is correct
8 Correct 54 ms 13760 KB Output is correct
9 Correct 53 ms 13760 KB Output is correct
10 Correct 41 ms 13760 KB Output is correct
11 Execution timed out 20043 ms 13760 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 13760 KB Output is correct
2 Correct 413 ms 13760 KB Output is correct
3 Correct 330 ms 13760 KB Output is correct
4 Correct 321 ms 13760 KB Output is correct
5 Correct 322 ms 13760 KB Output is correct
6 Correct 2 ms 13760 KB Output is correct
7 Correct 4 ms 13760 KB Output is correct
8 Correct 4 ms 13760 KB Output is correct
9 Correct 466 ms 13760 KB Output is correct
10 Correct 3 ms 13760 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2601 ms 19580 KB Output is correct
2 Correct 3045 ms 19652 KB Output is correct
3 Correct 1981 ms 19716 KB Output is correct
4 Correct 2304 ms 21132 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 21132 KB Output is correct
2 Correct 429 ms 21132 KB Output is correct
3 Correct 320 ms 21132 KB Output is correct
4 Correct 396 ms 21132 KB Output is correct
5 Correct 323 ms 21132 KB Output is correct
6 Correct 2216 ms 21132 KB Output is correct
7 Correct 3334 ms 21132 KB Output is correct
8 Correct 2275 ms 21132 KB Output is correct
9 Correct 2569 ms 22352 KB Output is correct
10 Correct 275 ms 22352 KB Output is correct
11 Correct 269 ms 22352 KB Output is correct
12 Execution timed out 20054 ms 22352 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 22352 KB Output is correct
2 Correct 395 ms 22352 KB Output is correct
3 Correct 314 ms 22352 KB Output is correct
4 Correct 350 ms 22352 KB Output is correct
5 Correct 324 ms 22352 KB Output is correct
6 Correct 1806 ms 22684 KB Output is correct
7 Correct 2656 ms 22684 KB Output is correct
8 Correct 2453 ms 22688 KB Output is correct
9 Correct 2854 ms 24272 KB Output is correct
10 Correct 223 ms 24272 KB Output is correct
11 Correct 213 ms 24272 KB Output is correct
12 Execution timed out 20049 ms 24272 KB Time limit exceeded
13 Halted 0 ms 0 KB -