CSES - Siperia opettaa 4.0

Submission details
Task:	Jimi Hendrix
Sender:	Hansuzu
Submission time:	2016-08-04 17:18:39 +0300
Language:	C++
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	100

Test results
test	verdict	time
#1	ACCEPTED	0.06 s	details
#2	ACCEPTED	0.06 s	details
#3	ACCEPTED	0.06 s	details
#4	ACCEPTED	0.05 s	details
#5	ACCEPTED	0.06 s	details
#6	ACCEPTED	0.06 s	details
#7	ACCEPTED	0.05 s	details
#8	ACCEPTED	0.06 s	details
#9	ACCEPTED	0.07 s	details
#10	ACCEPTED	0.06 s	details
#11	ACCEPTED	0.06 s	details
#12	ACCEPTED	0.06 s	details
#13	ACCEPTED	0.06 s	details
#14	ACCEPTED	0.05 s	details
#15	ACCEPTED	0.06 s	details
#16	ACCEPTED	0.06 s	details
#17	ACCEPTED	0.06 s	details
#18	ACCEPTED	0.06 s	details
#19	ACCEPTED	0.06 s	details
#20	ACCEPTED	0.06 s	details
#21	ACCEPTED	0.06 s	details
#22	ACCEPTED	0.06 s	details
#23	ACCEPTED	0.16 s	details
#24	ACCEPTED	0.14 s	details
#25	ACCEPTED	0.58 s	details
#26	ACCEPTED	0.58 s	details
#27	ACCEPTED	0.59 s	details
#28	ACCEPTED	0.66 s	details
#29	ACCEPTED	0.55 s	details
#30	ACCEPTED	0.58 s	details
#31	ACCEPTED	0.57 s	details
#32	ACCEPTED	0.31 s	details
#33	ACCEPTED	0.31 s	details
#34	ACCEPTED	0.31 s	details
#35	ACCEPTED	0.30 s	details
#36	ACCEPTED	0.32 s	details
#37	ACCEPTED	0.30 s	details
#38	ACCEPTED	0.32 s	details
#39	ACCEPTED	0.44 s	details
#40	ACCEPTED	0.34 s	details
#41	ACCEPTED	0.31 s	details
#42	ACCEPTED	0.43 s	details
#43	ACCEPTED	0.31 s	details
#44	ACCEPTED	0.45 s	details
#45	ACCEPTED	0.32 s	details
#46	ACCEPTED	0.30 s	details
#47	ACCEPTED	0.32 s	details
#48	ACCEPTED	0.44 s	details
#49	ACCEPTED	0.47 s	details
#50	ACCEPTED	0.47 s	details
#51	ACCEPTED	0.49 s	details
#52	ACCEPTED	0.49 s	details
#53	ACCEPTED	0.51 s	details
#54	ACCEPTED	0.46 s	details

Compiler report

input/code.cpp: In function 'void clearsz(int)':
input/code.cpp:20:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<rt[c].size(); ++i) clearsz(rt[c][i].F);
                              ^
