oj.uz

Submission #125843

# Submission time Handle Problem Language Result Execution time Memory
125843 2019-07-06T12:59:17 Z MoNsTeR_CuBe Wombats (IOI13_wombats) C++17
37 / 100
 20000 ms 17748 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< pair<int, 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);
    
    for(int i = 0; i < R; i++){
		for(int j = 0; j < C-1; j++){
			Graph[i*C+j].push_back(make_pair(i*C+j+1, H[i][j]));
			Graph[i*C+j+1].push_back(make_pair(i*C+j, 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].push_back(make_pair((i+1)*C+j, V[i][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;
	}
	for(auto &p : Graph[P*col+Q]){
		if(p.first == P*col+Q+1){
			p.second = W;
		}
	}
	for(auto &p : Graph[P*col+Q+1]){
		if(p.first == P*col+Q){
			p.second = W;
		}
	}
	/*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;
	}
	for(auto &p : Graph[P*col+Q]){
		if(p.first == (P+1)*col+Q) p.second = W;
	}
	//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(auto p : Graph[node]){
			if(dist[p.first] > cost + p.second){
				dist[p.first] = cost+p.second;
				pq.push(make_pair(dist[p.first], p.first));
			}
		}
	}
	
	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 12028 KB Output is correct
2 Correct 14 ms 12028 KB Output is correct
3 Correct 85 ms 13688 KB Output is correct
4 Correct 14 ms 12024 KB Output is correct
5 Correct 14 ms 12024 KB Output is correct
6 Correct 11 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
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8184 KB Output is correct
2 Correct 12 ms 8184 KB Output is correct
3 Correct 12 ms 8184 KB Output is correct
4 Correct 34 ms 8320 KB Output is correct
5 Correct 20 ms 8184 KB Output is correct
6 Correct 26 ms 8188 KB Output is correct
7 Correct 38 ms 8292 KB Output is correct
8 Correct 27 ms 8184 KB Output is correct
9 Correct 30 ms 8312 KB Output is correct
10 Correct 28 ms 8316 KB Output is correct
11 Correct 9343 ms 10032 KB Output is correct
12 Correct 38 ms 8312 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 9208 KB Output is correct
2 Correct 258 ms 9488 KB Output is correct
3 Correct 180 ms 9208 KB Output is correct
4 Correct 179 ms 9208 KB Output is correct
5 Correct 178 ms 9208 KB Output is correct
6 Correct 12 ms 8184 KB Output is correct
7 Correct 11 ms 8184 KB Output is correct
8 Correct 12 ms 8184 KB Output is correct
9 Correct 240 ms 9208 KB Output is correct
10 Correct 12 ms 8184 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 16700 KB Output is correct
2 Correct 1270 ms 16680 KB Output is correct
3 Correct 496 ms 16684 KB Output is correct
4 Execution timed out 20064 ms 17748 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 9208 KB Output is correct
2 Correct 264 ms 9396 KB Output is correct
3 Correct 185 ms 9208 KB Output is correct
4 Correct 178 ms 9208 KB Output is correct
5 Correct 178 ms 9208 KB Output is correct
6 Correct 493 ms 16696 KB Output is correct
7 Correct 1280 ms 16680 KB Output is correct
8 Correct 496 ms 16696 KB Output is correct
9 Execution timed out 20009 ms 17744 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 9204 KB Output is correct
2 Correct 260 ms 9492 KB Output is correct
3 Correct 179 ms 9208 KB Output is correct
4 Correct 179 ms 9208 KB Output is correct
5 Correct 179 ms 9208 KB Output is correct
6 Correct 501 ms 16760 KB Output is correct
7 Correct 1258 ms 16760 KB Output is correct
8 Correct 499 ms 16632 KB Output is correct
9 Execution timed out 20082 ms 17748 KB Time limit exceeded
10 Halted 0 ms 0 KB -