oj.uz

Submission #805463

# Submission time Handle Problem Language Result Execution time Memory
805463 2023-08-03T16:51:32 Z YassirSalama Wombats (IOI13_wombats) C++17
21 / 100
 18196 ms 36464 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXR=100;
const int MAXC=100;
#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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13140 KB Output is correct
2 Correct 53 ms 13140 KB Output is correct
3 Correct 18196 ms 15648 KB Output is correct
4 Correct 54 ms 13140 KB Output is correct
5 Correct 52 ms 13140 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 18 ms 928 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 11 ms 980 KB Output is correct
7 Correct 16 ms 932 KB Output is correct
8 Correct 13 ms 980 KB Output is correct
9 Correct 15 ms 980 KB Output is correct
10 Correct 14 ms 924 KB Output is correct
11 Correct 7437 ms 2412 KB Output is correct
12 Correct 18 ms 980 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 3208 KB Output is correct
2 Correct 173 ms 3284 KB Output is correct
3 Runtime error 8 ms 6240 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 18124 KB Output is correct
2 Runtime error 27 ms 36464 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 3156 KB Output is correct
2 Correct 175 ms 3328 KB Output is correct
3 Runtime error 10 ms 6356 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 3212 KB Output is correct
2 Correct 174 ms 3284 KB Output is correct
3 Runtime error 8 ms 6356 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -