QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#726897	#9607. 熟练	lmeowdn	100 ✓	682ms	182664kb	C++14	3.4kb	2024-11-09 10:11:21	2024-11-09 10:11:23

Judging History

你现在查看的是最新测评结果

[2024-11-09 10:11:23]
评测

测评结果：100
用时：682ms
内存：182664kb

查看

[2024-11-09 10:11:21]
提交

answer

#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}

#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
  return x*w;
}

const int N=5e5+5;
int c,T,sz[N],top[N],son[N],dfn[N],tick,d[N],n,m,f[N],g[N],ans[N],x[N],y[N],sss[N],B;
vi e[N],pd[N],pa[N],p[N];

void dfs1(int u,int fa) {
  f[u]=fa; sz[u]=1; d[u]=d[f[u]]+1;
  for(int v:e[u]) if(v!=fa) {
    dfs1(v,u); sz[u]+=sz[v];
    if(sz[v]>sz[son[u]]) son[u]=v;
  }
}
void dfs2(int u,int tp) {
  top[u]=tp; dfn[u]=++tick;
  if(son[u]) dfs2(son[u],tp);
  for(int v:e[u]) if(v!=f[u]&&v!=son[u]) dfs2(v,v);
}
int lca(int u,int v) {
  for(;top[u]!=top[v];u=f[top[u]])
    if(d[top[u]]<d[top[v]]) swap(u,v);
  //cout<<"   "<<u<<" "<<v<<" "<<d[u]<<" "<<d[v]<<endl;
  return d[u]<d[v]?u:v;
}
void dfs3(int u) {
  for(int v:e[u]) if(v!=f[u]) dfs3(v), g[u]+=g[v];
}
void upd(int a,int u,int r) {
  while(top[a]!=top[u]) {
      int x=a;
      pd[a].eb(r);
      pa[top[a]].eb(r);
      a=f[top[a]];
    } if(a!=u) pd[a].eb(r), pa[son[u]].eb(r);
}

int b[N],s[N];
void setx(int x,int y) {
  //cout<<"SET "<<x<<" "<<y<<endl;
  b[x]+=y, s[(x-1)/B+1]+=y;
}
int qry() {
  int x=1;
  while(s[x]==B) x++;
  x=(x-1)*B+1;
  while(b[x]) x++;
  return x;
}

void dfs4(int u) {
  for(int x:pa[u]) setx(ans[x],1);
  for(int r:p[u]) {
    int a=x[r], b=y[r];
    //cout<<"UU "<<u<<" "<<a<<" "<<b<<" "<<qry()<<endl;
    ans[r]=qry();
    setx(ans[r],1);
    upd(a,u,r), upd(b,u,r);
  }
  for(int x:pd[u]) setx(ans[x],-1);
  for(int x:p[u]) setx(ans[x],-1);
  if(son[u]) dfs4(son[u]);
  for(int v:e[u]) if(v!=son[u]&&v!=f[u]) dfs4(v);
}

signed main() {
  c=read(), T=read();
  while(T--) {
    n=read(), m=read(); tick=0; B=sqrt(m);
    rep(i,1,n) e[i].clear(), sz[i]=top[i]=son[i]=dfn[i]=g[i]=0, pa[i].clear(), pd[i].clear(), p[i].clear();
    rep(i,2,n) {
      int u=read(), v=read();
      e[u].eb(v), e[v].eb(u);
    }
    dfs1(1,0);
    dfs2(1,1);
    rep(i,1,m) {
      int a=read(), b=read(), l=lca(a,b);
      x[i]=a, y[i]=b, p[l].eb(i);
      g[a]++, g[b]++, g[l]--, g[f[l]]--;
    }
    dfs3(1);
    int res=0;
    rep(i,1,n) chmax(res,g[i]);
    printf("%lld\n",res);
    dfs4(1);
    rep(i,1,m) printf("%lld ",ans[i]); puts("");
    rep(i,1,m) b[ans[i]]=0, s[(ans[i]-1)/B+1]=0, ans[i]=0;
  }
  return 0;
}

源文件, 语言: C++14

詳細信息

Subtask #1:

score: 3

Accepted

Test #1:

score: 3

Accepted

time: 54ms

memory: 73580kb

input:

output:

result:

ok ok

Subtask #2:

score: 14

Accepted

Dependency #1:

100%

Accepted

Test #2:

score: 14

Accepted

time: 67ms

memory: 106624kb

input:

output:

result:

ok ok

Test #3:

score: 14

Accepted

time: 137ms

memory: 120432kb

input:

output:

5
1 2 4 3 5 
4
3 1 2 3 4 
4
1 2 3 4 
4
1 2 3 4 
2
1 1 1 2 
4
1 4 2 3 
5
1 2 3 4 5 
3
1 1 2 2 3 
2
1 1 1 2 
4
1 2 3 4 
2
1 1 2 1 
4
1 3 2 2 4 
3
1 1 1 2 3 
4
2 1 3 4 
3
2 1 2 2 3 
2
1 1 2 2 1 
4
4 2 3 1 2 
3
3 2 3 1 
4
1 3 4 2 
3
1 1 1 2 3 
3
1 1 3 2 
5
2 1 3 5 4 
4
2 4 2 3 1 
2
1 1 2 2 
4
1 2 1 3 4 ...

result:

ok ok

Test #4:

score: 14

Accepted

time: 78ms