input/code.cpp: In function 'int go(int, int)':
input/code.cpp:29:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<rt[c].size(); ++i){
                              ^
input/code.cpp:41:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<rt[c].size(); ++i){
                                ^
input/code.cpp: In function 'std::pair<std::pair<int, int>, std::pair<int, int> > findg(int)':
input/code.cpp:72:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<rt[c].size(); ++i){
                              ^
input/code.cpp: In function 'void find(int)':
input/code.cpp:105:30: war...

Code

#include <iostream>
#include <vector>
#define MP make_pair
#define F first
#define S second
using namespace std;
int n, m;
string s;


vector<pair<int, char> > rt[505050];
vector<int> crt[505050];

int sz[505050];
int u[505050];

void clearsz(int c){
  if (u[c] || sz[c]==0) return;
  sz[c]=0;
  for (int i=0; i<rt[c].size(); ++i) clearsz(rt[c][i].F);
}

int d;
int nz;
int go(int c, int p){
  sz[c]=1;
  int mx=0;
  int a=0;
  for (int i=0; i<rt[c].size(); ++i){
    int w=rt[c][i].F;
    if (u[w] || sz[w]) continue;
    a=go(w, c);
    if (a) return a;
    sz[c]+=sz[w];
    mx=max(mx, sz[w]);
  }
  mx=max(mx, nz-sz[c]);
  if (mx<=nz/2){
    u[c]=++d;
    int nzt=nz;
    for (int i=0; i<rt[c].size(); ++i){
      int w=rt[c][i].F;
      if (u[w]) continue;
      int nsz=sz[w];
      if (w==p) nsz=nz-sz[c];
      nz=nsz;
      clearsz(w);
      crt[c].push_back(go(w, -1));
      nz=nzt;
    }--d;
    sz[c]=nz;
    return c;
  }
  return 0;
}

int cn;

int na=-1;
int nb=-1;


int pr[505050];

int mxl;
pair<pair<int, int>, pair<int, int> > findg(int c){
  int mxa=0;
  int mxai=c;
  int mxb=0;
  int mxbi=c;
  
  for (int i=0; i<rt[c].size(); ++i){
    if (rt[c][i].F==pr[c] || u[rt[c][i].F]<=mxl) continue;
    
    pr[rt[c][i].F]=c;
    pair<pair<int, int>, pair<int, int> > k=findg(rt[c][i].F);
    if (k.F.F<m-1 && s[k.F.F]==rt[c][i].S){
      ++k.F.F;
    }
    if (k.S.F<m-1 && s[m-k.S.F-1]==rt[c][i].S){
      ++k.S.F;
    }
    if (k.F.F>mxa){
      mxa=k.F.F;
      mxai=k.F.S;
    }
    if (k.S.F>mxb){
      mxb=k.S.F;
      mxbi=k.S.S;
    }
  }
  return MP(MP(mxa, mxai), MP(mxb, mxbi));
}


void find(int c){
  if (sz[c]<m) return;  
  if (na!=-1) return;
  pr[c]=-1;
  mxl=u[c];
  int mxa=0;
  int mxb=0;
  int mxai=c;
  int mxbi=c;
  for (int i=0; i<rt[c].size(); ++i){
    pair<pair<int, int>, pair<int, int> > mx=findg(rt[c][i].F);
    if (s[mx.F.F]==rt[c][i].S)  ++mx.F.F;
    if (s[m-mx.S.F-1]==rt[c][i].S) ++mx.S.F;
    if (mxa+mx.S.F>=m){
      na=mxai;
      nb=mx.S.S;
      return;
    }
    if (mxb+mx.F.F>=m){
      na=mx.F.S;
      nb=mxbi;
      return;
    }
    if (mx.F.F>mxa){
      mxa=mx.F.F;
      mxai=mx.F.S;
    }
    if (mx.S.F>mxb){
      mxb=mx.S.F;
      mxbi=mx.S.S;
    }
  }
  
  for (int i=0; i<crt[c].size(); ++i)find(crt[c][i]);
}


int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m;
  for (int i=1; i<n; ++i){
    int a, b; char c;
    cin >> a >> b >> c;
    rt[a].push_back(MP(b, c));
    rt[b].push_back(MP(a, c));
  }
  nz=n;
  cn=go(1, -1);
  cin >> s;
  find(cn);
  cout << na << " " << nb << "\n";
}

Test details

Test 1

Verdict: ACCEPTED

input
`9 3 1 2 a 2 3 b 2 4 a 4 5 b ...` view save

correct output
`1 9` view save

user output
`1 9` view save

Test 2

Verdict: ACCEPTED

input
`2 1 1 2 b b` view save

correct output
`2 1` view save

user output
`2 1` view save

Test 3

Verdict: ACCEPTED

input
`2 1 1 2 k p` view save

correct output
`-1 -1` view save

user output
`-1 -1` view save

Test 4

Verdict: ACCEPTED

input
`10 2 1 4 a 7 5 c 1 9 a 10 1 c ...` view save

correct output
`2 1` view save

user output
`3 6` view save

Test 5

Verdict: ACCEPTED

input
`10 5 6 1 c 7 6 a 7 8 c 6 5 c ...` view save

correct output
`-1 -1` view save

user output
`-1 -1` view save

Test 6

Verdict: ACCEPTED

input
`10 3 3 10 c 1 9 b 4 8 a 10 4 b ...` view save

correct output
`10 1` view save

user output
`10 9` view save

Test 7

Verdict: ACCEPTED

input
`10 5 9 1 c 5 4 c 1 7 a 3 9 c ...` view save

correct output
`-1 -1` view save

user output
`-1 -1` view save

Test 8

Verdict: ACCEPTED

input
`10 2 9 10 c 9 8 c 9 3 c 9 4 c ...` view save

correct output
`1 10` view save

user output
`1 10` view save

Test 9

Verdict: ACCEPTED

input
`10 2 10 3 c 10 4 b 10 8 b 10 1 a ...` view save

correct output
`1 9` view save

user output
`1 3` view save

Test 10

Verdict: ACCEPTED

input
`10 2 6 7 e 6 9 l 6 2 q 6 10 i ...` view save

correct output
`1 9` view save

user output
`1 9` view save

Test 11

Verdict: ACCEPTED

input
`10 2 4 1 s 4 6 y 4 9 p 4 2 t ...` view save

correct output
`-1 -1` view save

user output
`-1 -1` view save

Test 12

Verdict: ACCEPTED

