oj.uz

답안 #805465

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
805465 2023-08-03T16:53:28 Z YassirSalama 웜뱃 (IOI13_wombats) C++17
28 / 100
 20000 ms 20764 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXR=200;
const int MAXC=200;
#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];
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<a;i++){
        // cout<<i<<" --> ";
        // for(auto x:v[i]) cout<<" [ "<<x.F<<" : "<<x.S<<" ] ,";
        // cout<<endl;
    // }
}

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]});
    // dbg(ind);
}

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]});
    // dbg(ind);
}

bool visited[MAXR*MAXC];
int dist[MAXR*MAXC];
int escape(int V1, int V2) {
    priority_queue<pair<int,int>> q;
    int ind=mp[{0,V1}];
    int ind2=mp[{r-1,V2}];
    memset(visited,false,sizeof(visited));
    q.push({0,ind});
    const int INF=1e9;
    for(int i=0;i<sizeof(dist)/sizeof(int);i++) dist[i]=INF;
    dist[ind]=0;
    while(!q.empty()){
        pair<int,int> p=q.top();
        q.pop();
        if(visited[p.S]) continue;
        visited[p.S]=true;
        for(auto x:v[p.S]){
            if(dist[x.F]>dist[p.S]+x.S){
                dist[x.F]=dist[p.S]+x.S;
                q.push({-dist[x.F],x.F});
            }
        }
    }
    return dist[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;
      |      ^~~
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   79 |     for(int i=0;i<sizeof(dist)/sizeof(int);i++) dist[i]=INF;
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 14676 KB Output is correct
2 Correct 56 ms 14676 KB Output is correct
3 Execution timed out 20076 ms 16156 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 1 ms 2388 KB Output is correct
3 Correct 1 ms 2388 KB Output is correct
4 Correct 22 ms 2516 KB Output is correct
5 Correct 11 ms 2516 KB Output is correct
6 Correct 15 ms 2516 KB Output is correct
7 Correct 20 ms 2516 KB Output is correct
8 Correct 17 ms 2516 KB Output is correct
9 Correct 19 ms 2516 KB Output is correct
10 Correct 20 ms 2516 KB Output is correct
11 Correct 9842 ms 3532 KB Output is correct
12 Correct 28 ms 2516 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 4692 KB Output is correct
2 Correct 185 ms 4820 KB Output is correct
3 Correct 143 ms 4692 KB Output is correct
4 Correct 149 ms 4768 KB Output is correct
5 Correct 126 ms 4820 KB Output is correct
6 Correct 1 ms 2388 KB Output is correct
7 Correct 1 ms 2324 KB Output is correct
8 Correct 1 ms 2388 KB Output is correct
9 Correct 170 ms 4772 KB Output is correct
10 Correct 1 ms 2324 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 347 ms 19608 KB Output is correct
2 Correct 792 ms 19600 KB Output is correct
3 Correct 331 ms 19668 KB Output is correct
4 Execution timed out 20033 ms 20764 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 4692 KB Output is correct
2 Correct 175 ms 4820 KB Output is correct
3 Correct 132 ms 4692 KB Output is correct
4 Correct 127 ms 4820 KB Output is correct
5 Correct 126 ms 4724 KB Output is correct
6 Correct 361 ms 19660 KB Output is correct
7 Correct 773 ms 19676 KB Output is correct
8 Correct 335 ms 19668 KB Output is correct
9 Execution timed out 20041 ms 20652 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 4692 KB Output is correct
2 Correct 174 ms 4820 KB Output is correct
3 Correct 130 ms 4692 KB Output is correct
4 Correct 131 ms 4820 KB Output is correct
5 Correct 136 ms 4820 KB Output is correct
6 Correct 331 ms 19668 KB Output is correct
7 Correct 795 ms 19668 KB Output is correct
8 Correct 365 ms 19668 KB Output is correct
9 Execution timed out 20074 ms 20692 KB Time limit exceeded
10 Halted 0 ms 0 KB -