oj.uz

Submission #125835

# Submission time Handle Problem Language Result Execution time Memory
125835 2019-07-06T12:28:24 Z MoNsTeR_CuBe Wombats (IOI13_wombats) C++17
9 / 100
 20000 ms 262148 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
 
int row, col;
 
int sum = 0;
 
int h[5000][200];
int v[5000][200];
 
const int INF = INT_MAX;
 
vector< vector< int > > Graph;
 
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    row = R;
    col = C;
    
	for(int i = 0; i < 5000; i++){
		for(int j = 0; j < 200; j++){
			h[i][j] = H[i][j];
			v[i][j] = V[i][j];
		}
	}
    
    if(C == 1){
		for(int i = 0; i < row-1; i++){
			sum += V[i][0];
		}
		return;
	}
    
    Graph.resize(R*C, vector< int > (R*C, -1));
    
    for(int i = 0; i < R; i++){
		for(int j = 0; j < C-1; j++){
			Graph[i*C+j][i*C+j+1] = H[i][j];
			Graph[i*C+j+1][i*C+j] = H[i][j];
		}
	}
	
	for(int i = 0; i < R-1; i++){
		for(int j = 0; j < C; j++){
			Graph[i*C+j][(i+1)*C+j] = V[i][j];
		}
	}
}
 
void changeH(int P, int Q, int W) {
    if(col == 1){
		sum += W - h[P][Q];
		h[P][Q] = W;
		return;
	}
	Graph[P*col+Q][P*col+Q+1] = W;
	Graph[P*col+Q+1][P*col+Q] = W;
}
 
void changeV(int P, int Q, int W) {
    if(col == 1){
		sum += W - v[P][Q];
		v[P][Q] = W;
		return;
	}
	Graph[P*col+Q][(P+1)*col+Q] = W;
}
 
int escape(int V1, int V2) {
    if(col == 1){
		return sum;
	}
	priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
	
	vector< int > dist(row*col, INF);
	
	dist[V1] = 0;
	pq.push(make_pair(0,V1));
	
	while(!pq.empty()){
		int node = pq.top().second;
		int cost = pq.top().first;
		pq.pop();
		
		//cout << node << ' ' << cost << endl;
		
		if(dist[node] != cost) continue;
		
		for(int i = 0; i < row*col; i++){
			if(Graph[node][i] != -1){
				if(dist[i] > cost + Graph[node][i]){
					dist[i] = cost+Graph[node][i];
					pq.push(make_pair(dist[i], i));
				}
			}
		}
	}
	
	return dist[(row-1)*col+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 14 ms 12024 KB Output is correct
2 Correct 14 ms 12152 KB Output is correct
3 Correct 85 ms 14840 KB Output is correct
4 Correct 14 ms 12024 KB Output is correct
5 Correct 15 ms 12024 KB Output is correct
6 Correct 12 ms 8184 KB Output is correct
7 Correct 12 ms 8184 KB Output is correct
8 Correct 12 ms 8184 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8184 KB Output is correct
2 Correct 11 ms 8184 KB Output is correct
3 Correct 11 ms 8184 KB Output is correct
4 Correct 106 ms 8892 KB Output is correct
5 Correct 95 ms 8904 KB Output is correct
6 Correct 99 ms 8824 KB Output is correct
7 Correct 112 ms 8824 KB Output is correct
8 Correct 89 ms 8696 KB Output is correct
9 Correct 101 ms 8952 KB Output is correct
10 Correct 88 ms 8824 KB Output is correct
11 Execution timed out 20033 ms 10316 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

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