| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 64206 |
2018-08-03T13:39:06 Z |
gs14004 |
None (KOI18_watertank) |
C++17 |
|
1555 ms |
189000 KB |
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 1005;
struct disj{
int pa[1000005];
void init(int n){
iota(pa, pa + n + 1, 0);
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
pa[q] = p; return 1;
}
}disj;
int n, m, h;
vector<pi> e[MAXN];
vector<pi> gph[1000005];
lint dfs(int x, int p, int e){
lint ret = e;
for(auto &i : gph[x]){
if(i.second != p){
ret += dfs(i.second, x, max(e, i.first));
}
}
return ret;
}
int get(int x, int y){
if(1 <= x && x <= n && 1 <= y && y <= m){
return (x - 1) * m + (y - 1) + 1;
}
else return 0;
}
int main(){
cin >> n >> m >> h;
disj.init(n * m);
for(int i=0; i<n+1; i++){
for(int j=1; j<=m; j++){
int l = get(i, j);
int r = get(i + 1, j);
int x;
scanf("%d",&x);
if(x == -1) x = h;
e[x].push_back(pi(l, r));
}
}
for(int i=1; i<=n; i++){
for(int j=0; j<m+1; j++){
int l = get(i, j);
int r = get(i, j + 1);
int x;
scanf("%d",&x);
if(x == -1) x = h;
e[x].push_back(pi(l, r));
}
}
for(int i=0; i<=h; i++){
for(auto &j : e[i]){
if(disj.uni(j.first, j.second)){
gph[j.first].push_back(pi(i, j.second));
gph[j.second].push_back(pi(i, j.first));
}
}
}
cout << dfs(0, -1, 0) << endl;
}
Compilation message
watertank.cpp: In function 'int main()':
watertank.cpp:54:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
~~~~~^~~~~~~~~
watertank.cpp:64:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
22 ms |
24044 KB |
Output is correct |
| 3 |
Correct |
22 ms |
24044 KB |
Output is correct |
| 4 |
Correct |
27 ms |
24044 KB |
Output is correct |
| 5 |
Correct |
27 ms |
24044 KB |
Output is correct |
| 6 |
Correct |
23 ms |
24044 KB |
Output is correct |
| 7 |
Correct |
26 ms |
24044 KB |
Output is correct |
| 8 |
Correct |
27 ms |
24084 KB |
Output is correct |
| 9 |
Correct |
28 ms |
24140 KB |
Output is correct |
| 10 |
Correct |
27 ms |
24152 KB |
Output is correct |
| 11 |
Correct |
26 ms |
24152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24152 KB |
Output is correct |
| 2 |
Correct |
27 ms |
24300 KB |
Output is correct |
| 3 |
Correct |
24 ms |
24300 KB |
Output is correct |
| 4 |
Correct |
24 ms |
24300 KB |
Output is correct |
| 5 |
Correct |
24 ms |
24300 KB |
Output is correct |
| 6 |
Correct |
23 ms |
24300 KB |
Output is correct |
| 7 |
Correct |
23 ms |
24300 KB |
Output is correct |
| 8 |
Correct |
23 ms |
24300 KB |
Output is correct |
| 9 |
Correct |
22 ms |
24300 KB |
Output is correct |
| 10 |
Correct |
26 ms |
24300 KB |
Output is correct |
| 11 |
Correct |
23 ms |
24300 KB |
Output is correct |
| 12 |
Correct |
24 ms |
24300 KB |
Output is correct |
| 13 |
Correct |
24 ms |
24316 KB |
Output is correct |
| 14 |
Correct |
26 ms |
24328 KB |
Output is correct |
| 15 |
Correct |
26 ms |
24328 KB |
Output is correct |
| 16 |
Correct |
23 ms |
24328 KB |
Output is correct |
| 17 |
Correct |
24 ms |
24344 KB |
Output is correct |
| 18 |
Correct |
27 ms |
24344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
568 ms |
81140 KB |
Output is correct |
| 2 |
Correct |
25 ms |
81140 KB |
Output is correct |
| 3 |
Correct |
602 ms |
81140 KB |
Output is correct |
| 4 |
Correct |
615 ms |
89520 KB |
Output is correct |
| 5 |
Correct |
23 ms |
89520 KB |
Output is correct |
| 6 |
Correct |
638 ms |
100212 KB |
Output is correct |
| 7 |
Correct |
780 ms |
100212 KB |
Output is correct |
| 8 |
Correct |
617 ms |
104648 KB |
Output is correct |
| 9 |
Correct |
676 ms |
104648 KB |
Output is correct |
| 10 |
Correct |
28 ms |
104648 KB |
Output is correct |
| 11 |
Correct |
595 ms |
117576 KB |
Output is correct |
| 12 |
Correct |
23 ms |
117576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
117576 KB |
Output is correct |
| 2 |
Correct |
25 ms |
117576 KB |
Output is correct |
| 3 |
Correct |
25 ms |
117576 KB |
Output is correct |
| 4 |
Correct |
29 ms |
117576 KB |
Output is correct |
| 5 |
Correct |
23 ms |
117576 KB |
Output is correct |
| 6 |
Correct |
27 ms |
117576 KB |
Output is correct |
| 7 |
Correct |
27 ms |
117576 KB |
Output is correct |
| 8 |
Correct |
29 ms |
117576 KB |
Output is correct |
| 9 |
Correct |
26 ms |
117576 KB |
Output is correct |
| 10 |
Correct |
29 ms |
117576 KB |
Output is correct |
| 11 |
Correct |
26 ms |
117576 KB |
Output is correct |
| 12 |
Correct |
24 ms |
117576 KB |
Output is correct |
| 13 |
Correct |
30 ms |
117576 KB |
Output is correct |
| 14 |
Correct |
24 ms |
117576 KB |
Output is correct |
| 15 |
Correct |
23 ms |
117576 KB |
Output is correct |
| 16 |
Correct |
29 ms |
117576 KB |
Output is correct |
| 17 |
Correct |
25 ms |
117576 KB |
Output is correct |
| 18 |
Correct |
28 ms |
117576 KB |
Output is correct |
| 19 |
Correct |
26 ms |
117576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
117576 KB |
Output is correct |
| 2 |
Correct |
22 ms |
117576 KB |
Output is correct |
| 3 |
Correct |
23 ms |
117576 KB |
Output is correct |
| 4 |
Correct |
26 ms |
117576 KB |
Output is correct |
| 5 |
Correct |
27 ms |
117576 KB |
Output is correct |
| 6 |
Correct |
547 ms |
119892 KB |
Output is correct |
| 7 |
Correct |
26 ms |
119892 KB |
Output is correct |
| 8 |
Correct |
29 ms |
119892 KB |
Output is correct |
| 9 |
Correct |
734 ms |
119892 KB |
Output is correct |
| 10 |
Correct |
25 ms |
119892 KB |
Output is correct |
| 11 |
Correct |
28 ms |
119892 KB |
Output is correct |
| 12 |
Correct |
581 ms |
125220 KB |
Output is correct |
| 13 |
Correct |
499 ms |
125220 KB |
Output is correct |
| 14 |
Correct |
26 ms |
125220 KB |
Output is correct |
| 15 |
Correct |
1097 ms |
125220 KB |
Output is correct |
| 16 |
Correct |
21 ms |
125220 KB |
Output is correct |
| 17 |
Correct |
23 ms |
125220 KB |
Output is correct |
| 18 |
Correct |
22 ms |
125220 KB |
Output is correct |
| 19 |
Correct |
586 ms |
125220 KB |
Output is correct |
| 20 |
Correct |
27 ms |
125220 KB |
Output is correct |
| 21 |
Correct |
1555 ms |
131000 KB |
Output is correct |
| 22 |
Correct |
27 ms |
131000 KB |
Output is correct |
| 23 |
Correct |
27 ms |
131000 KB |
Output is correct |
| 24 |
Correct |
26 ms |
131000 KB |
Output is correct |
| 25 |
Correct |
25 ms |
131000 KB |
Output is correct |
| 26 |
Correct |
26 ms |
131000 KB |
Output is correct |
| 27 |
Correct |
26 ms |
131000 KB |
Output is correct |
| 28 |
Correct |
1400 ms |
131072 KB |
Output is correct |
| 29 |
Correct |
604 ms |
131072 KB |
Output is correct |
| 30 |
Correct |
501 ms |
131072 KB |
Output is correct |
| 31 |
Correct |
518 ms |
131072 KB |
Output is correct |
| 32 |
Correct |
937 ms |
131072 KB |
Output is correct |
| 33 |
Correct |
28 ms |
131072 KB |
Output is correct |
| 34 |
Correct |
609 ms |
131072 KB |
Output is correct |
| 35 |
Correct |
26 ms |
131072 KB |
Output is correct |
| 36 |
Correct |
24 ms |
131072 KB |
Output is correct |
| 37 |
Correct |
29 ms |
131072 KB |
Output is correct |
| 38 |
Correct |
660 ms |
131072 KB |
Output is correct |
| 39 |
Correct |
543 ms |
189000 KB |
Output is correct |
| 40 |
Correct |
24 ms |
189000 KB |
Output is correct |
| 41 |
Correct |
24 ms |
189000 KB |
Output is correct |
| 42 |
Correct |
22 ms |
189000 KB |
Output is correct |
| 43 |
Correct |
30 ms |
189000 KB |
Output is correct |
| 44 |
Correct |
767 ms |
189000 KB |
Output is correct |
| 45 |
Correct |
1391 ms |
189000 KB |
Output is correct |
| 46 |
Correct |
21 ms |
189000 KB |
Output is correct |
