oj.uz

Submission #69879

# Submission time Handle Problem Language Result Execution time Memory
69879 2018-08-21T19:09:58 Z FLDutchman Wombats (IOI13_wombats) C++14
43 / 100
 20000 ms 41932 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;
int sum = 0;


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]; sum += 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) {
	sum -= V[P][Q];
	V[P][Q] = W;
	sum += W;
    recomp();
}

int escape(int V1, int V2) {
	if(C == 1) return sum;
	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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12280 KB Output is correct
2 Correct 14 ms 12388 KB Output is correct
3 Correct 84 ms 14600 KB Output is correct
4 Correct 14 ms 14600 KB Output is correct
5 Correct 13 ms 14600 KB Output is correct
6 Correct 3 ms 14600 KB Output is correct
7 Correct 3 ms 14600 KB Output is correct
8 Correct 3 ms 14600 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14600 KB Output is correct
2 Correct 3 ms 14600 KB Output is correct
3 Correct 3 ms 14600 KB Output is correct
4 Correct 52 ms 14600 KB Output is correct
5 Correct 67 ms 14600 KB Output is correct
6 Correct 47 ms 14600 KB Output is correct
7 Correct 60 ms 14600 KB Output is correct
8 Correct 45 ms 14600 KB Output is correct
9 Correct 55 ms 14600 KB Output is correct
10 Correct 47 ms 14600 KB Output is correct
11 Execution timed out 20059 ms 14600 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 14600 KB Output is correct
2 Correct 413 ms 14600 KB Output is correct
3 Correct 334 ms 14600 KB Output is correct
4 Correct 339 ms 14600 KB Output is correct
5 Correct 354 ms 14600 KB Output is correct
6 Correct 3 ms 14600 KB Output is correct
7 Correct 2 ms 14600 KB Output is correct
8 Correct 2 ms 14600 KB Output is correct
9 Correct 459 ms 14600 KB Output is correct
10 Correct 3 ms 14600 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2310 ms 17488 KB Output is correct
2 Correct 3421 ms 17488 KB Output is correct
3 Correct 2544 ms 17532 KB Output is correct
4 Correct 2190 ms 18260 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 18260 KB Output is correct
2 Correct 399 ms 18260 KB Output is correct
3 Correct 318 ms 18260 KB Output is correct
4 Correct 336 ms 18260 KB Output is correct
5 Correct 396 ms 18260 KB Output is correct
6 Correct 2243 ms 18260 KB Output is correct
7 Correct 3321 ms 18260 KB Output is correct
8 Correct 1879 ms 18260 KB Output is correct
9 Correct 2126 ms 18372 KB Output is correct
10 Correct 13 ms 18372 KB Output is correct
11 Correct 14 ms 18372 KB Output is correct
12 Correct 90 ms 18372 KB Output is correct
13 Correct 14 ms 18372 KB Output is correct
14 Correct 13 ms 18372 KB Output is correct
15 Correct 3 ms 18372 KB Output is correct
16 Correct 2 ms 18372 KB Output is correct
17 Correct 2 ms 18372 KB Output is correct
18 Correct 88 ms 18372 KB Output is correct
19 Correct 36 ms 18372 KB Output is correct
20 Correct 39 ms 18372 KB Output is correct
21 Correct 53 ms 18372 KB Output is correct
22 Correct 40 ms 18372 KB Output is correct
23 Correct 45 ms 18372 KB Output is correct
24 Correct 52 ms 18372 KB Output is correct
25 Execution timed out 20073 ms 18372 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 18372 KB Output is correct
2 Correct 385 ms 18372 KB Output is correct
3 Correct 317 ms 18372 KB Output is correct
4 Correct 320 ms 18372 KB Output is correct
5 Correct 317 ms 18372 KB Output is correct
6 Correct 2086 ms 19848 KB Output is correct
7 Correct 3481 ms 19848 KB Output is correct
8 Correct 2202 ms 19848 KB Output is correct
9 Correct 2441 ms 20464 KB Output is correct
10 Correct 14 ms 20464 KB Output is correct
11 Correct 13 ms 20464 KB Output is correct
12 Correct 88 ms 20464 KB Output is correct
13 Correct 12 ms 20464 KB Output is correct
14 Correct 12 ms 20464 KB Output is correct
15 Correct 1878 ms 34128 KB Output is correct
16 Execution timed out 20055 ms 41932 KB Time limit exceeded
17 Halted 0 ms 0 KB -