oj.uz

Submission #805444

# Submission time Handle Problem Language Result Execution time Memory
805444 2023-08-03T16:42:26 Z YassirSalama Wombats (IOI13_wombats) C++17
12 / 100
 6221 ms 16760 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXR=50;
const int MAXC=40;
#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<vector<pair<int,int>>> v(MAXR*MAXC);
map<pair<int,int>,int> mp;
int r,c;
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++){
            mp[{i,j}]=a;
            if(j==C-1) continue;
            v[a].push_back({a+1,H[i][j]});
            v[a+1].push_back({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++){
            v[a].push_back({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) {
    /* ... */
}

void changeV(int P, int Q, int W) {
    /* ... */
}

int escape(int V1, int V2) {
    priority_queue<pair<int,int>> q;
    int ind=mp[{0,V1}];
    int ind2=mp[{r-1,V2}];
    bool visited[MAXR*MAXC];
    memset(visited,false,sizeof(visited));
    q.push({0,ind});
    int dist[MAXR*MAXC];
    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:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   64 |     for(int i=0;i<sizeof(dist)/sizeof(int);i++) dist[i]=INF;
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 9208 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 15 ms 452 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 9 ms 464 KB Output is correct
7 Correct 13 ms 340 KB Output is correct
8 Correct 11 ms 456 KB Output is correct
9 Correct 15 ms 464 KB Output is correct
10 Correct 12 ms 360 KB Output is correct
11 Correct 6221 ms 2016 KB Output is correct
12 Correct 16 ms 340 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 16760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -