oj.uz

답안 #358354

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
358354 2021-01-25T11:22:19 Z amunduzbaev 웜뱃 (IOI13_wombats) C++14
37 / 100
 20000 ms 73288 KB 
#include "wombats.h"

#ifndef EVAL
#include "grader.cpp"
#endif 

#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define ff first
#define ss second

const int N = 5e3+5;

vector<pair<int, int>> edges[N*200];
int n, m;

int h[N][N], v[N][N];

#define ll long long

ll sum = 0;

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R, m = C;
    for(int i=0;i<n-1;i++){
		for(int j=0;j<m;j++) v[i][j] = V[i][j], sum += v[i][j];
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m-1;j++) h[i][j] = H[i][j];
	}
	
	for(int i=0;i<n-1;i++){
		for(int j=0;j<m;j++){
			edges[i * m + j].pb({(i+1) * m + j, v[i][j]});
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m-1;j++){
			edges[i * m + j].pb({i * m + j + 1, h[i][j]});
			edges[i * m + j + 1].pb({i * m + j, h[i][j]});
		}
	}
}


void changeH(int p, int q, int w) {
	
    for(auto &x:edges[p*m+q]){
		if(x.ff == p*m+q+1) x.ss = w;
	}
	for(auto &x:edges[p*m+q+1]){
		if(x.ff == p*m+q) x.ss = w;
	}
}

void changeV(int p, int q, int w) {
    sum -= v[p][q];
	sum += w;
	v[p][q] = w;
	for(auto &x:edges[p*m+q]){
		if(x.ff == (p+1)*m+q){
			x.ss = w;
		}
	}
}

const ll mod = 1e18+7;

int escape(int V1, int V2) {
	
	if(m == 1) return sum;
	
    priority_queue<pair<int, int>> qq;
	qq.push({0, V1});
	vector<ll> dis(n*m, mod);
	dis[V1] = 0;
	
	while(!qq.empty()){
		int cur = qq.top().ss, dd = qq.top().ff; qq.pop();
		if(dd > dis[cur]) continue;
		for(auto x:edges[cur]){
			if(dis[x.ff] > dis[cur] + x.ss){
				dis[x.ff] = dis[cur] + x.ss;
				qq.push({-dis[x.ff], x.ff});
			}
		}
	}
	
	return dis[m * (n-1) + V2];
}

/*

3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1

*/

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 48108 KB Output is correct
2 Correct 30 ms 48108 KB Output is correct
3 Correct 109 ms 49936 KB Output is correct
4 Correct 31 ms 48108 KB Output is correct
5 Correct 31 ms 48108 KB Output is correct
6 Correct 18 ms 23788 KB Output is correct
7 Correct 17 ms 23788 KB Output is correct
8 Correct 18 ms 23788 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 17 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Correct 34 ms 24044 KB Output is correct
5 Correct 25 ms 24044 KB Output is correct
6 Correct 26 ms 24044 KB Output is correct
7 Correct 40 ms 24044 KB Output is correct
8 Correct 31 ms 24044 KB Output is correct
9 Correct 33 ms 24044 KB Output is correct
10 Correct 31 ms 24172 KB Output is correct
11 Correct 8342 ms 25344 KB Output is correct
12 Correct 40 ms 24172 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 25452 KB Output is correct
2 Correct 227 ms 25644 KB Output is correct
3 Correct 168 ms 25708 KB Output is correct
4 Correct 166 ms 25580 KB Output is correct
5 Correct 164 ms 25580 KB Output is correct
6 Correct 17 ms 23788 KB Output is correct
7 Correct 17 ms 23788 KB Output is correct
8 Correct 17 ms 23776 KB Output is correct
9 Correct 227 ms 25708 KB Output is correct
10 Correct 17 ms 24064 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 495 ms 72684 KB Output is correct
2 Correct 1119 ms 72812 KB Output is correct
3 Correct 490 ms 72684 KB Output is correct
4 Execution timed out 20036 ms 73216 KB Time limit exceeded

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 25452 KB Output is correct
2 Correct 236 ms 25688 KB Output is correct
3 Correct 171 ms 25580 KB Output is correct
4 Correct 164 ms 25580 KB Output is correct
5 Correct 169 ms 25580 KB Output is correct
6 Correct 495 ms 72556 KB Output is correct
7 Correct 1122 ms 72628 KB Output is correct
8 Correct 497 ms 72556 KB Output is correct
9 Execution timed out 20024 ms 73288 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 25452 KB Output is correct
2 Correct 232 ms 25760 KB Output is correct
3 Correct 176 ms 25584 KB Output is correct
4 Correct 167 ms 25580 KB Output is correct
5 Correct 162 ms 25452 KB Output is correct
6 Correct 490 ms 72632 KB Output is correct
7 Correct 1124 ms 72656 KB Output is correct
8 Correct 494 ms 72556 KB Output is correct
9 Execution timed out 20055 ms 73084 KB Time limit exceeded
10 Halted 0 ms 0 KB -