| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 29638 |
2017-07-20T09:44:44 Z |
Nikefor |
Wombats (IOI13_wombats) |
C++ |
|
1206 ms |
262144 KB |
#include "wombats.h"
#include<bits/stdc++.h>
#define inf 1<<22
#define ii pair<int,int>
using namespace std;
int subtask;
int sum;
int ho, ve;
long dis[402][402];
int dp[1001][2][1001][2];
vector<ii> adj[10001];
int HG[5000][200];
int VG[5000][200];
int toone(int h, int v) { return (h*ho + v); }
int dijkstra(int V1, int V2) {
priority_queue<ii, vector<ii>, greater<ii> > q;
q.push(make_pair(0,toone(ho-1,V2)));
bool visit[10002];
for(int i=0; i<10002;i++) visit[i] = false;
int tar = toone(0,V1);
while(!q.empty()) {
ii ne = q.top();
q.pop();
int v = ne.second;
visit[v] = true;
if(v==tar) return ne.first;
for(int i=0; i<adj[v].size(); i++) {
int go = adj[v][i].second;
if(!visit[go]) q.push( make_pair((ne.first+adj[v][i].first),go) );
}
}
}
int f(int sh,int sv,int fh,int fv ) {
if(sh>1000 or fh>1000) return min( f(sh+1,sv, fh, fv)+VG[sh][sv], f(sh, (sv+1)%2, fh, fv )+HG[sh][0]);
if(dp[sh][sv][fh][fv]) return dp[sh][sv][fh][fv];
if(sh==fh and sv==fv) return 0;
if(sh==fh and sv!=fv) dp[sh][sv][fh][fv] = HG[sh][0];
else dp[sh][sv][fh][fv] = min( f(sh+1,sv, fh, fv)+VG[sh][sv], f(sh, (sv+1)%2, fh, fv )+HG[sh][0]);
return dp[sh][sv][fh][fv];
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
for(int i=0; i<5000; i++)
for(int j=0; j<200; j++) {
HG[i][j] = H[i][j];
VG[i][j] = V[i][j];
}
if(C==1) {
subtask=1;
// printf("birinci subtask\n");
for(int i=0; i<R-1; i++) sum+= V[i][0];
}
else if(C==2) subtask = 4;
else if(R<=20 and C<=20) {
subtask = 2;
ho = R;
ve = C;
for(int i=0 ; i<(R*C); i++)
for(int j=0; j<(R*C); j++) dis[i][j] = (i==j)?0:inf;
for(int i=0; i<R; i++)
for(int j=0; j<C-1; j++) dis[toone(i,j)][toone(i, j+1)] = dis[toone(i,j+1)][toone(i,j)] = H[i][j];
for(int i=0; i<R-1; i++)
for(int j=0; j<C; j++) dis[toone(i,j)][toone(i+1,j)] = dis[toone(i+1,j)][toone(i,j)];
for(int i=0; i<(R*C); i++)
for(int j=0; j<(R*C); j++)
for(int k=0; k<(R*C); k++) if((dis[i][j]+dis[j][k]) < dis[i][k]) dis[i][k] = dis[i][j]+dis[j][k];
}
else {
subtask = 3;
for(int i=0; i<R; i++)
for(int j=0; j<C-1; j++) {
int v1 = toone(i,j), v2=toone(i,j+1);
adj[v1].push_back(make_pair(H[i][j],v2));
adj[v2].push_back(make_pair(H[i][j], v1));
}
for(int i=0; i<R-1; i++)
for(int j=0; j<C; j++) {
int v1= toone(i,j), v2 = toone(i+1,j);
adj[v1].push_back(make_pair(V[i][j], v2));
adj[v2].push_back(make_pair(V[i][j], v1));
}
}
}
void changeH(int P, int Q, int W) {
if(subtask==3) {
int v1 = toone(P,Q), v2 = toone(P,Q+1);
for(int i=0; i<adj[v1].size();i++) if(adj[v1][i].second==v2) adj[v1][i].first = W;
for(int i=0; i<adj[v2].size();i++) if(adj[v2][i].second==v1) adj[v2][i].first = W;
}
}
void changeV(int P, int Q, int W) {
if(subtask==1) {
sum+= (W-VG[P][Q]);
VG[P][Q] = W;
}
if(subtask==3) {
int v1 = toone(P,Q), v2 = toone(P+1,Q);
for(int i=0; i<adj[v1].size();i++) if(adj[v1][i].second==v2) adj[v1][i].first = W;
for(int i=0; i<adj[v2].size();i++) if(adj[v2][i].second==v1) adj[v2][i].first = W;
}
}
int escape(int V1, int V2) {
if(subtask==1) return sum;
if(subtask==2) return dis[toone(0,V1)][toone(ho-1,V2)];
if(subtask==3) return dijkstra(V1,V2);
if(subtask==4) return f(0, V1, ho-1, V2);
return 42;
}
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;
^
wombats.cpp: In function 'int dijkstra(int, int)':
wombats.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<adj[v].size(); i++) {
^
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:100:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<adj[v1].size();i++) if(adj[v1][i].second==v2) adj[v1][i].first = W;
^
wombats.cpp:101:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<adj[v2].size();i++) if(adj[v2][i].second==v1) adj[v2][i].first = W;
^
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:113:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<adj[v1].size();i++) if(adj[v1][i].second==v2) adj[v1][i].first = W;
^
wombats.cpp:114:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<adj[v2].size();i++) if(adj[v2][i].second==v1) adj[v2][i].first = W;
^
wombats.cpp: In function 'int dijkstra(int, int)':
wombats.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
34800 KB |
Output is correct |
| 2 |
Correct |
6 ms |
34800 KB |
Output is correct |
| 3 |
Correct |
69 ms |
34800 KB |
Output is correct |
| 4 |
Correct |
3 ms |
34800 KB |
Output is correct |
| 5 |
Correct |
0 ms |
34800 KB |
Output is correct |
| 6 |
Correct |
3 ms |
34800 KB |
Output is correct |
| 7 |
Correct |
0 ms |
34800 KB |
Output is correct |
| 8 |
Correct |
0 ms |
34800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
34800 KB |
Output is correct |
| 2 |
Correct |
6 ms |
34800 KB |
Output is correct |
| 3 |
Correct |
6 ms |
34800 KB |
Output is correct |
| 4 |
Incorrect |
113 ms |
34800 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
1206 ms |
262144 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
43 ms |
262144 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
936 ms |
262144 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
963 ms |
262144 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
