oj.uz

Submission #1022332

# Submission time Handle Problem Language Result Execution time Memory
1022332 2024-07-13T12:05:39 Z MarwenElarbi Wombats (IOI13_wombats) C++17
37 / 100
 20000 ms 33952 KB 
#include <bits/stdc++.h>
#include"wombats.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
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:68: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]
   68 |     for (int i = 0; i < adj[convert(P,Q)].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:72: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]
   72 |     for (int i = 0; i < adj[convert(P,Q+1)].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:79: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]
   79 |     for (int i = 0; i < adj[convert(P,Q)].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'long long int djikastra(int, int)':
wombats.cpp:26:80: warning: control reaches end of non-void function [-Wreturn-type]
   26 |     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 56 ms 28628 KB Output is correct
2 Correct 65 ms 28504 KB Output is correct
3 Correct 16624 ms 31048 KB Output is correct
4 Correct 54 ms 28504 KB Output is correct
5 Correct 66 ms 28656 KB Output is correct
6 Correct 16 ms 24412 KB Output is correct
7 Correct 10 ms 24408 KB Output is correct
8 Correct 11 ms 24408 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24412 KB Output is correct
2 Correct 14 ms 24408 KB Output is correct
3 Correct 16 ms 24408 KB Output is correct
4 Correct 27 ms 24408 KB Output is correct
5 Correct 16 ms 24412 KB Output is correct
6 Correct 22 ms 24564 KB Output is correct
7 Correct 19 ms 24412 KB Output is correct
8 Correct 26 ms 24408 KB Output is correct
9 Correct 19 ms 24412 KB Output is correct
10 Correct 19 ms 24408 KB Output is correct
11 Correct 4415 ms 26384 KB Output is correct
12 Correct 20 ms 24620 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 25176 KB Output is correct
2 Correct 109 ms 25432 KB Output is correct
3 Correct 125 ms 25180 KB Output is correct
4 Correct 127 ms 25176 KB Output is correct
5 Correct 115 ms 25176 KB Output is correct
6 Correct 16 ms 24540 KB Output is correct
7 Correct 13 ms 24412 KB Output is correct
8 Correct 13 ms 24412 KB Output is correct
9 Correct 150 ms 25280 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 274 ms 32680 KB Output is correct
2 Correct 681 ms 32800 KB Output is correct
3 Correct 269 ms 32604 KB Output is correct
4 Execution timed out 20086 ms 33796 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 25180 KB Output is correct
2 Correct 115 ms 25180 KB Output is correct
3 Correct 115 ms 25348 KB Output is correct
4 Correct 111 ms 25344 KB Output is correct
5 Correct 121 ms 25180 KB Output is correct
6 Correct 289 ms 32604 KB Output is correct
7 Correct 725 ms 32800 KB Output is correct
8 Correct 272 ms 32600 KB Output is correct
9 Execution timed out 20048 ms 33868 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 25176 KB Output is correct
2 Correct 109 ms 25436 KB Output is correct
3 Correct 113 ms 25180 KB Output is correct
4 Correct 109 ms 25180 KB Output is correct
5 Correct 110 ms 25340 KB Output is correct
6 Correct 275 ms 32816 KB Output is correct
7 Correct 685 ms 32600 KB Output is correct
8 Correct 301 ms 32808 KB Output is correct
9 Execution timed out 20061 ms 33952 KB Time limit exceeded
10 Halted 0 ms 0 KB -