memory: 96740kb

input:

output:

result:

ok ok

Test #5:

score: 14

Accepted

time: 95ms

memory: 91176kb

input:

output:

5
1 2 3 4 5 
4
1 4 1 2 3 
4
4 2 1 1 3 
4
1 1 2 3 4 
4
1 2 3 1 4 
3
3 1 1 2 
3
3 1 2 1 
3
1 3 2 1 
5
1 2 3 4 5 
3
1 2 1 3 
4
1 3 4 2 
3
1 1 2 3 
3
1 2 2 3 
3
1 2 3 1 2 
4
1 1 2 3 4 
4
1 2 1 4 3 
4
1 2 3 4 
2
1 1 1 2 
5
4 1 2 5 3 
3
1 2 2 3 3 
5
1 4 2 5 3 
4
1 3 2 4 
5
3 1 4 2 5 
3
1 2 3 2 
4
3 1 2 3 ...

result:

ok ok

Test #6:

score: 14

Accepted

time: 42ms

memory: 73960kb

input:

output:

result:

ok ok

Test #7:

score: 14

Accepted

time: 63ms

memory: 74168kb

input:

output:

result:

ok ok

Test #8:

score: 14

Accepted

time: 85ms

memory: 96696kb

input:

output:

result:

ok ok

Test #9:

score: 14

Accepted

time: 108ms

memory: 87288kb

input:

output:

result:

ok ok

Test #10:

score: 14

Accepted

time: 183ms

memory: 103936kb

input:

output:

5
1 2 3 4 5 
5
2 5 3 4 1 
4
2 1 4 3 4 
3
1 2 3 1 
4
1 1 4 2 3 
3
2 1 3 2 
4
1 2 2 3 4 
4
1 2 3 4 
5
1 3 2 4 5 
4
1 3 2 4 
4
1 2 3 4 
5
1 4 2 5 3 
3
1 1 3 1 2 
5
1 4 2 5 3 
3
1 1 2 3 
2
2 1 1 2 
3
1 3 2 3 
3
1 2 1 3 3 
4
2 3 4 1 
5
1 2 3 4 5 
3
1 2 3 1 
4
3 1 4 2 1 
4
1 2 3 4 
5
1 4 5 2 3 
3
1 1 2 3 ...

result:

ok ok

Subtask #3:

score: 9

Accepted

Test #11:

score: 9

Accepted

time: 283ms

memory: 177784kb

input:

3
1769
481318 428631
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

66
7 47 15 47 19 26 43 17 22 5 40 24 2 28 38 32 22 14 14 50 49 4 45 27 56 54 33 29 1 39 52 22 26 35 21 9 21 16 14 36 28 20 44 31 12 46 27 10 19 23 37 5 10 6 35 44 55 11 1 16 8 2 12 18 1 34 16 33 8 19 31 3 15 30 42 52 4 17 24 11 6 51 46 25 11 35 41 7 9 11 25 9 3 13 48 34 33 8 34 6 35 12 53 2 16 1 19 ...

result:

ok ok

Test #12:

score: 9

Accepted

time: 167ms

memory: 106220kb

input:

3
5246
78503 54670
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 5...

output:

12758
10938 4240 339 9800 7699 6346 2007 76 10218 5099 6048 2409 3151 9097 8089 8649 59 8261 10310 3039 10107 5848 10823 6730 3388 1134 3119 12608 868 9084 3100 5950 3473 1611 10312 3444 321 4571 5695 7129 9235 760 6371 7372 12446 10037 565 2278 6314 321 7060 12272 7800 12569 8687 7280 11223 9193 58...

result:

ok ok

Test #13:

score: 9

Accepted

time: 113ms

memory: 74624kb

input:

output:

160
38 29 44 16 24 139 66 19 109 105 103 55 7 49 95 114 123 77 1 82 142 60 35 70 54 5 9 56 131 74 47 3 105 40 55 85 21 25 56 58 67 39 24 97 43 1 76 75 91 37 36 52 30 57 25 69 23 34 77 48 78 141 61 3 12 110 65 48 13 59 119 42 117 44 87 18 21 3 98 129 32 84 132 17 52 28 8 76 19 116 99 11 33 18 54 6 90...

result:

ok ok

Test #14:

score: 9

Accepted

time: 114ms

memory: 74392kb

input:

output:

558
148 537 112 217 209 410 136 260 195 375 210 315 234 292 159 215 342 258 300 180 84 295 422 20 473 196 266 457 138 279 395 1 69 286 310 327 526 393 280 442 100 268 350 107 359 167 245 314 60 342 69 401 306 17 297 354 31 248 290 205 33 60 105 327 173 182 531 466 52 182 77 408 465 5 538 9 505 150 1...

result:

ok ok

Test #15:

score: 9

Accepted

time: 408ms

memory: 182664kb

input:

3
130
498610 459330
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 ...

output:

28970
4318 8168 42 18794 2818 13201 5818 6740 19087 2853 19327 11210 17989 1884 23652 16738 10771 27881 12031 21203 16372 3641 14454 4146 7887 7410 12022 9061 7108 2386 5868 1371 25392 1308 10731 14487 125 5402 3049 8941 17028 14519 3602 3045 21713 1997 21414 15867 19219 15400 15859 3011 2808 5786 4...

result:

ok ok

Test #16:

score: 9

Accepted

time: 327ms

