| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 128504 |
2019-07-11T04:28:11 Z |
김세빈(#3158) |
Rope (JOI17_rope) |
C++14 |
|
864 ms |
78472 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
vector <pii> V[1010101];
vector <int> X;
int S[1010101], K[1010101];
int A[1010101];
bool chk[1010101];
int n, m;
int main()
{
int i, j, k, a, b;
scanf("%d%d", &n, &m);
for(i=1; i<=n; i++){
scanf("%d", &a);
S[a] ++;
if(i > 1 && a != b){
V[a].emplace_back(b, i & 1);
V[b].emplace_back(a, i & 1);
}
b = a;
}
for(i=1; i<=m; i++){
K[i] = i;
X.push_back(i);
}
sort(K + 1, K + m + 1, [&](int &a, int &b){
return S[a] > S[b];
});
for(i=1; !X.empty(); i++){
chk[K[i]] = 1;
for(pii &t: V[K[i]]){
chk[t.first] = 1;
}
for(j=0; j<X.size(); ){
if(chk[X[j]]) j ++;
else{
A[X[j]] = S[X[j]] + S[K[i]];
swap(X[j], X.back());
X.pop_back();
}
}
chk[K[i]] = 0;
for(pii &t: V[K[i]]){
chk[t.first] = 0;
}
}
for(i=1; i<=m; i++){
sort(V[i].begin(), V[i].end());
for(j=0; j<V[i].size(); j=k){
for(k=j, a=0, b=0; V[i][j].first == V[i][k].first; k++){
(V[i][k].second? a : b) ++;
}
A[i] = max(A[i], S[i] + S[V[i][j].first] - min(a, b));
}
}
for(i=1; i<=m; i++){
printf("%d\n", n - A[i]);
}
return 0;
}
Compilation message
rope.cpp: In function 'int main()':
rope.cpp:46:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0; j<X.size(); ){
~^~~~~~~~~
rope.cpp:64:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0; j<V[i].size(); j=k){
~^~~~~~~~~~~~
rope.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
rope.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 3 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 4 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 5 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 6 |
Correct |
23 ms |
24060 KB |
Output is correct |
| 7 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 8 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 9 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 10 |
Correct |
24 ms |
24060 KB |
Output is correct |
| 11 |
Correct |
24 ms |
24184 KB |
Output is correct |
| 12 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 13 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 14 |
Correct |
24 ms |
24088 KB |
Output is correct |
| 15 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 16 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 17 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 18 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 19 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 20 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 21 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 22 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 23 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 24 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 25 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 26 |
Correct |
23 ms |
24056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 3 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 4 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 5 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 6 |
Correct |
23 ms |
24060 KB |
Output is correct |
| 7 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 8 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 9 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 10 |
Correct |
24 ms |
24060 KB |
Output is correct |
| 11 |
Correct |
24 ms |
24184 KB |
Output is correct |
| 12 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 13 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 14 |
Correct |
24 ms |
24088 KB |
Output is correct |
| 15 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 16 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 17 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 18 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 19 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 20 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 21 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 22 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 23 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 24 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 25 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 26 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 27 |
Correct |
47 ms |
26056 KB |
Output is correct |
| 28 |
Correct |
43 ms |
25816 KB |
Output is correct |
| 29 |
Correct |
47 ms |
25816 KB |
Output is correct |
| 30 |
Correct |
43 ms |
25576 KB |
Output is correct |
| 31 |
Correct |
47 ms |
25868 KB |
Output is correct |
| 32 |
Correct |
43 ms |
25652 KB |
Output is correct |
| 33 |
Correct |
46 ms |
25684 KB |
Output is correct |
| 34 |
Correct |
44 ms |
25580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 3 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 4 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 5 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 6 |
Correct |
23 ms |
24060 KB |
Output is correct |
| 7 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 8 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 9 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 10 |
Correct |
24 ms |
24060 KB |
Output is correct |
| 11 |
Correct |
24 ms |
24184 KB |
Output is correct |
| 12 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 13 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 14 |
Correct |
24 ms |
24088 KB |
Output is correct |
| 15 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 16 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 17 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 18 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 19 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 20 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 21 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 22 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 23 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 24 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 25 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 26 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 27 |
Correct |
47 ms |
26056 KB |
Output is correct |
| 28 |
Correct |
43 ms |
25816 KB |
Output is correct |
| 29 |
Correct |
47 ms |
25816 KB |
Output is correct |
| 30 |
Correct |
43 ms |
25576 KB |
Output is correct |
| 31 |
Correct |
47 ms |
25868 KB |
Output is correct |
| 32 |
Correct |
43 ms |
25652 KB |
Output is correct |
| 33 |
Correct |
46 ms |
25684 KB |
Output is correct |
| 34 |
Correct |
44 ms |
25580 KB |
Output is correct |
| 35 |
Correct |
53 ms |
26436 KB |
Output is correct |
| 36 |
Correct |
52 ms |
26360 KB |
Output is correct |
| 37 |
Correct |
52 ms |
26232 KB |
Output is correct |
| 38 |
Correct |
52 ms |
26360 KB |
Output is correct |
| 39 |
Correct |
52 ms |
26360 KB |
Output is correct |
| 40 |
Correct |
52 ms |
26744 KB |
Output is correct |
| 41 |
Correct |
52 ms |
26872 KB |
Output is correct |
| 42 |
Correct |
52 ms |
26764 KB |
Output is correct |
| 43 |
Correct |
52 ms |
26616 KB |
Output is correct |
| 44 |
Correct |
52 ms |
26744 KB |
Output is correct |
| 45 |
Correct |
51 ms |
26744 KB |
Output is correct |
| 46 |
Correct |
52 ms |
26360 KB |
Output is correct |
| 47 |
Correct |
53 ms |
26616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 3 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 4 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 5 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 6 |
Correct |
23 ms |
24060 KB |
Output is correct |
| 7 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 8 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 9 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 10 |
Correct |
24 ms |
24060 KB |
Output is correct |
| 11 |
Correct |
24 ms |
24184 KB |
Output is correct |
| 12 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 13 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 14 |
Correct |
24 ms |
24088 KB |
Output is correct |
| 15 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 16 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 17 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 18 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 19 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 20 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 21 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 22 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 23 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 24 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 25 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 26 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 27 |
Correct |
47 ms |
26056 KB |
Output is correct |
| 28 |
Correct |
43 ms |
25816 KB |
Output is correct |
| 29 |
Correct |
47 ms |
25816 KB |
Output is correct |
| 30 |
Correct |
43 ms |
25576 KB |
Output is correct |
| 31 |
Correct |
47 ms |
25868 KB |
Output is correct |
| 32 |
Correct |
43 ms |
25652 KB |
Output is correct |
| 33 |
Correct |
46 ms |
25684 KB |
Output is correct |
| 34 |
Correct |
44 ms |
25580 KB |
Output is correct |
| 35 |
Correct |
53 ms |
26436 KB |
Output is correct |
| 36 |
Correct |
52 ms |
26360 KB |
Output is correct |
| 37 |
Correct |
52 ms |
26232 KB |
Output is correct |
| 38 |
Correct |
52 ms |
26360 KB |
Output is correct |
| 39 |
Correct |
52 ms |
26360 KB |
Output is correct |
| 40 |
Correct |
52 ms |
26744 KB |
Output is correct |
| 41 |
Correct |
52 ms |
26872 KB |
Output is correct |
| 42 |
Correct |
52 ms |
26764 KB |
Output is correct |
| 43 |
Correct |
52 ms |
26616 KB |
Output is correct |
| 44 |
Correct |
52 ms |
26744 KB |
Output is correct |
| 45 |
Correct |
51 ms |
26744 KB |
Output is correct |
| 46 |
Correct |
52 ms |
26360 KB |
Output is correct |
| 47 |
Correct |
53 ms |
26616 KB |
Output is correct |
| 48 |
Correct |
372 ms |
50464 KB |
Output is correct |
| 49 |
Correct |
371 ms |
50656 KB |
Output is correct |
| 50 |
Correct |
373 ms |
50448 KB |
Output is correct |
| 51 |
Correct |
367 ms |
49140 KB |
Output is correct |
| 52 |
Correct |
362 ms |
44792 KB |
Output is correct |
| 53 |
Correct |
339 ms |
46968 KB |
Output is correct |
| 54 |
Correct |
333 ms |
43480 KB |
Output is correct |
| 55 |
Correct |
334 ms |
42616 KB |
Output is correct |
| 56 |
Correct |
343 ms |
41464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 3 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 4 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 5 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 6 |
Correct |
23 ms |
24060 KB |
Output is correct |
| 7 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 8 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 9 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 10 |
Correct |
24 ms |
24060 KB |
Output is correct |
| 11 |
Correct |
24 ms |
24184 KB |
Output is correct |
| 12 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 13 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 14 |
Correct |
24 ms |
24088 KB |
Output is correct |
| 15 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 16 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 17 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 18 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 19 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 20 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 21 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 22 |
Correct |
24 ms |
24056 KB |
Output is correct |
| 23 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 24 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 25 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 26 |
Correct |
23 ms |
24056 KB |
Output is correct |
| 27 |
Correct |
47 ms |
26056 KB |
Output is correct |
| 28 |
Correct |
43 ms |
25816 KB |
Output is correct |
| 29 |
Correct |
47 ms |
25816 KB |
Output is correct |
| 30 |
Correct |
43 ms |
25576 KB |
Output is correct |
| 31 |
Correct |
47 ms |
25868 KB |
Output is correct |
| 32 |
Correct |
43 ms |
25652 KB |
Output is correct |
| 33 |
Correct |
46 ms |
25684 KB |
Output is correct |
| 34 |
Correct |
44 ms |
25580 KB |
Output is correct |
| 35 |
Correct |
53 ms |
26436 KB |
Output is correct |
| 36 |
Correct |
52 ms |
26360 KB |
Output is correct |
| 37 |
Correct |
52 ms |
26232 KB |
Output is correct |
| 38 |
Correct |
52 ms |
26360 KB |
Output is correct |
| 39 |
Correct |
52 ms |
26360 KB |
Output is correct |
| 40 |
Correct |
52 ms |
26744 KB |
Output is correct |
| 41 |
Correct |
52 ms |
26872 KB |
Output is correct |
| 42 |
Correct |
52 ms |
26764 KB |
Output is correct |
| 43 |
Correct |
52 ms |
26616 KB |
Output is correct |
| 44 |
Correct |
52 ms |
26744 KB |
Output is correct |
| 45 |
Correct |
51 ms |
26744 KB |
Output is correct |
| 46 |
Correct |
52 ms |
26360 KB |
Output is correct |
| 47 |
Correct |
53 ms |
26616 KB |
Output is correct |
| 48 |
Correct |
372 ms |
50464 KB |
Output is correct |
| 49 |
Correct |
371 ms |
50656 KB |
Output is correct |
| 50 |
Correct |
373 ms |
50448 KB |
Output is correct |
| 51 |
Correct |
367 ms |
49140 KB |
Output is correct |
| 52 |
Correct |
362 ms |
44792 KB |
Output is correct |
| 53 |
Correct |
339 ms |
46968 KB |
Output is correct |
| 54 |
Correct |
333 ms |
43480 KB |
Output is correct |
| 55 |
Correct |
334 ms |
42616 KB |
Output is correct |
| 56 |
Correct |
343 ms |
41464 KB |
Output is correct |
| 57 |
Correct |
864 ms |
78472 KB |
Output is correct |
| 58 |
Correct |
743 ms |
71316 KB |
Output is correct |
| 59 |
Correct |
747 ms |
71264 KB |
Output is correct |
| 60 |
Correct |
770 ms |
74204 KB |
Output is correct |
| 61 |
Correct |
764 ms |
74352 KB |
Output is correct |
| 62 |
Correct |
504 ms |
60416 KB |
Output is correct |
| 63 |
Correct |
618 ms |
66024 KB |
Output is correct |
| 64 |
Correct |
564 ms |
62568 KB |
Output is correct |
| 65 |
Correct |
424 ms |
53892 KB |
Output is correct |
