제출 #29621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29621		Nikefor	웜뱃 (IOI13_wombats)	C++98	0 / 100	856 ms	262144 KiB

wombats

#include "wombats.h"
#include<bits/stdc++.h>
#define inf 1<<22
#define ii pair<int,int>
using namespace std;
int subtask;
long 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;
        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]);
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

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:98: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:99: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:108: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:109: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]
 }
 ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24