memory: 176904kb

input:

3
3566
462541 448340
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

183
2 147 46 118 66 100 71 68 70 20 84 151 84 80 54 134 123 39 32 26 58 97 96 36 14 124 29 86 73 50 7 58 19 141 4 40 76 53 74 47 63 121 95 64 30 6 90 52 93 12 120 116 133 125 7 21 85 51 32 11 119 109 37 9 94 29 48 82 1 106 15 56 10 115 9 139 26 20 82 24 86 39 22 50 158 90 69 56 12 55 16 39 8 103 32 ...

result:

ok ok

Subtask #4:

score: 20

Accepted

Test #17:

score: 20

Accepted

time: 8ms

memory: 73692kb

input:

output:

839
1 1 2 2 3 4 5 6 7 8 1 9 10 11 12 13 14 15 16 17 18 1 19 20 1 21 22 23 24 2 25 26 27 28 2 29 1 30 1 31 32 33 34 35 36 37 38 7 39 40 41 42 43 44 45 46 47 8 48 49 50 51 52 53 54 55 1 56 57 1 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 2 1 78 79 80 81 82 83 84 85 86 8 87 88 89 90 91 ...

result:

ok ok

Test #18:

score: 20

Accepted

time: 3ms

memory: 73680kb

input:

output:

417
153 83 233 397 309 69 58 49 90 113 122 171 283 88 55 197 11 5 215 21 210 49 154 3 117 134 143 173 324 8 158 36 198 10 167 318 210 367 199 22 65 49 35 252 13 178 44 33 8 241 60 229 29 242 8 108 146 18 220 29 204 28 128 97 113 31 6 280 34 49 352 24 8 1 398 50 358 174 123 155 56 315 17 258 13 268 2...

result:

ok ok

Test #19:

score: 20

Accepted

time: 8ms

memory: 73856kb

input:

output:

161
1 2 3 3 48 4 1 2 1 1 2 5 1 2 6 127 5 4 3 7 8 1 9 135 19 10 3 5 1 11 6 12 13 136 5 9 14 7 16 4 2 8 3 127 15 10 7 6 2 20 21 9 1 9 2 128 22 4 3 10 16 4 5 6 17 7 2 3 3 127 8 23 2 2 9 11 18 1 12 13 24 14 8 5 128 10 6 15 1 19 10 11 16 17 18 7 7 20 1 2 8 25 12 62 1 26 1 4 27 28 119 13 19 29 20 127 128 ...

result:

ok ok

Test #20:

score: 20

Accepted

time: 3ms

memory: 73792kb

input:

output:

473
270 11 22 133 237 69 254 56 170 276 288 22 241 272 18 293 307 353 419 98 158 169 77 272 382 172 67 337 38 130 334 113 275 63 375 16 135 115 63 40 383 326 209 201 117 297 130 54 145 25 11 95 123 324 8 80 196 25 26 131 2 250 198 226 96 363 315 237 210 192 250 12 125 379 401 341 211 146 19 52 17 28...

result:

ok ok

Test #21:

score: 20

Accepted

time: 4ms

memory: 71684kb

input:

output:

196
28 1 46 105 2 124 3 4 5 6 137 30 7 138 142 37 5 8 9 143 144 10 2 11 145 12 13 1 14 146 147 15 1 16 17 18 19 20 10 21 22 3 23 2 148 24 149 25 150 26 27 28 151 5 29 4 30 31 152 153 32 1 33 154 46 34 35 36 37 3 155 156 48 38 39 56 40 41 42 43 44 45 46 47 48 157 158 159 160 49 50 161 51 52 162 75 5 ...

result:

ok ok

Test #22:

score: 20

Accepted

time: 7ms

memory: 73728kb

input:

output:

216
1 4 2 1 7 3 4 2 99 101 3 4 104 5 6 7 105 8 9 10 11 12 13 14 9 108 2 109 4 15 10 2 11 110 112 16 3 5 1 17 18 62 125 114 2 126 19 5 115 117 20 1 21 2 1 22 6 14 23 3 24 25 26 27 8 28 124 29 5 6 125 30 31 32 33 34 35 36 37 38 39 40 126 41 127 128 129 42 43 9 15 4 130 44 45 46 8 19 20 1 7 47 48 127 2...

result:

ok ok

Test #23:

score: 20

Accepted

time: 8ms

memory: 73840kb

input:

output:

175
93 84 27 39 11 7 8 48 46 3 30 83 75 168 119 107 10 55 130 53 82 22 62 96 99 43 59 85 20 55 45 3 124 33 65 64 123 30 148 65 135 140 23 77 117 159 85 21 138 104 103 126 52 15 20 37 86 120 88 48 127 1 136 29 54 68 56 77 153 30 137 108 6 78 144 16 127 15 36 13 10 23 111 86 3 98 147 11 102 71 6 95 3 ...

result:

ok ok

Test #24:

score: 20

Accepted

time: 8ms

memory: 73912kb

input:

output:

588
89 467 468 469 467 470 1 2 3 1 4 5 6 468 7 2 8 2 471 9 10 472 11 12 13 14 473 15 16 4 469 17 470 471 18 19 472 474 20 21 4 5 1 22 23 24 25 473 1 26 27 28 29 30 31 32 474 33 475 1 3 476 34 477 478 35 475 6 36 479 37 38 39 480 40 41 42 43 44 45 46 47 481 48 476 49 5 477 50 51 7 482 483 484 478 5 3...