input
`1000 11 987 593 b 428 821 a 865 116 b 676 817 a ...` view save

correct output
`998 1` view save

user output
`998 819` view save

Test 13

Verdict: ACCEPTED

input
`1000 10 782 148 a 498 256 a 389 269 a 156 291 b ...` view save

correct output
`652 1` view save

user output
`469 561` view save

Test 14

Verdict: ACCEPTED

input
`1000 20 657 328 a 185 518 a 778 343 b 56 390 a ...` view save

correct output
`-1 -1` view save

user output
`-1 -1` view save

Test 15

Verdict: ACCEPTED

input
`1000 10 555 641 a 309 489 b 799 943 b 934 662 a ...` view save

correct output
`953 332` view save

user output
`645 569` view save

Test 16

Verdict: ACCEPTED

input
`1000 6 161 816 b 25 712 b 540 233 b 980 204 c ...` view save

correct output
`990 1` view save

user output
`683 149` view save

Test 17

Verdict: ACCEPTED

input
`1000 635 163 159 o 615 797 x 192 770 n 211 860 j ...` view save

correct output
`650 951` view save

user output
`650 134` view save

Test 18

Verdict: ACCEPTED

input
`1000 191 370 983 e 792 207 u 260 334 t 504 718 t ...` view save

correct output
`-1 -1` view save

user output
`-1 -1` view save

Test 19

Verdict: ACCEPTED

input
`1000 40 471 594 o 345 995 n 973 405 y 215 646 o ...` view save

correct output
`1 982` view save

user output
`778 218` view save

Test 20

Verdict: ACCEPTED

input
`1000 100 151 902 a 730 935 b 295 369 b 823 145 a ...` view save

correct output
`948 1` view save

user output
`414 676` view save

Test 21

Verdict: ACCEPTED

input
`1000 2 660 306 n 660 778 l 660 924 y 660 902 n ...` view save

correct output
`988 969` view save

user output
`988 70` view save

Test 22

Verdict: ACCEPTED

input
`1000 2 526 579 a 526 150 b 526 168 a 526 24 b ...` view save

correct output
`1000 1` view save

user output
`579 168` view save

Test 23

Verdict: ACCEPTED

input
`200000 2 140844 190697 r 140844 124115 f 140844 112461 i 140844 19992 d ...` view save

correct output
`124115 199952` view save

user output
`124115 73325` view save

Test 24

Verdict: ACCEPTED

input
`200000 2 105421 5980 b 105421 150207 a 105421 115929 a 105421 77625 b ...` view save

correct output
`200000 1` view save

user output
`5980 77625` view save

Test 25

Verdict: ACCEPTED

input
`200000 50000 38207 51908 a 123390 86325 b 123134 78235 b 104677 7330 a ...` view save

correct output
`112796 1` view save

user output
`112796 57909` view save

Test 26

Verdict: ACCEPTED

input
`200000 150000 116487 13268 b 84833 43815 b 40993 188837 a 197098 131672 a ...` view save

correct output
`-1 -1` view save

user output
`-1 -1` view save

Test 27

Verdict: ACCEPTED

input
`200000 5000 6663 37269 l 74938 58143 w 79955 85205 e 172041 175241 z ...` view save

correct output
`199644 1` view save

user output
`67105 142940` view save

Test 28

Verdict: ACCEPTED

input
`200000 10000 162365 187926 o 25849 45282 n 69475 76654 d 59397 127873 g ...` view save

correct output
`-1 -1` view save

user output
`-1 -1` view save

Test 29

Verdict: ACCEPTED

input
`200000 4736 135910 152433 b 196857 44930 b 180142 58474 b 123198 131735 a ...` view save

correct output
`193336 1` view save

user output
`58629 1192` view save

Test 30

Verdict: ACCEPTED

input
`200000 54739 116541 156209 b 112813 171247 b 134494 179457 b 52303 59188 b ...` view save

correct output
`175912 1` view save

user output
`24116 102951` view save

Test 31

Verdict: ACCEPTED

input
`200000 49999 117084 195231 a 38504 191202 n 134618 132918 i 24748 150597 v ...` view save

correct output
`198783 1` view save

user output
`35200 11981` view save

Test 32

Verdict: ACCEPTED

input
`200000 20 56534 21846 a 127466 99775 b 197009 10481 a 13071 25861 a ...` view save

correct output
`154647 179047` view save

user output
`111576 24194` view save

Test 33

Verdict: ACCEPTED

input
`200000 18 25645 115335 b 138086 169629 b 147195 28130 a 90251 19229 b ...` view save

correct output
`1 11192` view save

user output
`53824 62914` view save

Test 34

Verdict: ACCEPTED

input
`200000 15 130040 52065 a 85066 121947 a 142587 138972 c 98852 109707 b ...` view save

