oj.uz

Submission #805469

# Submission time Handle Problem Language Result Execution time Memory
805469 2023-08-03T16:55:19 Z YassirSalama Wombats (IOI13_wombats) C++17
37 / 100
 20000 ms 18644 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXR=105;
const int MAXC=105;
#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 52 ms 13140 KB Output is correct
2 Correct 56 ms 13140 KB Output is correct
3 Correct 18322 ms 14744 KB Output is correct
4 Correct 52 ms 13140 KB Output is correct
5 Correct 52 ms 13096 KB Output is correct
6 Correct 0 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 980 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 15 ms 980 KB Output is correct
7 Correct 16 ms 980 KB Output is correct
8 Correct 14 ms 980 KB Output is correct
9 Correct 18 ms 980 KB Output is correct
10 Correct 17 ms 980 KB Output is correct
11 Correct 7666 ms 1936 KB Output is correct
12 Correct 17 ms 980 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 3128 KB Output is correct
2 Correct 174 ms 3284 KB Output is correct
3 Correct 139 ms 3156 KB Output is correct
4 Correct 124 ms 3156 KB Output is correct
5 Correct 123 ms 3224 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 0 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 166 ms 3284 KB Output is correct
10 Correct 1 ms 852 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 18096 KB Output is correct
2 Correct 803 ms 18104 KB Output is correct
3 Correct 322 ms 18096 KB Output is correct
4 Execution timed out 20061 ms 18644 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 3232 KB Output is correct
2 Correct 185 ms 3284 KB Output is correct
3 Correct 123 ms 3180 KB Output is correct
4 Correct 123 ms 3156 KB Output is correct
5 Correct 128 ms 3232 KB Output is correct
6 Correct 324 ms 18092 KB Output is correct
7 Correct 768 ms 18096 KB Output is correct
8 Correct 320 ms 18004 KB Output is correct
9 Execution timed out 20070 ms 18592 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 3156 KB Output is correct
2 Correct 176 ms 3284 KB Output is correct
3 Correct 134 ms 3156 KB Output is correct
4 Correct 124 ms 3156 KB Output is correct
5 Correct 125 ms 3156 KB Output is correct
6 Correct 323 ms 18092 KB Output is correct
7 Correct 785 ms 18100 KB Output is correct
8 Correct 332 ms 18084 KB Output is correct
9 Execution timed out 20101 ms 18484 KB Time limit exceeded
10 Halted 0 ms 0 KB -