result:

ok ok

Test #25:

score: 20

Accepted

time: 8ms

memory: 73812kb

input:

output:

123
1 1 1 2 2 1 3 2 1 2 2 1 3 4 4 2 3 4 3 5 4 5 2 3 5 4 5 6 6 3 6 2 3 4 4 7 7 6 7 3 8 7 5 9 8 9 8 5 5 8 10 9 6 10 11 7 6 12 9 13 8 6 7 10 14 8 7 15 4 11 11 5 12 6 10 11 7 9 9 8 13 16 17 12 13 10 14 14 15 12 13 14 11 15 12 16 15 9 10 13 16 18 14 17 17 10 16 11 18 8 9 12 18 13 19 15 14 20 17 18 21 19 ...

result:

ok ok

Test #26:

score: 20

Accepted

time: 8ms

memory: 73820kb

input:

output:

648
1 3 2 3 4 5 8 2 1 6 7 8 5 9 10 10 11 11 12 30 13 14 15 16 2 33 3 17 18 19 15 20 21 5 2 22 23 18 24 25 26 27 28 29 30 31 32 33 34 35 4 36 23 3 37 38 27 39 38 40 7 28 41 42 43 5 44 45 68 46 6 75 47 31 4 32 48 49 9 50 51 52 76 53 46 77 48 54 87 55 56 1 93 50 57 2 58 94 59 100 55 109 111 60 61 62 63...

result:

ok ok

Test #27:

score: 20

Accepted

time: 4ms

memory: 73824kb

input:

output:

675
1 1 10 12 88 89 13 18 20 22 90 2 3 26 1 31 9 39 47 91 92 3 93 94 5 2 7 1 95 96 97 56 98 59 99 100 101 65 67 102 9 68 72 103 104 74 2 105 106 75 107 108 109 79 85 13 1 88 90 110 101 14 111 112 113 114 115 15 2 6 116 102 3 4 117 103 118 119 5 120 19 21 136 147 149 5 6 153 121 162 163 122 180 123 2...

result:

ok ok

Test #28:

score: 20

Accepted

time: 14ms

memory: 73720kb

input:

output:

377
13 36 1 2 2 2 3 41 4 1 3 51 5 3 1 56 5 6 7 8 9 4 10 11 12 1 13 79 14 98 2 15 3 16 17 18 19 6 8 20 130 21 22 23 24 25 26 6 27 1 190 207 9 208 10 28 29 30 212 213 6 31 216 224 55 32 1 33 227 233 1 235 34 243 244 245 11 35 36 37 246 38 15 1 21 39 40 247 9 3 248 41 64 42 43 249 44 4 45 250 46 17 47 ...

result:

ok ok

Test #29:

score: 20

Accepted

time: 11ms

memory: 71584kb

input:

output:

261
2 1 2 3 4 5 6 7 8 9 10 10 11 12 13 14 15 16 17 18 19 20 21 1 22 23 9 24 9 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 2 3 55 56 57 58 59 2 60 61 62 63 64 65 66 67 3 68 69 70 71 2 1 72 73 74 75 76 77 78 79 80 6 81 82 83 84 85 86 87 88 89 90 9 91 92 93...

result:

ok ok

Test #30:

score: 20

Accepted

time: 11ms

memory: 73728kb

input:

output:

34
12 1 9 7 5 4 6 17 5 9 26 15 26 1 17 9 5 9 10 3 10 6 15 4 14 22 12 19 7 1 2 7 10 8 2 6 9 3 16 12 2 5 4 13 26 31 10 14 10 26 4 9 13 9 20 9 10 12 2 17 17 26 9 16 3 2 25 8 7 2 32 19 6 12 11 15 8 7 3 20 8 4 11 7 15 4 14 8 18 2 14 6 5 1 1 3 9 10 4 18 1 6 4 18 3 7 7 22 18 1 5 13 2 2 1 20 11 17 5 4 7 15 ...

result:

ok ok

Test #31:

score: 20

Accepted

time: 3ms

memory: 73996kb

input:

output:

19
1 2 3 4 5 6 7 8 17 2 3 5 1 5 1 1 1 6 2 1 6 6 7 5 2 1 1 2 1 1 1 8 1 1 1 1 2 1 2 1 1 5 4 1 1 1 2 10 5 4 5 1 2 1 2 2 1 3 1 1 1 6 6 4 1 2 1 6 9 1 1 8 1 2 2 1 3 1 5 8 1 1 10 1 6 1 11 2 3 3 1 1 1 5 2 1 1 6 7 1 9 5 1 9 3 3 1 3 1 9 1 3 4 1 3 1 3 5 2 1 1 5 1 1 6 3 1 9 1 1 14 2 6 16 3 2 5 4 1 4 5 1 1 4 3 2...

result:

ok ok

Test #32:

score: 20

Accepted

time: 3ms

memory: 71900kb

input:

output:

150
1 1 2 2 2 3 1 4 3 4 3 1 5 4 3 6 2 7 4 5 1 2 6 4 2 7 8 8 9 5 10 9 2 6 11 3 5 3 12 2 2 4 10 6 13 6 1 10 1 1 11 4 1 6 5 6 7 8 4 7 7 8 11 9 9 10 3 14 10 12 8 11 3 9 9 10 13 5 13 3 11 14 15 16 12 2 15 12 13 6 11 12 4 14 17 6 17 18 13 16 7 14 14 13 15 14 8 15 16 16 17 1 18 17 18 17 19 7 19 18 20 20 19...

