Submission #29638

# Submission time Handle Problem Language Result Execution time Memory
29638 2017-07-20T09:44:44 Z Nikefor Wombats (IOI13_wombats) C++
9 / 100
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 -