CSES - KILO 2018 2/5

Submission details
Task:	Counting Canals
Sender:	ollpu_kilo
Submission time:	2018-09-13 18:11:40 +0300
Language:	C++
Status:	READY
Result:	WRONG ANSWER

Test results
test	verdict	time
#1	ACCEPTED	0.04 s	details
#2	ACCEPTED	0.04 s	details
#3	ACCEPTED	0.04 s	details
#4	WRONG ANSWER	0.03 s	details
#5	ACCEPTED	0.04 s	details
#6	WRONG ANSWER	0.04 s	details
#7	WRONG ANSWER	0.03 s	details
#8	WRONG ANSWER	0.03 s	details
#9	WRONG ANSWER	0.03 s	details
#10	WRONG ANSWER	0.02 s	details
#11	WRONG ANSWER	0.18 s	details
#12	WRONG ANSWER	0.18 s	details
#13	WRONG ANSWER	0.21 s	details
#14	WRONG ANSWER	0.17 s	details
#15	WRONG ANSWER	0.18 s	details
#16	ACCEPTED	0.10 s	details
#17	ACCEPTED	0.11 s	details
#18	WRONG ANSWER	0.17 s	details
#19	WRONG ANSWER	0.15 s	details
#20	WRONG ANSWER	0.17 s	details
#21	WRONG ANSWER	0.22 s	details
#22	WRONG ANSWER	0.19 s	details
#23	WRONG ANSWER	0.26 s	details
#24	WRONG ANSWER	0.22 s	details
#25	WRONG ANSWER	0.22 s	details
#26	ACCEPTED	0.22 s	details
#27	ACCEPTED	0.21 s	details
#28	WRONG ANSWER	0.22 s	details
#29	WRONG ANSWER	0.20 s	details
#30	WRONG ANSWER	0.20 s	details

Code

#include <bits/stdc++.h>
using namespace std;
vector<int> v[101010];
set<int> aob[2][101010];
long res = 0;
void h(int i, int p=-1) {
  aob[0][i].insert(i);
  aob[1][i].insert(i);
  for (int j : v[i]) {
    if (j == p) continue;
    h(j, i);
    for (int x = 0; x < 2; ++x) {
      if (aob[x][j].size() > aob[x][i].size()) swap(aob[x][j], aob[x][i]);
      for (int e : aob[x][j]) aob[x][i].insert(e);
    }
  }
  while (*aob[0][i].rbegin() > i) aob[0][i].erase(--aob[0][i].end());
  while (*aob[1][i].begin() < i) aob[1][i].erase(aob[1][i].begin());
  res += aob[0][i].size()*aob[1][i].size();
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n-1; ++i) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  h(0);
  cout << res << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
`5 1 2 2 3 3 4 4 5` view save

correct output
`15` view save

user output
`15` view save

Test 2

Verdict: ACCEPTED

input
`4 3 2 2 1 4 2` view save

correct output
`9` view save

user output
`9` view save

Test 3

Verdict: ACCEPTED

input
`1` view save

correct output
`1` view save

user output
`1` view save

Test 4

Verdict: WRONG ANSWER

input
`6 1 3 3 5 3 4 4 6 ...` view save

correct output
`17` view save

user output
`20` view save

Test 5

Verdict: ACCEPTED

input
`10 10 1 1 9 9 2 2 8 ...` view save

correct output
`19` view save

user output
`19` view save

Test 6

Verdict: WRONG ANSWER

input
`10 10 6 2 4 1 2 5 10 ...` view save

correct output
`25` view save

user output
`27` view save

Test 7

Verdict: WRONG ANSWER

input
`10 9 1 8 1 8 5 10 2 ...` view save

correct output
`20` view save

user output
`22` view save

Test 8

Verdict: WRONG ANSWER

input
`10 9 5 1 6 8 5 10 6 ...` view save

correct output
`24` view save

user output
`26` view save

Test 9

Verdict: WRONG ANSWER

input
`10 10 3 1 6 6 3 10 8 ...` view save

correct output
`26` view save

user output
`31` view save

Test 10

Verdict: WRONG ANSWER