result:

ok ok

Subtask #5:

score: 22

Accepted

Dependency #4:

100%

Accepted

Test #33:

score: 22

Accepted

time: 98ms

memory: 94824kb

input:

5
496
94286 94269
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
9 12
4 13
3 14
13 15
1 16
5 17
16 18
15 19
18 20
2 21
10 22
12 23
23 24
14 25
19 26
20 27
26 28
8 29
29 30
27 31
21 32
25 33
28 34
22 35
30 36
17 37
32 38
33 39
7 40
38 41
37 42
39 43
11 44
44 45
35 46
40 47
41 48
43 49
24 50
34 51
45 52
47...

output:

27238
1 2 3 4 124 54 5 139 6 7 8 9 10 11 12 13 14 15 16 97 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 37 40 41 123 42 43 44 45 46 91 47 48 44 49 50 51 52 53 54 55 56 57 58 59 60 61 62 40 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 ...

result:

ok ok

Test #34:

score: 22

Accepted

time: 111ms

memory: 103844kb

input:

5
102
87302 98915
1 2
2 3
3 4
4 5
1 6
2 7
3 8
1 9
7 10
3 11
9 12
5 13
2 14
13 15
3 16
9 17
7 18
13 19
19 20
16 21
4 22
20 23
14 24
18 25
17 26
26 27
7 28
4 29
3 30
28 31
16 32
32 33
5 34
13 35
17 36
10 37
19 38
14 39
22 40
22 41
36 42
25 43
43 44
12 45
6 46
33 47
24 48
38 49
8 50
31 51
26 52
47 53
2...

output:

43611
3 1 2 3 23 34 4 135 5 5 235 264 6 285 1 3 292 313 373 7 384 4 8 5 389 6 9 415 1 436 439 10 8 11 450 11 493 12 12 496 13 2 499 547 14 17 14 15 559 6 16 578 598 605 17 18 1 18 626 19 20 21 22 1 651 656 665 19 679 4 2 23 24 7 20 25 1 26 9 692 10 693 21 27 28 13 29 702 758 783 827 5 6 30 15 16 31 ...

result:

ok ok

Test #35:

score: 22

Accepted

time: 110ms

memory: 112300kb

input:

5
465
95072 88256
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26...

output:

58693
1 24500 2 3 35913 39857 39857 2 4 5 39858 6 7 8 39859 39860 9 10 11 2 12 3 1 5 39861 13 14 15 39858 39862 16 17 18 19 20 5 6 21 9 3 39863 39864 39865 22 23 24 1 25 39866 26 39859 39867 27 28 29 30 39868 39869 3 8 31 6 7 32 39870 39871 1 33 34 39872 1 9 35 36 37 38 39 5 40 41 39873 11 4 39860 4...

result:

ok ok

Test #36:

score: 22

Accepted

time: 47ms

memory: 81316kb

input:

output:

11000
1 2 3 4 9 5 6 3 7 8 9 10 11 12 26 13 14 17 15 20 16 17 18 19 20 21 22 23 24 25 26 38 27 28 4 29 30 31 32 67 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 4 58 51 59 60 61 62 21 63 64 65 66 67 68 69 70 71 38 72 73 74 75 76 77 78 79 80 81 82 83 84 72 85 86 87 88 89 9...

result:

ok ok

Test #37:

score: 22

Accepted

time: 39ms

memory: 80052kb

input:

output:

3386
1 2 5 3 4 5 6 6 7 8 16 20 21 30 1 9 10 1 11 60 12 64 13 14 1 66 2 15 83 16 17 18 1 103 19 104 107 20 21 22 109 3 23 24 25 26 3 110 27 28 29 7 30 31 113 120 32 33 34 125 1 6 35 36 37 38 39 40 154 41 42 7 158 172 43 188 198 44 211 45 46 8 4 47 48 6 5 49 50 51 215 218 52 220 222 53 54 7 9 232 8 55...

result:

ok ok

Test #38:

score: 22

Accepted

time: 58ms

memory: 82628kb

input:

5
942
12731 14938
1 2
2 3
3 4
3 5
2 6
1 7
2 8
4 9
4 10
7 11
7 12
4 13
8 14
6 15
4 16
2 17
10 18
4 19
9 20
3 21
17 22
14 23
6 24
20 25
2 26
3 27
22 28
7 29
15 30
27 31
5 32
19 33
6 34
31 35
11 36
33 37
21 38
10 39
34 40
6 41
20 42
19 43
22 44
27 45
41 46
27 47
34 48
36 49
49 50
26 51
47 52
25 53
35 5...

output:

1051
2 14 6 1 1 10 34 2 3 54 73 97 2 4 4 106 131 133 137 7 5 10 150 169 11 198 12 201 6 2 7 206 7 209 212 8 214 258 9 13 3 10 263 14 11 10 309 12 11 13 13 316 14 17 3 1 2 2 1 1 15 1 15 3 1 16 2 1 16 5 6 8 9 7 1 2 3 14 2 5 15 15 5 3 17 1 6 3 1 329 8 12 16 6 17 17 3 15 18 18 16 5 1 13 4 4 17 3 6 7 5 1...

result:

ok ok

Test #39:

