oj.uz

Submission #1022329

# Submission time Handle Problem Language Result Execution time Memory
1022329 2024-07-13T12:04:35 Z MarwenElarbi Wombats (IOI13_wombats) C++17
37 / 100
 20000 ms 33900 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
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,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:66: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]
   66 |     for (int i = 0; i < adj[convert(P,Q)].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:70: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]
   70 |     for (int i = 0; i < adj[convert(P,Q+1)].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:77: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]
   77 |     for (int i = 0; i < adj[convert(P,Q)].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'long long int djikastra(int, int)':
wombats.cpp:24:80: warning: control reaches end of non-void function [-Wreturn-type]
   24 |     priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
      |                                                                                ^~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 28636 KB Output is correct
2 Correct 64 ms 28508 KB Output is correct
3 Correct 16085 ms 30020 KB Output is correct
4 Correct 58 ms 28504 KB Output is correct
5 Correct 55 ms 28504 KB Output is correct
6 Correct 11 ms 24412 KB Output is correct
7 Correct 11 ms 24412 KB Output is correct
8 Correct 12 ms 24412 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24408 KB Output is correct
2 Correct 16 ms 24372 KB Output is correct
3 Correct 15 ms 24548 KB Output is correct
4 Correct 19 ms 24392 KB Output is correct
5 Correct 15 ms 24408 KB Output is correct
6 Correct 15 ms 24412 KB Output is correct
7 Correct 26 ms 24412 KB Output is correct
8 Correct 18 ms 24412 KB Output is correct
9 Correct 23 ms 24500 KB Output is correct
10 Correct 19 ms 24612 KB Output is correct
11 Correct 4504 ms 25520 KB Output is correct
12 Correct 21 ms 24408 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 25008 KB Output is correct
2 Correct 109 ms 25176 KB Output is correct
3 Correct 142 ms 25176 KB Output is correct
4 Correct 140 ms 25180 KB Output is correct
5 Correct 105 ms 25328 KB Output is correct
6 Correct 18 ms 24408 KB Output is correct
7 Correct 13 ms 24408 KB Output is correct
8 Correct 11 ms 24412 KB Output is correct
9 Correct 179 ms 25356 KB Output is correct
10 Correct 11 ms 24412 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 32600 KB Output is correct
2 Correct 664 ms 32768 KB Output is correct
3 Correct 305 ms 32740 KB Output is correct
4 Execution timed out 20014 ms 33140 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 25184 KB Output is correct
2 Correct 108 ms 25180 KB Output is correct
3 Correct 105 ms 25180 KB Output is correct
4 Correct 107 ms 25176 KB Output is correct
5 Correct 107 ms 25180 KB Output is correct
6 Correct 270 ms 32604 KB Output is correct
7 Correct 701 ms 32800 KB Output is correct
8 Correct 263 ms 32800 KB Output is correct
9 Execution timed out 20061 ms 33900 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 25420 KB Output is correct
2 Correct 114 ms 25416 KB Output is correct
3 Correct 107 ms 25348 KB Output is correct
4 Correct 134 ms 25340 KB Output is correct
5 Correct 103 ms 25180 KB Output is correct
6 Correct 261 ms 32604 KB Output is correct
7 Correct 705 ms 32796 KB Output is correct
8 Correct 270 ms 32680 KB Output is correct
9 Execution timed out 20032 ms 33876 KB Time limit exceeded
10 Halted 0 ms 0 KB -