input
`10 1 10 9 3 5 10 6 8 ...` view save

correct output
`22` view save

user output
`27` view save

Test 11

Verdict: WRONG ANSWER

input
`100000 61825 85829 24480 90462 1014 5496 81225 44931 ...` view save

correct output
`3130799` view save

user output
`69901780` view save

Test 12

Verdict: WRONG ANSWER

input
`100000 12328 59847 68010 51200 20911 42026 5769 15416 ...` view save

correct output
`13958274` view save

user output
`374540338` view save

Test 13

Verdict: WRONG ANSWER

input
`100000 20362 12728 7958 63236 52010 30403 43065 57339 ...` view save

correct output
`15065805` view save

user output
`520556156` view save

Test 14

Verdict: WRONG ANSWER

input
`100000 8572 72714 94149 74894 64167 42479 28114 53008 ...` view save

correct output
`365273` view save

user output
`21330899` view save

Test 15

Verdict: WRONG ANSWER

input
`100000 1978 36216 32844 35606 89082 19460 32960 67705 ...` view save

correct output
`299957` view save

user output
`11625991` view save

Test 16

Verdict: ACCEPTED

input
`100000 1 100000 2 100000 2 99999 3 99999 ...` view save

correct output
`199999` view save

user output
`199999` view save

Test 17

Verdict: ACCEPTED

input
`100000 1 2 2 3 3 4 4 5 ...` view save

correct output
`5000050000` view save

user output
`5000050000` view save

Test 18

Verdict: WRONG ANSWER

input
`100000 26026 17578 2063 27495 18825 88516 73417 44243 ...` view save

correct output
`300106` view save

user output
`9745865` view save

Test 19

Verdict: WRONG ANSWER

input
`100000 62594 92916 39396 77445 39736 18145 51960 63921 ...` view save

correct output
`305292` view save

user output
`14316841` view save

Test 20

Verdict: WRONG ANSWER

input
`100000 35361 29834 80103 20628 56121 98538 96141 60130 ...` view save

correct output
`299953` view save

user output
`11712215` view save

Test 21

Verdict: WRONG ANSWER

input
`100000 83387 6566 1464 36071 83940 1947 30207 81630 ...` view save

correct output
`18170796` view save

user output
`188509351` view save

Test 22

Verdict: WRONG ANSWER

input
`100000 57048 59591 13592 7630 96625 65606 39702 62144 ...` view save

correct output
`122357921` view save

user output
`302671339` view save

Test 23

Verdict: WRONG ANSWER

input
`100000 665 16956 97424 82744 19070 82235 29207 21317 ...` view save

correct output
`255370837` view save

user output
`1152040442` view save

Test 24

Verdict: WRONG ANSWER

input
`100000 73391 7794 48957 7794 10376 7794 68812 7794 ...` view save

correct output
`661409588` view save

user output
`688192576` view save

Test 25

Verdict: WRONG ANSWER

input
`100000 25428 93716 47665 20024 43005 47665 47665 4035 ...` view save

correct output
`775090231` view save

user output
`1533653864` view save

Test 26

Verdict: ACCEPTED

input
`100000 88514 75301 20924 75301 8871 75301 26360 75301 ...` view save

correct output
`1860034699` view save

user output
`1860034699` view save

Test 27

Verdict: ACCEPTED

input
`100000 31831 1 46505 1 76032 1 41560 1 ...` view save

correct output
`199999` view save

user output
`199999` view save

Test 28

Verdict: WRONG ANSWER

input
`100000 38156 15310 92580 66280 10847 49530 8672 38794 ...` view save

correct output
`27926764` view save

user output
`531568287` view save

Test 29

Verdict: WRONG ANSWER

input
`100000 60300 13490 372 28166 4123 3653 97935 79942 ...` view save

correct output
`27607584` view save

user output
`488480237` view save

Test 30

Verdict: WRONG ANSWER

input
`100000 93798 40604 95227 14928 80126 98198 54474 67913 ...` view save

correct output
`22603373` view save

user output
`220943533` view save

KILO 2018 2/5

Counting Canals

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Tasks

Submissions (ollpu_kilo)