oj.uz

Submission #125868

# Submission time Handle Problem Language Result Execution time Memory
125868 2019-07-06T13:18:50 Z MoNsTeR_CuBe Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 143196 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
 
#define int long long 

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;

#undef int
 
void init(int R, int C, int H[5000][200], int V[5000][200]) {
	#define int long long 
    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));
		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];
		}
	}
	#undef int
}
 
void changeH(int P, int Q, int W) {
	#define int long long 
    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;
		}
	}
	#undef int
	/*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) {
	#define int long long 
    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;
	}
	#undef int
	//Graph[P*col+Q][(P+1)*col+Q] = W;
}
 
int escape(int V1, int V2) {
	#define int long long 
    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] = 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];
	#undef int
}

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 20 ms 19832 KB Output is correct
2 Correct 20 ms 19960 KB Output is correct
3 Correct 93 ms 22520 KB Output is correct
4 Correct 20 ms 19960 KB Output is correct
5 Correct 20 ms 19960 KB Output is correct
6 Correct 17 ms 15992 KB Output is correct
7 Correct 17 ms 15992 KB Output is correct
8 Correct 17 ms 15992 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15992 KB Output is correct
2 Correct 18 ms 15992 KB Output is correct
3 Correct 17 ms 15996 KB Output is correct
4 Correct 41 ms 16120 KB Output is correct
5 Correct 27 ms 16124 KB Output is correct
6 Correct 29 ms 16120 KB Output is correct
7 Correct 44 ms 16120 KB Output is correct
8 Correct 34 ms 16120 KB Output is correct
9 Correct 36 ms 16248 KB Output is correct
10 Correct 34 ms 16120 KB Output is correct
11 Correct 9500 ms 18632 KB Output is correct
12 Correct 45 ms 16248 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 17400 KB Output is correct
2 Correct 291 ms 17664 KB Output is correct
3 Correct 194 ms 17440 KB Output is correct
4 Correct 195 ms 17528 KB Output is correct
5 Correct 193 ms 17400 KB Output is correct
6 Correct 18 ms 15992 KB Output is correct
7 Correct 17 ms 15992 KB Output is correct
8 Correct 17 ms 16012 KB Output is correct
9 Correct 262 ms 17668 KB Output is correct
10 Correct 20 ms 15992 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 24220 KB Output is correct
2 Correct 145 ms 24056 KB Output is correct
3 Correct 148 ms 24312 KB Output is correct
4 Correct 12562 ms 25740 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 17400 KB Output is correct
2 Correct 289 ms 17740 KB Output is correct
3 Correct 193 ms 17400 KB Output is correct
4 Correct 191 ms 17400 KB Output is correct
5 Correct 194 ms 17400 KB Output is correct
6 Correct 150 ms 24184 KB Output is correct
7 Correct 150 ms 24188 KB Output is correct
8 Correct 146 ms 24120 KB Output is correct
9 Correct 12593 ms 25684 KB Output is correct
10 Correct 20 ms 19848 KB Output is correct
11 Correct 20 ms 19960 KB Output is correct
12 Correct 91 ms 22648 KB Output is correct
13 Correct 20 ms 19960 KB Output is correct
14 Correct 20 ms 19960 KB Output is correct
15 Correct 17 ms 15992 KB Output is correct
16 Correct 17 ms 15996 KB Output is correct
17 Correct 17 ms 15992 KB Output is correct
18 Correct 40 ms 16120 KB Output is correct
19 Correct 26 ms 16172 KB Output is correct
20 Correct 28 ms 16120 KB Output is correct
21 Correct 44 ms 16136 KB Output is correct
22 Correct 37 ms 16120 KB Output is correct
23 Correct 37 ms 16248 KB Output is correct
24 Correct 34 ms 16120 KB Output is correct
25 Correct 9563 ms 18860 KB Output is correct
26 Correct 45 ms 16120 KB Output is correct
27 Correct 262 ms 17500 KB Output is correct
28 Execution timed out 20068 ms 82168 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 17400 KB Output is correct
2 Correct 293 ms 17740 KB Output is correct
3 Correct 194 ms 17400 KB Output is correct
4 Correct 197 ms 17400 KB Output is correct
5 Correct 193 ms 17372 KB Output is correct
6 Correct 151 ms 24184 KB Output is correct
7 Correct 147 ms 24224 KB Output is correct
8 Correct 151 ms 24196 KB Output is correct
9 Correct 12506 ms 25824 KB Output is correct
10 Correct 20 ms 19960 KB Output is correct
11 Correct 20 ms 19960 KB Output is correct
12 Correct 91 ms 22648 KB Output is correct
13 Correct 20 ms 19960 KB Output is correct
14 Correct 20 ms 19960 KB Output is correct
15 Correct 1816 ms 143196 KB Output is correct
16 Execution timed out 20022 ms 141320 KB Time limit exceeded
17 Halted 0 ms 0 KB -