oj.uz

Submission #367168

# Submission time Handle Problem Language Result Execution time Memory
367168 2021-02-16T12:11:00 Z idk321 Wombats (IOI13_wombats) C++11
55 / 100
 20000 ms 101048 KB 
#include "wombats.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MA = 1000000000;
const int N = 5005;
const int M = 205;
const int NM = 1026025;
int n;
int m;
int h[N][M];
int v[N][M];
int between[M][M];
vector<array<int, 2>> adj[NM];

void makeGraph()
{
    for (int i = 0; i < n * m; i++)
    {
        adj[i].clear();
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (i != n - 1)
            {
                adj[i * m + j].push_back({(i + 1) * m + j, v[i][j]});
            }
            if (j != m - 1)
            {
                adj[i * m + j].push_back({i * m + j + 1, h[i][j]});
                adj[i * m + j + 1].push_back({i * m + j, h[i][j]});
            }
        }
    }
}

void djikstra(int node)
{
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    vector<int> dist(n * m, MA);
    pq.push({0, node});

    while(!pq.empty())
    {
        auto cur = pq.top();
        pq.pop();
        int cnode = cur[1];
        int cdist = cur[0];
        if (dist[cnode] != MA) continue;
        //cout << cnode / m << " " << " " << cnode % m << " "<< cdist << " " << adj[cnode].size()<< endl;
        dist[cnode] = cdist;
        for (auto next : adj[cnode])
        {
            //if (cnode == 0) cout << next[0] << " " << dist[next[0]] << endl;
            if (dist[next[0]] != MA) continue;
            pq.push({next[1] + cdist, next[0]});

        }
    }

    for (int j = 0; j < m; j++)
    {
        between[node][j] = dist[(n - 1) * m + j];
    }
    //for (int i = 0; i < m; i++) cout << node << " " << between[node][i] << endl;
}

void build()
{
    makeGraph();
    for (int i = 0; i < m; i++) djikstra(i);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R;
    m = C;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            h[i][j] = H[i][j];
            v[i][j] = V[i][j];
        }
    }
    if (m <= 20) build();
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    if (m <= 20) build();
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    if (m <= 20) build();
}

int escape(int V1, int V2) {
    if (m > 20)
    {
        makeGraph();
        djikstra(V1);
    }

    return between[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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 36716 KB Output is correct
2 Correct 125 ms 36588 KB Output is correct
3 Correct 199 ms 39404 KB Output is correct
4 Correct 120 ms 36588 KB Output is correct
5 Correct 121 ms 36588 KB Output is correct
6 Correct 18 ms 24428 KB Output is correct
7 Correct 17 ms 24428 KB Output is correct
8 Correct 17 ms 24428 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24428 KB Output is correct
2 Correct 17 ms 24428 KB Output is correct
3 Correct 18 ms 24428 KB Output is correct
4 Correct 19 ms 24556 KB Output is correct
5 Correct 18 ms 24556 KB Output is correct
6 Correct 19 ms 24556 KB Output is correct
7 Correct 21 ms 24556 KB Output is correct
8 Correct 19 ms 24556 KB Output is correct
9 Correct 18 ms 24556 KB Output is correct
10 Correct 21 ms 24556 KB Output is correct
11 Correct 100 ms 26988 KB Output is correct
12 Correct 19 ms 24556 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 25432 KB Output is correct
2 Correct 309 ms 25608 KB Output is correct
3 Correct 269 ms 25708 KB Output is correct
4 Correct 266 ms 25452 KB Output is correct
5 Correct 278 ms 25600 KB Output is correct
6 Correct 17 ms 24556 KB Output is correct
7 Correct 20 ms 24428 KB Output is correct
8 Correct 17 ms 24428 KB Output is correct
9 Correct 306 ms 25452 KB Output is correct
10 Correct 17 ms 24428 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 40720 KB Output is correct
2 Correct 1485 ms 40904 KB Output is correct
3 Correct 790 ms 40812 KB Output is correct
4 Correct 850 ms 42300 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 25452 KB Output is correct
2 Correct 312 ms 25616 KB Output is correct
3 Correct 268 ms 25580 KB Output is correct
4 Correct 267 ms 25452 KB Output is correct
5 Correct 265 ms 25452 KB Output is correct
6 Correct 811 ms 40792 KB Output is correct
7 Correct 1464 ms 40904 KB Output is correct
8 Correct 790 ms 40920 KB Output is correct
9 Correct 834 ms 42092 KB Output is correct
10 Correct 121 ms 36588 KB Output is correct
11 Correct 121 ms 36588 KB Output is correct
12 Correct 207 ms 39404 KB Output is correct
13 Correct 123 ms 36716 KB Output is correct
14 Correct 121 ms 36716 KB Output is correct
15 Correct 17 ms 24428 KB Output is correct
16 Correct 17 ms 24428 KB Output is correct
17 Correct 18 ms 24428 KB Output is correct
18 Correct 19 ms 24684 KB Output is correct
19 Correct 18 ms 24556 KB Output is correct
20 Correct 19 ms 24556 KB Output is correct
21 Correct 19 ms 24556 KB Output is correct
22 Correct 18 ms 24556 KB Output is correct
23 Correct 19 ms 24556 KB Output is correct
24 Correct 18 ms 24556 KB Output is correct
25 Correct 97 ms 26988 KB Output is correct
26 Correct 19 ms 24556 KB Output is correct
27 Correct 273 ms 25452 KB Output is correct
28 Execution timed out 20036 ms 69616 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 25324 KB Output is correct
2 Correct 361 ms 25584 KB Output is correct
3 Correct 273 ms 25580 KB Output is correct
4 Correct 264 ms 25580 KB Output is correct
5 Correct 287 ms 25708 KB Output is correct
6 Correct 827 ms 40940 KB Output is correct
7 Correct 1464 ms 40776 KB Output is correct
8 Correct 800 ms 40940 KB Output is correct
9 Correct 840 ms 42388 KB Output is correct
10 Correct 121 ms 36588 KB Output is correct
11 Correct 120 ms 36588 KB Output is correct
12 Correct 203 ms 39532 KB Output is correct
13 Correct 122 ms 36664 KB Output is correct
14 Correct 121 ms 36588 KB Output is correct
15 Correct 1880 ms 101048 KB Output is correct
16 Execution timed out 20020 ms 99284 KB Time limit exceeded
17 Halted 0 ms 0 KB -