oj.uz

Submission #69880

# Submission time Handle Problem Language Result Execution time Memory
69880 2018-08-21T19:14:02 Z FLDutchman Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 28824 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];
int pre2[20][20];
vvi dist;
int sum = 0;
bool changed;


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();
	changed = 0;
	if(R <= 20 and C <= 20){
		FOR(i, 0, C){
			dijkstra(0, i);
			FOR(j, 0, C) pre2[i][j] = dist[R-1][j];
		}
	}

}

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

void changeV(int P, int Q, int W) {
	sum -= V[P][Q];
	V[P][Q] = W;
	sum += W;
	changed = 1;
    recomp();
}

int escape(int V1, int V2) {
	if(C == 1) return sum;
	if(C == 2) {
		return precomp[V1][V2];
	}
	if(!changed and R <= 20 and C <= 20) {
		return pre2[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 12408 KB Output is correct
2 Correct 13 ms 12516 KB Output is correct
3 Correct 83 ms 14836 KB Output is correct
4 Correct 13 ms 14836 KB Output is correct
5 Correct 15 ms 14836 KB Output is correct
6 Correct 2 ms 14836 KB Output is correct
7 Correct 2 ms 14836 KB Output is correct
8 Correct 2 ms 14836 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14836 KB Output is correct
2 Correct 3 ms 14836 KB Output is correct
3 Correct 3 ms 14836 KB Output is correct
4 Correct 5 ms 14836 KB Output is correct
5 Correct 4 ms 14836 KB Output is correct
6 Correct 5 ms 14836 KB Output is correct
7 Correct 6 ms 14836 KB Output is correct
8 Correct 6 ms 14836 KB Output is correct
9 Correct 5 ms 14836 KB Output is correct
10 Correct 6 ms 14836 KB Output is correct
11 Correct 91 ms 14836 KB Output is correct
12 Correct 6 ms 14836 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 14836 KB Output is correct
2 Correct 417 ms 14836 KB Output is correct
3 Correct 376 ms 14836 KB Output is correct
4 Correct 386 ms 14836 KB Output is correct
5 Correct 386 ms 14836 KB Output is correct
6 Correct 4 ms 14836 KB Output is correct
7 Correct 2 ms 14836 KB Output is correct
8 Correct 2 ms 14836 KB Output is correct
9 Correct 486 ms 14836 KB Output is correct
10 Correct 3 ms 14836 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2051 ms 19464 KB Output is correct
2 Correct 3314 ms 19544 KB Output is correct
3 Correct 2440 ms 19716 KB Output is correct
4 Correct 2234 ms 20984 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 20984 KB Output is correct
2 Correct 400 ms 20984 KB Output is correct
3 Correct 332 ms 20984 KB Output is correct
4 Correct 346 ms 20984 KB Output is correct
5 Correct 343 ms 20984 KB Output is correct
6 Correct 2234 ms 20984 KB Output is correct
7 Correct 2969 ms 20984 KB Output is correct
8 Correct 1932 ms 20984 KB Output is correct
9 Correct 2479 ms 21612 KB Output is correct
10 Correct 13 ms 21612 KB Output is correct
11 Correct 12 ms 21612 KB Output is correct
12 Correct 83 ms 21612 KB Output is correct
13 Correct 13 ms 21612 KB Output is correct
14 Correct 13 ms 21612 KB Output is correct
15 Correct 2 ms 21612 KB Output is correct
16 Correct 4 ms 21612 KB Output is correct
17 Correct 2 ms 21612 KB Output is correct
18 Correct 6 ms 21612 KB Output is correct
19 Correct 6 ms 21612 KB Output is correct
20 Correct 5 ms 21612 KB Output is correct
21 Correct 5 ms 21612 KB Output is correct
22 Correct 4 ms 21612 KB Output is correct
23 Correct 4 ms 21612 KB Output is correct
24 Correct 4 ms 21612 KB Output is correct
25 Correct 82 ms 21612 KB Output is correct
26 Correct 6 ms 21612 KB Output is correct
27 Correct 388 ms 21612 KB Output is correct
28 Execution timed out 20102 ms 26872 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 26872 KB Output is correct
2 Correct 471 ms 26872 KB Output is correct
3 Correct 328 ms 26872 KB Output is correct
4 Correct 403 ms 26872 KB Output is correct
5 Correct 324 ms 26872 KB Output is correct
6 Correct 2134 ms 26872 KB Output is correct
7 Correct 3909 ms 26872 KB Output is correct
8 Correct 2342 ms 26872 KB Output is correct
9 Correct 2481 ms 26872 KB Output is correct
10 Correct 15 ms 26872 KB Output is correct
11 Correct 11 ms 26872 KB Output is correct
12 Correct 83 ms 26872 KB Output is correct
13 Correct 13 ms 26872 KB Output is correct
14 Correct 13 ms 26872 KB Output is correct
15 Correct 1937 ms 28824 KB Output is correct
16 Execution timed out 20057 ms 28824 KB Time limit exceeded
17 Halted 0 ms 0 KB -