score: 22

Accepted

time: 31ms

memory: 74968kb

input:

output:

451
1 5 1 2 3 2 15 36 3 3 38 4 51 5 67 4 6 83 7 1 8 5 9 85 10 6 11 7 12 13 88 14 90 95 123 8 15 16 131 17 18 19 20 21 134 22 23 24 9 157 25 175 10 184 8 26 27 3 191 28 192 1 11 2 12 2 193 29 30 31 32 13 14 15 16 17 33 34 5 35 36 18 19 37 194 195 38 20 196 197 3 1 198 21 22 39 23 40 199 41 24 42 43 1...

result:

ok ok

Test #40:

score: 22

Accepted

time: 31ms

memory: 75008kb

input:

output:

118
1 1 2 3 2 4 5 6 7 8 9 3 10 11 12 13 14 15 16 1 7 17 2 18 19 20 21 22 23 24 25 26 4 27 28 29 30 31 32 33 34 35 36 37 6 9 38 1 1 1 1 2 7 10 39 1 40 2 3 41 4 5 10 2 4 5 12 42 3 15 11 4 3 43 12 6 17 44 3 5 6 14 3 16 7 45 5 7 4 5 17 4 1 7 4 7 8 18 9 46 10 10 5 8 20 47 48 23 11 5 49 24 25 12 50 11 51 ...

result:

ok ok

Test #41:

score: 22

Accepted

time: 31ms

memory: 74932kb

input:

output:

345
323 164 141 168 79 14 103 88 116 108 207 247 241 29 122 314 130 3 123 122 272 273 128 86 55 269 182 140 266 104 38 109 305 18 143 52 230 133 156 136 298 21 275 148 172 154 225 26 113 44 216 236 21 87 245 223 130 51 84 278 57 88 181 293 199 289 134 106 74 108 15 272 42 63 229 105 3 171 194 7 10 2...

result:

ok ok

Test #42:

score: 22

Accepted

time: 35ms

memory: 74992kb

input:

output:

695
1 56 2 3 3 3 4 258 1 5 4 6 1 478 5 1 3 6 7 7 2 8 9 10 7 5 525 11 2 2 12 553 8 536 2 553 1 526 554 5 9 4 527 10 555 13 11 14 554 12 8 15 16 528 556 529 530 557 558 13 17 18 1 555 531 1 14 19 1 20 2 532 533 1 6 21 2 22 556 15 3 7 1 23 9 3 24 559 13 17 25 1 16 525 17 526 1 1 26 20 8 18 27 534 5 28 ...

result:

ok ok

Test #43:

score: 22

Accepted

time: 99ms

memory: 98180kb

input:

5
85
99108 97396
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
...

output:

48829
6615 1493 2509 16293 2446 1378 12727 2501 10823 25502 15971 7316 14309 4646 1488 13713 13836 44033 3447 9495 26767 22714 4967 20743 5833 24457 8894 5243 6548 33985 19473 7025 8281 13532 17397 81 7340 18021 15081 11750 14781 20181 3306 17569 14162 47413 10711 45500 566 244 14100 3716 46023 1602...

result:

ok ok

Test #44:

score: 22

Accepted

time: 75ms

memory: 85204kb

input:

5
221
97581 86531
1 2
1 3
1 4
4 5
5 6
1 7
4 8
4 9
7 10
2 11
2 12
2 13
9 14
10 15
13 16
4 17
12 18
10 19
16 20
17 21
6 22
18 23
8 24
17 25
22 26
16 27
22 28
8 29
8 30
11 31
21 32
23 33
19 34
9 35
25 36
10 37
1 38
7 39
38 40
38 41
6 42
35 43
36 44
20 45
20 46
16 47
22 48
21 49
43 50
17 51
17 52
39 53
...

output:

126
1 4 1 2 3 4 5 6 6 7 8 9 1 10 11 12 9 13 14 15 10 2 16 17 18 4 1 19 20 21 22 23 10 24 25 26 27 28 5 29 30 31 7 32 33 34 35 1 2 36 37 3 38 11 39 40 5 41 42 43 44 45 46 6 47 48 49 50 51 8 52 53 7 6 13 54 55 56 57 58 10 59 60 61 62 63 64 65 9 8 66 67 68 69 70 71 72 73 74 75 76 12 77 18 78 79 80 81 8...

result:

ok ok

Test #45:

score: 22

Accepted

time: 63ms

memory: 92348kb

input:

5
125
98543 89905
1 2
2 3
1 4
4 5
4 6
1 7
6 8
1 9
3 10
4 11
7 12
9 13
1 14
4 15
7 16
8 17
5 18
8 19
3 20
6 21
5 22
7 23
6 24
4 25
9 26
8 27
8 28
2 29
9 30
3 31
2 32
1 33
1 34
3 35
9 36
2 37
5 38
8 39
5 40
3 41
6 42
1 43
1 44
8 45
3 46
7 47
5 48
3 49
5 50
9 51
8 52
7 53
7 54
8 55
4 56
9 57
6 58
5 59
...

output:

10182
1 1 2 7 3 4 5 6 7 8 1 9 10 1 4 2 1 6 3 8 2 1 4 3 1 3 5 4 8 11 12 8 2 3 9 6 4 6 9 7 4 4 9 10 11 12 10 13 11 8 5 14 5 6 10 6 11 13 12 15 9 12 13 8 14 9 10 10 15 11 7 16 12 8 2 14 13 7 16 8 14 13 9 3 14 9 10 11 17 12 15 13 5 10 16 6 15 14 15 18 15 7 11 17 8 18 11 12 16 17 12 17 19 16 13 13 14 19 ...

result:

ok ok

Test #46:

score: 22

Accepted

time: 60ms

memory: 95364kb

input:

5
1256
83133 86248
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 5...

output:

31782
4472 1039 7847 16742 16644 24506 28185 11040 2802 5593 9864 27444 26883 11471 22261 14936 5158 2323 8978 28698 19727 24012 17356 12029 19708 20233 21472 18180 29700 9449 21908 11785 17934 13680 15117 12549 14901 14594 19584 3386 5105 15118 4727 11811 12039 24897 13846 2020 7902 1331 5924 20857...

result:

ok ok

Test #47:

score: 22

Accepted

time: 39ms

memory: 80672kb

input:

output:

4114
1 2 3 4 5 6 7 5 8 9 10 11 12 6 13 14 15 9 16 17 18 1 19 20 21 22 23 24 25 2 1 26 2 27 28 29 30 4 31 32 33 34 1 35 1 4 36 37 8 3 38 39 3 40 41 12 13 42 43 44 45 46 2 47 48 49 50 51 52 53 54 55 56 9 57 4 58 59 60 61 62 7 14 63 64 65 19 23 24 8 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 10 82...

result:

ok ok

Test #48:

score: 22

Accepted

time: 38ms

memory: 80308kb

input:

output:

2862
2368 1599 439 990 235 417 503 2518 1250 1260 545 141 380 1511 1834 1092 357 2294 418 1149 430 463 577 72 402 2749 2314 555 705 1383 2084 249 645 11 799 445 70 2833 1126 438 100 1585 120 1073 1038 593 379 1843 137 2150 2556 2194 194 19 2654 803 929 1855 336 1686 535 2050 2691 1966 1587 1551 2607...

result:

ok ok

Subtask #6:

score: 32

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

100%

Accepted

Test #49:

score: 32

Accepted

time: 286ms

memory: 177772kb

input:

6
178
497927 412086
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 ...

output:

120
62 5 23 18 58 3 2 83 52 62 60 54 25 7 79 5 66 11 75 93 19 88 14 31 55 90 60 44 72 15 112 4 6 56 79 96 34 69 18 91 105 49 11 10 14 16 78 85 8 42 72 62 47 50 71 68 103 7 4 5 63 106 5 22 80 13 18 1 3 70 58 3 26 58 29 64 3 16 94 26 7 71 57 21 29 24 19 53 89 66 34 32 57 92 37 77 18 65 33 74 12 67 38 ...

result:

ok ok

Test #50:

score: 32

Accepted

time: 481ms

memory: 178204kb

input:

6
3234
454553 464302
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

232572
31356 64071 111264 172334 45975 15337 124475 229823 42138 14770 37255 4463 216481 23766 32125 120409 59526 147317 4334 148386 105359 13625 130548 40204 3160 3311 37389 128001 59462 175158 124118 102426 46569 128292 32395 89098 186060 27424 85851 3563 7100 65174 57341 109482 68220 145206 22489...

result:

ok ok

Test #51:

score: 32

Accepted

time: 682ms

memory: 166080kb

input:

6
5593
417535 438611
1 2
1 3
1 4
1 5
1 6
1 7
4 8
2 9
1 10
8 11
9 12
12 13
10 14
11 15
14 16
15 17
7 18
6 19
19 20
3 21
20 22
22 23
23 24
16 25
24 26
26 27
25 28
18 29
13 30
27 31
21 32
5 33
30 34
31 35
32 36
34 37
17 38
33 39
38 40
40 41
28 42
36 43
42 44
29 45
37 46
43 47
44 48
35 49
47 50
39 51
50...

output:

347915
1 2 3 4 5 6 7 3221 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 84 27 28 29 30 31 32 33 2717 34 565 35 36 37 38 39 40 41 42 915 43 44 45 628 46 1022 47 48 49 50 51 951 52 53 54 55 56 57 58 59 60 61 62 3739 63 64 1436 1148 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 2726...

result:

ok ok

Test #52:

score: 32

Accepted

time: 361ms

memory: 135280kb

input:

6
13826
84978 124376
1 2
2 3
3 4
4 5
3 6
1 7
4 8
8 9
7 10
7 11
3 12
5 13
12 14
10 15
6 16
14 17
9 18
15 19
8 20
13 21
12 22
20 23
16 24
23 25
4 26
5 27
2 28
5 29
5 30
17 31
5 32
24 33
11 34
14 35
11 36
25 37
22 38
16 39
11 40
29 41
38 42
17 43
38 44
41 45
17 46
44 47
33 48
42 49
6 50
29 51
51 52
3 5...

output:

80099
1 17 1 2 63 68 79 3 187 1 4 205 392 462 5 1 534 4 587 2 6 7 8 600 9 652 3 10 676 745 4 824 962 1017 1097 1 1150 1322 11 148 12 1346 7 13 1447 1535 1557 1 14 1866 6 374 1940 1976 2149 2232 2245 2316 1 2433 15 2581 16 8 17 18 2654 19 20 10 2734 2740 2998 3095 3178 3348 21 22 3369 3576 3593 9 23 ...

result:

ok ok

