oj.uz

Submission #1022315

# Submission time Handle Problem Language Result Execution time Memory
1022315 2024-07-13T12:00:58 Z MarwenElarbi Wombats (IOI13_wombats) C++17
12 / 100
 4311 ms 57680 KB 
#include <bits/stdc++.h>
#include"wombats.h"
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
const int nax=1e5+5;
vector<pair<int,int>> adj[5005*205];
int r,c;
int convert(int x,int y){
    return x*c+y;
}
long long dis[5005*205];
long long djikastra(int x,int y){
    x=convert(0,x);
    y=convert(r-1,y);
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            dis[convert(i,j)]=1e18;
        }
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,x});
    dis[x]=0;
    while(!pq.empty()){
        int node=pq.top().se;
        long long d=pq.top().fi;
        pq.pop();
        if(node==y) return d;
        if(d>dis[node]) continue;
        for(auto u:adj[node]){
            long long newd=d+u.se;
            if(newd>=dis[u.fi]) continue;
            dis[u.fi]=newd;
            pq.push({newd,u.fi});
        }
    }
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r=R;
    c=C;
    for (int i = 0; i < R; ++i)
    {
        for (int j = 0; j < C-1; ++j)
        {
            int x=convert(i,j);
            int y=convert(i,j+1);
            adj[x].pb({y,H[i][j]});
            adj[y].pb({x,H[i][j]});
        }
    }
    for (int i = 0; i < R-1; ++i)
    {
        for (int j = 0; j < C; ++j)
        {
            int x=convert(i,j);
            int y=convert(i+1,j);
            adj[x].pb({y,V[i][j]});
        }
    }
    return;
}
void changeH(int P, int Q, int W) {
    for (int i = 0; i < adj[convert(P,Q)].size(); ++i)
    {
        if(adj[convert(P,Q)][i].fi==convert(P,Q+1)) adj[convert(P,Q)][i].se=W;
    }
    for (int i = 0; i < adj[convert(P,Q+1)].size(); ++i)
    {
        if(adj[convert(P,Q+1)][i].fi==convert(P,Q)) adj[convert(P,Q+1)][i].se=W;
    }
}

void changeV(int P, int Q, int W) {
    for (int i = 0; i < adj[convert(P,Q)].size(); ++i)
    {
        if(adj[convert(P,Q)][i].fi==convert(P+1,Q)) adj[convert(P+1,Q)][i].se=W;
    }
}

int escape(int V1, int V2) {
    return djikastra(V1,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;
      |      ^~~
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < adj[convert(P,Q)].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < adj[convert(P,Q+1)].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0; i < adj[convert(P,Q)].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'long long int djikastra(int, int)':
wombats.cpp:25:80: warning: control reaches end of non-void function [-Wreturn-type]
   25 |     priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
      |                                                                                ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 28508 KB Output is correct
2 Runtime error 69 ms 57680 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24412 KB Output is correct
2 Correct 17 ms 24412 KB Output is correct
3 Correct 11 ms 24412 KB Output is correct
4 Correct 17 ms 24628 KB Output is correct
5 Correct 22 ms 24408 KB Output is correct
6 Correct 19 ms 24412 KB Output is correct
7 Correct 18 ms 24408 KB Output is correct
8 Correct 19 ms 24412 KB Output is correct
9 Correct 20 ms 24412 KB Output is correct
10 Correct 28 ms 24412 KB Output is correct
11 Correct 4311 ms 26620 KB Output is correct
12 Correct 30 ms 24408 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 25180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 32600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 25180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 25176 KB Output isn't correct
2 Halted 0 ms 0 KB -