답안 #81637 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81637	2018-10-25T16:30:12 Z	tjdgus4384	물탱크 (KOI18_watertank)	C++14	100 / 100	1053 ms	92620 KB

watertank

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> p;
int n, m, h;
int idx[1050][1050];
vector<p> v[1000500];
int ans[1000500];

void make(int a, int b, int x)
{
    v[a].push_back({b, x});
    v[b].push_back({a, x});
}

int main()
{
    int x;
    scanf("%d %d %d", &n, &m, &h);
    int cnt = 0;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            idx[i][j] = ++cnt;
        }
    }
    for(int i = 1;i <= n + 1;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            scanf("%d", &x);
            if(x != -1) make(idx[i][j], idx[i - 1][j], x);
        }
    }
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m + 1;j++)
        {
            scanf("%d", &x);
            if(x != -1) make(idx[i][j], idx[i][j - 1], x);
        }
    }
    for(int i = 0;i <= n*m;i++) ans[i] = h;
    ans[0] = 0;
    priority_queue<p, vector<p>, greater<p> > pq;
    pq.push({0, 0});
    while(!pq.empty())
    {
        int f = pq.top().first;
        int s = pq.top().second;
        pq.pop();
        if(f != ans[s]) continue;
        for(int i = 0;i < v[s].size();i++)
        {
            int next = v[s][i].first;
            int d = v[s][i].second;
            int nexth = max(f, d);
            if(ans[next] > nexth)
            {
                ans[next] = nexth;
                pq.push({nexth, next});
            }
        }
    }
    int res = 0;
    for(int i = 1;i <= n*m;i++) res += ans[i];
    printf("%d", res);
}

Compilation message

watertank.cpp: In function 'int main()':
watertank.cpp:55:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i < v[s].size();i++)
                       ~~^~~~~~~~~~~~~
watertank.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &h);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watertank.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
watertank.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23800 KB	Output is correct
2	Correct	23 ms	24060 KB	Output is correct
3	Correct	23 ms	24060 KB	Output is correct
4	Correct	21 ms	24060 KB	Output is correct
5	Correct	21 ms	24060 KB	Output is correct
6	Correct	24 ms	24060 KB	Output is correct
7	Correct	23 ms	24060 KB	Output is correct
8	Correct	27 ms	24060 KB	Output is correct
9	Correct	23 ms	24064 KB	Output is correct
10	Correct	24 ms	24064 KB	Output is correct
11	Correct	22 ms	24064 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	24064 KB	Output is correct
2	Correct	22 ms	24124 KB	Output is correct
3	Correct	24 ms	24124 KB	Output is correct
4	Correct	23 ms	24124 KB	Output is correct
5	Correct	23 ms	24124 KB	Output is correct
6	Correct	22 ms	24124 KB	Output is correct
7	Correct	23 ms	24132 KB	Output is correct
8	Correct	25 ms	24132 KB	Output is correct
9	Correct	23 ms	24132 KB	Output is correct
10	Correct	23 ms	24144 KB	Output is correct
11	Correct	22 ms	24144 KB	Output is correct
12	Correct	22 ms	24144 KB	Output is correct
13	Correct	24 ms	24160 KB	Output is correct
14	Correct	23 ms	24160 KB	Output is correct
15	Correct	23 ms	24160 KB	Output is correct
16	Correct	23 ms	24160 KB	Output is correct
17	Correct	23 ms	24160 KB	Output is correct
18	Correct	22 ms	24160 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	208 ms	32096 KB	Output is correct
2	Correct	22 ms	32096 KB	Output is correct
3	Correct	208 ms	35420 KB	Output is correct
4	Correct	291 ms	52568 KB	Output is correct
5	Correct	23 ms	52568 KB	Output is correct
6	Correct	524 ms	69068 KB	Output is correct
7	Correct	228 ms	69068 KB	Output is correct
8	Correct	586 ms	79340 KB	Output is correct
9	Correct	228 ms	79340 KB	Output is correct
10	Correct	28 ms	79340 KB	Output is correct
11	Correct	588 ms	79340 KB	Output is correct
12	Correct	22 ms	79340 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	79340 KB	Output is correct
2	Correct	22 ms	79340 KB	Output is correct
3	Correct	23 ms	79340 KB	Output is correct
4	Correct	23 ms	79340 KB	Output is correct
5	Correct	21 ms	79340 KB	Output is correct
6	Correct	22 ms	79340 KB	Output is correct
7	Correct	23 ms	79340 KB	Output is correct
8	Correct	25 ms	79340 KB	Output is correct
9	Correct	22 ms	79340 KB	Output is correct
10	Correct	23 ms	79340 KB	Output is correct
11	Correct	24 ms	79340 KB	Output is correct
12	Correct	23 ms	79340 KB	Output is correct
13	Correct	24 ms	79340 KB	Output is correct
14	Correct	22 ms	79340 KB	Output is correct
15	Correct	22 ms	79340 KB	Output is correct
16	Correct	25 ms	79340 KB	Output is correct
17	Correct	23 ms	79340 KB	Output is correct
18	Correct	24 ms	79340 KB	Output is correct
19	Correct	22 ms	79340 KB	Output is correct

Subtask #5
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	79340 KB	Output is correct
2	Correct	21 ms	79340 KB	Output is correct
3	Correct	23 ms	79340 KB	Output is correct
4	Correct	22 ms	79340 KB	Output is correct
5	Correct	23 ms	79340 KB	Output is correct
6	Correct	215 ms	79340 KB	Output is correct
7	Correct	23 ms	79340 KB	Output is correct
8	Correct	26 ms	79340 KB	Output is correct
9	Correct	209 ms	79340 KB	Output is correct
10	Correct	23 ms	79340 KB	Output is correct
11	Correct	25 ms	79340 KB	Output is correct
12	Correct	224 ms	79340 KB	Output is correct
13	Correct	240 ms	79340 KB	Output is correct
14	Correct	23 ms	79340 KB	Output is correct
15	Correct	357 ms	79340 KB	Output is correct
16	Correct	22 ms	79340 KB	Output is correct
17	Correct	22 ms	79340 KB	Output is correct
18	Correct	23 ms	79340 KB	Output is correct
19	Correct	307 ms	79340 KB	Output is correct
20	Correct	23 ms	79340 KB	Output is correct
21	Correct	1053 ms	87532 KB	Output is correct
22	Correct	24 ms	87532 KB	Output is correct
23	Correct	24 ms	87532 KB	Output is correct
24	Correct	22 ms	87532 KB	Output is correct
25	Correct	24 ms	87532 KB	Output is correct
26	Correct	23 ms	87532 KB	Output is correct
27	Correct	22 ms	87532 KB	Output is correct
28	Correct	576 ms	87532 KB	Output is correct
29	Correct	525 ms	87532 KB	Output is correct
30	Correct	239 ms	87532 KB	Output is correct
31	Correct	570 ms	87532 KB	Output is correct
32	Correct	307 ms	87532 KB	Output is correct
33	Correct	22 ms	87532 KB	Output is correct
34	Correct	235 ms	87532 KB	Output is correct
35	Correct	23 ms	87532 KB	Output is correct
36	Correct	22 ms	87532 KB	Output is correct
37	Correct	23 ms	87532 KB	Output is correct
38	Correct	552 ms	87532 KB	Output is correct
39	Correct	996 ms	87564 KB	Output is correct
40	Correct	24 ms	87564 KB	Output is correct
41	Correct	25 ms	87564 KB	Output is correct
42	Correct	24 ms	87564 KB	Output is correct
43	Correct	24 ms	87564 KB	Output is correct
44	Correct	264 ms	87564 KB	Output is correct
45	Correct	959 ms	92620 KB	Output is correct
46	Correct	22 ms	92620 KB	Output is correct

답안 #81637

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 18.0 / 18.0

Subtask #3 15.0 / 15.0

Subtask #4 21.0 / 21.0

Subtask #5 40.0 / 40.0

Subtask #1
6.0 / 6.0

Subtask #2
18.0 / 18.0

Subtask #3
15.0 / 15.0

Subtask #4
21.0 / 21.0

Subtask #5
40.0 / 40.0