oj.uz

Submission #125852

# Submission time Handle Problem Language Result Execution time Memory
125852 2019-07-06T13:07:47 Z MoNsTeR_CuBe Wombats (IOI13_wombats) C++17
37 / 100
 9017 ms 16892 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;
 
vector< vector< int > > dp;
 
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;
	}
    
    if(C == 2){
		dp.resize(R, vector< int > (2));
	}
    
    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 || col == 2){
		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 || col == 2){
		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;
	}
	if(col == 2){
		dp.assign(row, vector< int > (col,INF));
		dp[0][V1] = 0;
		
		for(int i = 0; i < row; i++){
			for(int j = 0; j < col; j++){
				if(i){
					dp[i][j] = min(dp[i][j], dp[i-1][j] + v[i-1][j]);
				}
			}
			dp[i][0] = min(dp[i][0], dp[i][1] + h[i][0]);
			dp[i][1] = min(dp[i][1], dp[i][0] + h[i][0]);
		}
		
		return dp[row-1][V2];
	}
	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 12024 KB Output is correct
2 Correct 14 ms 12024 KB Output is correct
3 Correct 84 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 12 ms 8312 KB Output is correct
7 Correct 12 ms 8184 KB Output is correct
8 Correct 11 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 11 ms 8184 KB Output is correct
4 Correct 36 ms 8312 KB Output is correct
5 Correct 20 ms 8316 KB Output is correct
6 Correct 22 ms 8184 KB Output is correct
7 Correct 41 ms 8312 KB Output is correct
8 Correct 27 ms 8184 KB Output is correct
9 Correct 29 ms 8312 KB Output is correct
10 Correct 28 ms 8312 KB Output is correct
11 Correct 9017 ms 9200 KB Output is correct
12 Correct 37 ms 8188 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 9080 KB Output is correct
2 Correct 258 ms 9308 KB Output is correct
3 Correct 176 ms 9080 KB Output is correct
4 Correct 175 ms 9080 KB Output is correct
5 Correct 174 ms 9080 KB Output is correct
6 Correct 12 ms 8184 KB Output is correct
7 Correct 11 ms 8184 KB Output is correct
8 Correct 11 ms 8184 KB Output is correct
9 Correct 238 ms 9080 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 Incorrect 140 ms 16892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 9080 KB Output is correct
2 Correct 257 ms 9352 KB Output is correct
3 Correct 179 ms 9052 KB Output is correct
4 Correct 177 ms 9132 KB Output is correct
5 Correct 178 ms 9056 KB Output is correct
6 Incorrect 143 ms 16764 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 9056 KB Output is correct
2 Correct 257 ms 9308 KB Output is correct
3 Correct 176 ms 9080 KB Output is correct
4 Correct 174 ms 9080 KB Output is correct
5 Correct 177 ms 9104 KB Output is correct
6 Incorrect 141 ms 16888 KB Output isn't correct
7 Halted 0 ms 0 KB -