oj.uz

답안 #962209

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
962209 2024-04-13T08:58:43 Z Ice_man 웜뱃 (IOI13_wombats) C++14
39 / 100
 20000 ms 19468 KB 
/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include"wombats.h"
#include <set>
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <cstdio>

#define maxn 5005
#define maxn2 205
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cerr<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;

/**std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}*/

typedef pair <long long, int> pli;

int d[maxn];
int c, r;
int h[maxn][maxn2];
int v[maxn][maxn2];
int dp[maxn][maxn2];


void dijkstra(int node)
{
    for(int i = 0; i < c; i++)
        d[i] = 1e9;
    d[node] = 0;

    for(int j = 0; j < r; j++)
    {
        set <int> q;
        for(int i = 0; i < c; i++)
            if(d[i] != 1e9)
                q.emplace(i);

        while(q.size())
        {
            int e = *q.begin();
            q.erase(q.begin());

            if(e + 1 < c)
                if(d[e + 1] > d[e] + h[j][e])
                {
                    d[e + 1] = d[e] + h[j][e];
                    q.emplace(e + 1);
                }

            if(e >= 1)
                if(d[e - 1] > d[e] + h[j][e - 1])
                {
                    d[e - 1] = d[e] + h[j][e - 1];
                    q.emplace(e - 1);
                }
        }

        if(j + 1 < r)
            for(int i = 0; i < c; i++)
                d[i] += v[j][i];

    }

    for(int i = 0; i < c; i++)
        dp[node][i] = d[i];
}



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; j++)
        {
            if(j + 1 < c)
                h[i][j] = H[i][j];

            if(i + 1 < r)
                v[i][j] = V[i][j];
        }

    for(int i = 0; i < c; i++)
        dijkstra(i);
}



void changeH(int P , int Q , int W)
{
    h[P][Q] = W;
    for(int i = 0; i < c; i++)
        dijkstra(i);
}

void changeV(int P , int Q , int W)
{
    v[P][Q] = W;
    for(int i = 0; i < c; i++)
        dijkstra(i);
}


int escape(int V1 , int V2)
{
    return dp[V1][V2];
}


/**int main()
{

    #ifdef ONLINE_JUDGE /// promeni
        freopen("input.in", "r", stdin);
        freopen("taxi.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    //startT = std::chrono::high_resolution_clock::now();





    return 0;
}*/

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

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 12900 KB Output is correct
2 Correct 137 ms 12920 KB Output is correct
3 Correct 193 ms 14412 KB Output is correct
4 Correct 136 ms 12924 KB Output is correct
5 Correct 141 ms 12904 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4452 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 3 ms 8536 KB Output is correct
11 Correct 67 ms 9412 KB Output is correct
12 Correct 2 ms 8536 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11205 ms 8708 KB Output is correct
2 Correct 9839 ms 8712 KB Output is correct
3 Correct 11124 ms 8712 KB Output is correct
4 Correct 11294 ms 8788 KB Output is correct
5 Correct 10414 ms 8712 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Execution timed out 20031 ms 8704 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 593 ms 18236 KB Output is correct
2 Correct 659 ms 18304 KB Output is correct
3 Correct 607 ms 18316 KB Output is correct
4 Correct 624 ms 19468 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11008 ms 8708 KB Output is correct
2 Correct 9837 ms 8716 KB Output is correct
3 Correct 10959 ms 8712 KB Output is correct
4 Correct 10883 ms 8716 KB Output is correct
5 Correct 10473 ms 8708 KB Output is correct
6 Correct 611 ms 18256 KB Output is correct
7 Correct 669 ms 18260 KB Output is correct
8 Correct 598 ms 18008 KB Output is correct
9 Correct 619 ms 18800 KB Output is correct
10 Correct 131 ms 12888 KB Output is correct
11 Correct 131 ms 12900 KB Output is correct
12 Correct 197 ms 14396 KB Output is correct
13 Correct 137 ms 12900 KB Output is correct
14 Correct 133 ms 12904 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 5 ms 8548 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 3 ms 8540 KB Output is correct
22 Correct 2 ms 8540 KB Output is correct
23 Correct 2 ms 8540 KB Output is correct
24 Correct 2 ms 8540 KB Output is correct
25 Correct 57 ms 9552 KB Output is correct
26 Correct 3 ms 8536 KB Output is correct
27 Execution timed out 20005 ms 8712 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10996 ms 8708 KB Output is correct
2 Correct 9474 ms 8716 KB Output is correct
3 Correct 10925 ms 8712 KB Output is correct
4 Correct 11242 ms 8712 KB Output is correct
5 Correct 10814 ms 8712 KB Output is correct
6 Correct 609 ms 18244 KB Output is correct
7 Correct 661 ms 18244 KB Output is correct
8 Correct 601 ms 18008 KB Output is correct
9 Correct 619 ms 19024 KB Output is correct
10 Correct 143 ms 12892 KB Output is correct
11 Correct 137 ms 12892 KB Output is correct
12 Correct 194 ms 14420 KB Output is correct
13 Correct 137 ms 12908 KB Output is correct
14 Correct 139 ms 12892 KB Output is correct
15 Execution timed out 20005 ms 18244 KB Time limit exceeded
16 Halted 0 ms 0 KB -