correct output
`186271 1` view save

user output
`135125 102418` view save

Test 35

Verdict: ACCEPTED

input
`200000 13 186972 158038 n 141304 144334 c 150644 92260 d 75472 56494 e ...` view save

correct output
`134673 188304` view save

user output
`90352 188304` view save

Test 36

Verdict: ACCEPTED

input
`200000 22 77116 177355 b 41248 8511 a 196560 61055 b 93074 47152 b ...` view save

correct output
`101231 1` view save

user output
`7011 177273` view save

Test 37

Verdict: ACCEPTED

input
`200000 24 12092 977 b 89606 92554 a 98999 130713 b 29359 58778 a ...` view save

correct output
`45421 191976` view save

user output
`105435 168998` view save

Test 38

Verdict: ACCEPTED

input
`200000 32 42678 46956 a 85804 92343 a 58647 187834 a 40022 25789 a ...` view save

correct output
`170898 83806` view save

user output
`10897 83806` view save

Test 39

Verdict: ACCEPTED

input
`200000 37 97344 4860 b 59032 105557 b 33232 135880 a 41849 198146 b ...` view save

correct output
`-1 -1` view save

user output
`-1 -1` view save

Test 40

Verdict: ACCEPTED

input
`200000 35 165160 188580 b 169019 179034 a 162600 167716 b 12953 68090 b ...` view save

correct output
`34556 152796` view save

user output
`34556 121411` view save

Test 41

Verdict: ACCEPTED

input
`200000 36 25981 130203 b 96700 180125 a 127368 165961 b 64857 173799 b ...` view save

correct output
`140998 25928` view save

user output
`125942 25928` view save

Test 42

Verdict: ACCEPTED

input
`200000 37 84272 141200 a 115974 60401 b 164159 9233 b 95061 109295 a ...` view save

correct output
`-1 -1` view save

user output
`-1 -1` view save

Test 43

Verdict: ACCEPTED

input
`200000 9 64062 160380 r 125886 155571 c 171774 169538 y 98278 87688 l ...` view save

correct output
`178549 166726` view save

user output
`178549 34044` view save

Test 44

Verdict: ACCEPTED

input
`200000 10 180259 144845 g 116606 49642 c 17065 195194 h 19110 15737 w ...` view save

correct output
`-1 -1` view save

user output
`-1 -1` view save

Test 45

Verdict: ACCEPTED

input
`200000 28 69795 159223 b 120740 49968 a 175591 112576 b 13475 97987 b ...` view save

correct output
`191304 139389` view save

user output
`182861 60392` view save

Test 46

Verdict: ACCEPTED

input
`200000 29 196920 93284 b 10733 37080 b 60158 81484 a 182923 50537 a ...` view save

correct output
`118826 166004` view save

user output
`146699 50672` view save

Test 47

Verdict: ACCEPTED

input
`200000 29 139335 36430 a 19077 167148 a 14826 196018 a 24497 91018 b ...` view save

correct output
`176667 184941` view save

user output
`7196 111243` view save

Test 48

Verdict: ACCEPTED

input
`200000 38 198494 65812 a 154023 48530 a 161230 125892 a 163972 48765 b ...` view save

correct output
`-1 -1` view save

user output
`-1 -1` view save

Test 49

Verdict: ACCEPTED

input
`200000 100000 138756 91790 c 50567 42961 d 199463 59094 d 158218 93083 e ...` view save

correct output
`120276 158931` view save

user output
`120276 158931` view save

Test 50

Verdict: ACCEPTED

input
`200000 100000 93749 174202 a 182960 2304 n 23460 111271 d 142390 124490 h ...` view save

correct output
`197101 82602` view save

user output
`197101 82602` view save

Test 51

Verdict: ACCEPTED

input
`200000 50000 26351 4065 d 190076 154406 b 47708 176166 c 56748 94747 d ...` view save

correct output
`102345 166560` view save

user output
`80847 166560` view save

Test 52

Verdict: ACCEPTED

input
`200000 50000 25937 89996 f 147254 157058 r 72097 126197 k 143403 116253 i ...` view save

correct output
`175469 125703` view save

user output
`73950 125703` view save

Test 53

Verdict: ACCEPTED

input
`200000 1000 138872 149623 e 161260 117770 a 151105 54329 a 120464 187446 d ...` view save

correct output
`188942 1` view save

user output
`15560 57113` view save

Test 54

Verdict: ACCEPTED

input
`200000 1000 53986 146114 r 139076 142403 c 86688 88562 g 40058 165888 g ...` view save

correct output
`140202 1` view save

user output
`65384 90992` view save

Siperia opettaa 4.0

Jimi Hendrix

Compiler report

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

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Tasks

Submissions (Hansuzu)