oj.uz

Submission #358304

# Submission time Handle Problem Language Result Execution time Memory
358304 2021-01-25T09:58:04 Z amunduzbaev Wombats (IOI13_wombats) C++14
28 / 100
 20000 ms 73480 KB 
#include "wombats.h"

#ifndef EVAL
#include "grader.cpp"
#endif 

#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define ff first
#define ss second

const int N = 5e3+5;

vector<pair<int, int>> edges[N*200];
int n, m;

int h[N][N], v[N][N];

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R, m = C;
    for(int i=0;i<n-1;i++){
		for(int j=0;j<m;j++) v[i][j] = V[i][j];
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++) h[i][j] = H[i][j];
	}
	
	for(int i=0;i<n-1;i++){
		for(int j=0;j<m;j++){
			edges[i * m + j].pb({(i+1) * m + j, v[i][j]});
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m-1;j++){
			edges[i * m + j].pb({i * m + j + 1, h[i][j]});
			edges[i * m + j + 1].pb({i * m + j, h[i][j]});
		}
	}
}

void changeH(int p, int q, int w) {
    for(auto &x:edges[p*m+q]){
		if(x.ff == p*m+q+1) x.ss = w;
	}
	for(auto &x:edges[p*m+q+1]){
		if(x.ff == p*m+q) x.ss = w;
	}
}

void changeV(int p, int q, int w) {
    for(auto &x:edges[p*m+q]){
		if(x.ff == (p+1)*m+q){
			x.ss = w;
		}
	}
}

#define ll long long
const ll mod = 1e18+7;

int escape(int V1, int V2) {
    priority_queue<pair<int, int>> qq;
	qq.push({0, V1});
	vector<ll> dis(n*m, mod);
	dis[V1] = 0;
	
	while(!qq.empty()){
		int cur = qq.top().ss, dd = qq.top().ff; qq.pop();
		if(dd > dis[cur]) continue;
		for(auto x:edges[cur]){
			if(dis[x.ff] > dis[cur] + x.ss){
				dis[x.ff] = dis[cur] + x.ss;
				qq.push({-dis[x.ff], x.ff});
			}
		}
	}
	
	return dis[m * (n-1) + V2];
}

/*

3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1

*/

Compilation message

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 68332 KB Output is correct
2 Correct 101 ms 68332 KB Output is correct
3 Execution timed out 20056 ms 70072 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 17 ms 23788 KB Output is correct
4 Correct 34 ms 24044 KB Output is correct
5 Correct 25 ms 24044 KB Output is correct
6 Correct 26 ms 24172 KB Output is correct
7 Correct 39 ms 24044 KB Output is correct
8 Correct 31 ms 24044 KB Output is correct
9 Correct 33 ms 24044 KB Output is correct
10 Correct 31 ms 24044 KB Output is correct
11 Correct 8253 ms 25456 KB Output is correct
12 Correct 40 ms 24044 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 25580 KB Output is correct
2 Correct 247 ms 25688 KB Output is correct
3 Correct 166 ms 25452 KB Output is correct
4 Correct 165 ms 25504 KB Output is correct
5 Correct 166 ms 25452 KB Output is correct
6 Correct 16 ms 23788 KB Output is correct
7 Correct 16 ms 23788 KB Output is correct
8 Correct 16 ms 23788 KB Output is correct
9 Correct 224 ms 25580 KB Output is correct
10 Correct 17 ms 23916 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 72684 KB Output is correct
2 Correct 1119 ms 72632 KB Output is correct
3 Correct 491 ms 72556 KB Output is correct
4 Execution timed out 20057 ms 73384 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 25452 KB Output is correct
2 Correct 254 ms 25900 KB Output is correct
3 Correct 164 ms 25504 KB Output is correct
4 Correct 163 ms 25452 KB Output is correct
5 Correct 161 ms 25452 KB Output is correct
6 Correct 484 ms 72704 KB Output is correct
7 Correct 1122 ms 72812 KB Output is correct
8 Correct 504 ms 72812 KB Output is correct
9 Execution timed out 20027 ms 73480 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 25480 KB Output is correct
2 Correct 229 ms 25584 KB Output is correct
3 Correct 163 ms 25580 KB Output is correct
4 Correct 184 ms 25452 KB Output is correct
5 Correct 176 ms 25620 KB Output is correct
6 Correct 490 ms 72556 KB Output is correct
7 Correct 1166 ms 72556 KB Output is correct
8 Correct 502 ms 72588 KB Output is correct
9 Execution timed out 20095 ms 73292 KB Time limit exceeded
10 Halted 0 ms 0 KB -