Submission #125852

#	Time	Username	Problem	Language	Result	Execution time	Memory
125852		MoNsTeR_CuBe	Wombats (IOI13_wombats)	C++17	37 / 100	9017 ms	16892 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24