oj.uz

Submission #1074111

# Submission time Handle Problem Language Result Execution time Memory
1074111 2024-08-25T08:03:11 Z Malix Wombats (IOI13_wombats) C++14
37 / 100
 20000 ms 18204 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

#define REP(a,b,c) for(int a=b;a<c;a++)
#define F first
#define S second
#define PB push_back

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;

int inf=1000000010;

vii a(5000,vi(200,0)),b(5000,vi(200,0));
int n,m;
vi dist;
vector<vector<pi>> arr;

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n=R;
    m=C;
    REP(i,0,5000)REP(j,0,200)a[i][j]=H[i][j];
    REP(i,0,5000)REP(j,0,200)b[i][j]=V[i][j];
    arr.resize(n*m+2);
    REP(i,0,n*m){
        if((i+1)%m!=0)arr[i].PB({i+1,a[i/m][i%m]});
        if(i+m<n*m+1)arr[i].PB({i+m,b[i/m][i%m]});
        if(i%m!=0)arr[i].PB({i-1,a[(i-1)/m][(i-1)%m]});
    }
}

void changeH(int P, int Q, int W) {
    a[P][Q]=W;
    int i=P*m+Q;
    arr[i].clear();
    if((i+1)%m!=0)arr[i].PB({i+1,a[i/m][i%m]});
    if(i+m<n*m+1)arr[i].PB({i+m,b[i/m][i%m]});
    if(i%m!=0)arr[i].PB({i-1,a[(i-1)/m][(i-1)%m]});
    i++;
    arr[i].clear();
    if((i+1)%m!=0)arr[i].PB({i+1,a[i/m][i%m]});
    if(i+m<n*m+1)arr[i].PB({i+m,b[i/m][i%m]});
    if(i%m!=0)arr[i].PB({i-1,a[(i-1)/m][(i-1)%m]});
}

void changeV(int P, int Q, int W) {
    b[P][Q]=W;
    int i=P*m+Q;
    arr[i].clear();
    if((i+1)%m!=0)arr[i].PB({i+1,a[i/m][i%m]});
    if(i+m<n*m+1)arr[i].PB({i+m,b[i/m][i%m]});
    if(i%m!=0)arr[i].PB({i-1,a[(i-1)/m][(i-1)%m]});
}

int escape(int V1, int V2) {
if(m==1){
    int ans=0;
    REP(i,0,n)REP(j,0,m)ans+=b[i][j];
    return ans;
}   
    dist.clear();
    dist.resize(n*m+2,inf);
    dist[V1]=0;
    priority_queue<pi,vector<pi>,greater<pi>> pq;
    pq.push({0,V1});
    while(!pq.empty()){
        int x=pq.top().F;
        int y=pq.top().S;
        pq.pop();
        if(x!=dist[y])continue;
        for(auto u:arr[y])if(dist[u.F]>x+u.S){
            dist[u.F]=x+u.S;
            pq.push({dist[u.F],u.F});
        }
    }
    return dist[(n-1)*m+V2];
}

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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12832 KB Output is correct
2 Correct 16 ms 12636 KB Output is correct
3 Correct 1207 ms 14420 KB Output is correct
4 Correct 15 ms 13148 KB Output is correct
5 Correct 16 ms 13208 KB Output is correct
6 Correct 11 ms 8668 KB Output is correct
7 Correct 9 ms 8540 KB Output is correct
8 Correct 10 ms 8520 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8540 KB Output is correct
2 Correct 12 ms 8540 KB Output is correct
3 Correct 9 ms 8536 KB Output is correct
4 Correct 18 ms 8540 KB Output is correct
5 Correct 13 ms 8540 KB Output is correct
6 Correct 13 ms 8536 KB Output is correct
7 Correct 18 ms 8744 KB Output is correct
8 Correct 18 ms 8540 KB Output is correct
9 Correct 20 ms 8536 KB Output is correct
10 Correct 18 ms 8648 KB Output is correct
11 Correct 4922 ms 9544 KB Output is correct
12 Correct 26 ms 8792 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 9564 KB Output is correct
2 Correct 158 ms 11612 KB Output is correct
3 Correct 113 ms 11352 KB Output is correct
4 Correct 136 ms 11352 KB Output is correct
5 Correct 126 ms 11356 KB Output is correct
6 Correct 10 ms 8536 KB Output is correct
7 Correct 12 ms 8448 KB Output is correct
8 Correct 13 ms 8540 KB Output is correct
9 Correct 151 ms 11352 KB Output is correct
10 Correct 12 ms 10584 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 17060 KB Output is correct
2 Correct 715 ms 16988 KB Output is correct
3 Correct 275 ms 16988 KB Output is correct
4 Execution timed out 20079 ms 17580 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 11356 KB Output is correct
2 Correct 159 ms 11608 KB Output is correct
3 Correct 108 ms 11556 KB Output is correct
4 Correct 107 ms 11352 KB Output is correct
5 Correct 108 ms 11356 KB Output is correct
6 Correct 259 ms 16984 KB Output is correct
7 Correct 718 ms 17076 KB Output is correct
8 Correct 261 ms 17060 KB Output is correct
9 Execution timed out 20084 ms 17636 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 11352 KB Output is correct
2 Correct 172 ms 11612 KB Output is correct
3 Correct 109 ms 11356 KB Output is correct
4 Correct 109 ms 11356 KB Output is correct
5 Correct 110 ms 11356 KB Output is correct
6 Correct 252 ms 16860 KB Output is correct
7 Correct 725 ms 16988 KB Output is correct
8 Correct 264 ms 16984 KB Output is correct
9 Execution timed out 20061 ms 18204 KB Time limit exceeded
10 Halted 0 ms 0 KB -