Test #53:

score: 32

Accepted

time: 374ms

memory: 141156kb

input:

6
3480
135245 82221
1 2
1 3
1 4
1 5
1 6
4 7
3 8
5 9
2 10
6 11
1 12
11 13
13 14
14 15
8 16
10 17
12 18
16 19
7 20
19 21
18 22
20 23
15 24
23 25
24 26
26 27
17 28
22 29
29 30
9 31
31 32
21 33
33 34
25 35
30 36
27 37
37 38
38 39
39 40
36 41
40 42
35 43
34 44
42 45
32 46
43 47
47 48
44 49
45 50
28 51
50...

output:

8376
1 2 3 1693 3632 1824 4475 241 2124 175 2891 4923 2215 173 4 324 5986 5762 1571 2752 3244 1474 3077 4005 198 466 1389 10 5 390 3684 533 1675 4323 13 497 530 6 591 4549 7 8 544 2591 9 2474 303 2750 578 2541 714 3227 3072 10 5852 1977 5775 8006 2303 8282 2880 1502 464 6978 352 360 5470 8138 814 26...

result:

ok ok

Test #54:

score: 32

Accepted

time: 241ms

memory: 117844kb

input:

6
6213
156426 135199
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

62086
13676 46386 20634 18076 16297 36601 35499 54885 46903 7155 16282 12738 21208 6426 312 27742 18438 36632 14387 4974 26663 25261 4611 34377 31877 15497 42568 1915 34798 22748 11445 27590 19170 25600 41270 65 2611 45314 41927 58992 3166 1166 53939 35355 7543 25236 1042 36090 57050 8665 45641 1360...

result:

ok ok

Test #55:

score: 32

Accepted

time: 129ms

memory: 75604kb

input:

output:

604
1 2 478 3 1 1 4 1 8 6 5 2 483 6 6 7 9 10 11 484 485 8 9 3 10 2 11 12 12 3 13 14 15 13 16 3 17 2 4 3 5 18 483 14 15 16 19 17 18 7 3 1 1 19 2 7 20 21 20 21 320 486 22 487 22 23 4 6 23 24 25 26 9 27 24 28 484 488 25 29 7 489 30 26 4 27 28 2 443 31 9 32 33 490 34 35 29 1 36 37 30 38 39 1 4 31 32 443...

result:

ok ok

Test #56:

score: 32

Accepted

time: 126ms

memory: 73508kb

input:

output:

1521
1 2 3 5 4 5 6 1093 9 7 8 4 2 9 1094 10 11 12 13 6 8 1095 14 1096 15 10 1097 673 3 6 5 16 17 18 1 1094 1095 1 19 20 13 21 22 1096 23 24 1097 25 3 26 14 1098 27 1099 28 29 12 30 2 5 31 32 33 17 4 1 34 1100 16 35 19 8 1 1098 1101 9 36 1099 37 22 38 39 40 1100 6 41 42 1 1101 43 44 1 1 23 45 25 1102...

result:

ok ok

Test #57:

score: 32

Accepted

time: 128ms

memory: 75428kb

input:

output:

747
162 1 2 588 3 4 5 285 588 5 589 590 589 591 590 6 7 8 592 6 9 6 593 10 594 591 11 12 13 595 14 592 15 16 596 6 1 597 17 18 19 20 21 1 2 22 593 3 23 11 24 25 594 9 595 596 5 26 598 3 27 2 28 29 599 3 4 30 597 31 32 33 5 600 34 35 11 36 37 38 12 17 39 40 41 42 43 17 18 44 1 45 19 2 46 47 601 1 598...

result:

ok ok

Test #58:

score: 32

Accepted

time: 132ms

memory: 75656kb

input:

output:

344
4 2 1 2 3 4 6 5 7 6 10 7 8 9 15 10 5 11 12 13 14 15 17 4 23 16 17 18 19 29 9 20 21 44 46 22 52 23 24 70 72 25 86 91 26 27 28 93 29 97 30 31 32 33 34 35 36 108 109 37 38 120 39 40 41 128 6 143 144 145 146 11 42 43 44 147 148 149 150 45 151 152 1 16 46 47 48 153 154 1 49 50 51 17 52 53 54 55 56 57...

result:

ok ok

Test #59:

score: 32

Accepted

time: 145ms

memory: 75472kb

input:

output:

730
1 2 11 2 3 4 5 6 7 8 139 1 1 9 5 10 11 9 47 12 51 13 2 22 5 31 106 14 15 7 16 103 112 49 378 50 8 158 17 18 113 14 19 20 21 5 94 24 22 36 11 23 37 24 14 23 10 149 146 13 20 113 3 50 37 55 8 25 26 3 379 85 27 28 73 11 62 29 106 3 245 30 119 38 14 31 89 16 77 20 23 84 2 37 4 90 32 35 39 1 33 18 34...

result:

ok ok

Test #60:

score: 32

Accepted

time: 447ms

memory: 178656kb

input:

6
2736
454986 470122
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

204856
91426 159214 74324 11769 119810 161626 19906 5196 15127 105051 39453 124543 69261 63527 172614 106789 12258 35278 51902 93651 69498 33924 131589 62922 35943 64267 88958 1887 30000 52199 92366 68013 77403 118286 148420 30356 146831 85991 181170 9399 69914 16117 35627 989 93748 65908 82328 1923...

result:

ok ok