#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXR=101;
const int MAXC=101;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
vector<set<pair<int,int>>> v(MAXR*MAXC);
map<pair<int,int>,int> mp;
int r,c;
int h[5000][200];
int vv[5000][200];
bool visited[MAXR*MAXC];
const ll INF=1e18;
vector<vector<ll>> dist2(MAXR*MAXC,vector<ll>(MAXR*MAXC,INF));
vector<ll> dijkstra(ll node){
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> q;
memset(visited,false,sizeof(visited));
vector<ll> dist(MAXR*MAXC,INF);
dist[node]=0;
q.push({0LL,node});
while(!q.empty()){
pair<ll,ll> p=q.top();
q.pop();
if(visited[p.S]) continue;
visited[p.S]=true;
for(auto x:v[p.S]){
// dbg(dist[p.S],p.S,x.F,dist[x.F]);
if(dist[x.F]>dist[p.S]+x.S){
dist[x.F]=dist[p.S]+x.S;
q.push({dist[x.F],x.F});
}
}
}
// OVL(dist," ")
return dist;
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
int a=0;
r=R,c=C;
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
h[i][j]=H[i][j];
mp[{i,j}]=a;
if(j==C-1) continue;
v[a].insert({a+1,H[i][j]});
v[a+1].insert({a,H[i][j]});
// cout<<H[i][j]<<" ";
a++;
}a++;
}
a=0;
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
vv[i][j]=V[i][j];
v[a].insert({a+C,V[i][j]});
a++;
}
}
for(int i=0;i<MAXR*MAXC;i++) {
for(int j=0;j<MAXR*MAXC;j++) dist2[i][j]=INF;
}
for(int i=0;i<c;i++){
vector<ll> dist=dijkstra(i);
for(int j=0;j<MAXR*MAXC;j++){
dist2[i][j]=min(dist2[i][j],dist[j]);
}
}
}
void changeH(int P, int Q, int W) {
int ind=mp[{P,Q}];
v[ind].erase({ind+1,h[P][Q]});
v[ind+1].erase({ind,h[P][Q]});
h[P][Q]=W;
v[ind].insert({ind+1,h[P][Q]});
v[ind+1].insert({ind,h[P][Q]});
for(int i=0;i<MAXR*MAXC;i++) {
for(int j=0;j<MAXR*MAXC;j++) dist2[i][j]=INF;
}
for(int i=0;i<c;i++){
vector<ll> dist=dijkstra(i);
for(int j=0;j<MAXR*MAXC;j++){
dist2[i][j]=min(dist2[i][j],dist[j]);
}
}
}
void changeV(int P, int Q, int W) {
int ind=mp[{P,Q}];
v[ind].erase({ind+c,vv[P][Q]});
vv[P][Q]=W;
v[ind].insert({ind+c,vv[P][Q]});
for(int i=0;i<MAXR*MAXC;i++) {
for(int j=0;j<MAXR*MAXC;j++) dist2[i][j]=INF;
}
for(int i=0;i<c;i++){
vector<ll> dist=dijkstra(i);
for(int j=0;j<MAXR*MAXC;j++){
dist2[i][j]=min(dist2[i][j],dist[j]);
}
}
}
int escape(int V1, int V2) {
priority_queue<pair<int,int>> q;
int ind=mp[{0,V1}];
int ind2=mp[{r-1,V2}];
return dist2[ind][ind2];
}
#ifdef IOI
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
static int H[5000][200];
static int V[5000][200];
int main() {
int R, C, E, P, Q, W, V1, V2, event, i, j;
int res;
FILE *f = fopen("wombats.in", "r");
if (!f)
fail("Failed to open input file.");
res = fscanf(f, "%d%d", &R, &C);
for (i = 0; i < R; ++i)
for (j = 0; j < C-1; ++j)
res = fscanf(f, "%d", &H[i][j]);
for (i = 0; i < R-1; ++i)
for (j = 0; j < C; ++j)
res = fscanf(f, "%d", &V[i][j]);
init(R, C, H, V);
res = fscanf(f, "%d", &E);
for (i = 0; i < E; i++) {
res = fscanf(f, "%d", &event);
if (event == 1) {
res = fscanf(f, "%d%d%d", &P, &Q, &W);
changeH(P, Q, W);
} else if (event == 2) {
res = fscanf(f, "%d%d%d", &P, &Q, &W);
changeV(P, Q, W);
} else if (event == 3) {
res = fscanf(f, "%d%d", &V1, &V2);
printf("%d\n", escape(V1, V2));
} else
fail("Invalid event type.");
}
fclose(f);
return 0;
}
#endif
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;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
100 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
108 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
120 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
98 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
101 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
116 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
