QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #71856 | #1785. 轻重边 | He_Ren | 100 ✓ | 839ms | 25636kb | C++17 | 3.4kb | 2023-01-12 02:01:52 | 2025-04-18 00:16:29 |
Judging History
This is the latest submission verdict.
- [2025-04-18 00:16:29]
- A successful hack was made. The test data has been updated.
- (/hack/1679)
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-01-12 02:01:52]
- Submitted
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5 + 5;
struct Data
{
int l,r,cnt;
Data(void){}
Data(int _l,int _r,int _cnt): l(_l), r(_r), cnt(_cnt) {}
};
inline Data operator + (const Data &p,const Data &q)
{
return Data(p.l, q.r, p.cnt + q.cnt - (p.r == q.l));
}
struct Segment_Tree
{
Data tree[MAXN<<2];
int tag[MAXN<<2], n;
#define ls(u) ((u)<<1)
#define rs(u) ((u)<<1|1)
#define lson(u) ls(u),l,mid
#define rson(u) rs(u),mid+1,r
inline void push_up(int u){ tree[u] = tree[ls(u)] + tree[rs(u)];}
inline void push_down(int u)
{
if(tag[u])
{
tree[ls(u)] = tree[rs(u)] = Data(tag[u], tag[u], 1);
tag[ls(u)] = tag[rs(u)] = tag[u];
tag[u] = 0;
}
}
void update(int u,int l,int r,int ql,int qr,int k)
{
if(ql<=l && r<=qr){ tree[u] = Data(k,k,1); tag[u] = k; return;}
push_down(u);
int mid = (l+r)>>1;
if(ql<=mid) update(lson(u),ql,qr,k);
if(mid<qr) update(rson(u),ql,qr,k);
push_up(u);
}
inline void update(int ql,int qr,int k){ update(1,1,n,ql,qr,k);}
Data query(int u,int l,int r,int ql,int qr)
{
if(ql<=l && r<=qr) return tree[u];
push_down(u);
int mid = (l+r)>>1;
if(ql<=mid && mid<qr) return query(lson(u),ql,qr) + query(rson(u),ql,qr);
return ql<=mid? query(lson(u),ql,qr): query(rson(u),ql,qr);
}
inline Data query(int ql,int qr){ return query(1,1,n,ql,qr);}
}tree;
vector<int> g[MAXN];
int anc[MAXN], dep[MAXN], siz[MAXN], son[MAXN];
void dfs_tree(int u,int fa)
{
anc[u] = fa; siz[u] = 1; son[u] = -1;
for(int i=0; i<(int)g[u].size(); ++i)
{
int v = g[u][i];
if(v == fa) continue;
dep[v] = dep[u] + 1;
dfs_tree(v,u);
siz[u] += siz[v];
if(son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v;
}
}
int dfn[MAXN], seq[MAXN], top[MAXN], cur_dfn = 0;
void dfs_dfn(int u,int fa,int tp)
{
top[u] = tp;
dfn[u] = ++cur_dfn; seq[dfn[u]] = u;
if(son[u] != -1) dfs_dfn(son[u], u, tp);
for(int i=0; i<(int)g[u].size(); ++i)
{
int v = g[u][i];
if(v == fa || v == son[u]) continue;
dfs_dfn(v,u,v);
}
}
inline int lca(int u,int v)
{
while(top[u] != top[v]) dep[top[u]] > dep[top[v]]? u = anc[top[u]]: v = anc[top[v]];
return dep[u] < dep[v]? u: v;
}
inline void update(int u,int v,int k)
{
while(top[u] != top[v])
tree.update(dfn[top[u]], dfn[u], k), u = anc[top[u]];
tree.update(dfn[v], dfn[u], k);
}
inline Data query(int u,int v)
{
if(top[u] == top[v]) return tree.query(dfn[v], dfn[u]);
Data res = tree.query(dfn[top[u]], dfn[u]);
u = anc[top[u]];
while(top[u] != top[v])
res = tree.query(dfn[top[u]], dfn[u]) + res, u = anc[top[u]];
return tree.query(dfn[v], dfn[u]) + res;
}
void solve(void)
{
int n,Q;
scanf("%d%d",&n,&Q);
for(int i=1; i<=n; ++i) g[i].clear();
for(int i=1; i<n; ++i)
{
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v); g[v].push_back(u);
}
cur_dfn = 0;
dfs_tree(1,0); dfs_dfn(1,0,1);
tree.n = n;
int ccnt = 0;
for(int i=1; i<=n; ++i)
tree.update(dfn[i], dfn[i], ++ccnt);
while(Q--)
{
int oper,u,v;
scanf("%d%d%d",&oper,&u,&v);
int uv = lca(u,v);
if(oper == 1)
update(u, uv, ++ccnt), update(v, uv, ccnt);
else
{
int k = dep[u] + dep[v] - 2 * dep[uv];
Data res = query(u, uv);
swap(res.l, res.r);
res = res + query(v, uv);
printf("%d\n",k - res.cnt + 1);
}
}
}
int main(void)
{
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 5
Accepted
time: 1ms
memory: 8088kb
input:
3 8 6 6 8 7 2 6 1 2 6 7 5 4 6 3 1 1 1 2 2 7 1 1 6 3 2 2 5 1 5 2 1 2 5 7 10 6 2 3 1 1 6 5 3 2 7 1 4 2 3 4 2 3 4 1 5 6 2 6 7 1 5 1 2 4 3 2 2 6 2 4 6 2 6 5 2 4 5 10 8 7 1 2 4 8 7 5 8 1 6 9 6 9 10 9 3 4 6 1 4 5 2 1 7 2 3 10 1 6 7 1 10 2 2 6 3 2 9 7 1 6 9
output:
2 0 0 0 0 1 0 0 2 2 1 0 1 2
result:
ok 14 lines
Test #2:
score: 5
Accepted
time: 0ms
memory: 10064kb
input:
3 10 10 4 9 3 7 9 6 8 9 5 8 1 8 10 1 10 7 2 4 1 9 5 2 2 4 1 10 3 2 3 4 1 4 9 1 9 8 2 7 4 1 8 2 1 1 10 2 4 6 10 10 7 4 2 4 9 10 8 9 7 1 7 6 3 2 9 2 10 5 2 4 1 1 8 1 1 5 2 1 1 9 1 10 6 1 10 4 2 1 6 2 1 2 1 10 5 2 7 6 10 10 1 9 8 6 7 1 6 2 5 3 8 3 4 6 7 5 5 10 2 8 10 1 7 3 1 7 2 1 9 3 2 7 5 2 6 5 1 7 6...
output:
0 3 2 1 0 1 1 1 0 1 2 2
result:
ok 12 lines
Test #3:
score: 5
Accepted
time: 16ms
memory: 10284kb
input:
3 4691 4033 141 4537 2326 1658 1170 2567 2602 2235 4073 3976 2976 4052 814 922 551 3848 1739 3392 3646 3990 1095 4575 2939 286 2927 1846 3333 818 3095 162 3761 2541 881 2634 3436 2861 4517 401 3702 438 2894 355 4395 304 4028 3919 1660 3426 2927 374 4673 99 2724 3034 616 3218 2760 4348 4631 3839 1218...
output:
9 1 12 0 0 11 12 29 39 11 40 13 13 26 0 23 8 70 41 12 15 24 28 21 57 11 13 25 69 15 58 8 21 38 25 59 60 51 38 20 83 9 45 83 45 6 18 20 22 28 23 57 24 0 27 51 25 24 24 38 30 45 0 32 28 27 46 36 18 50 19 20 48 32 29 20 42 35 47 24 13 34 34 32 0 49 12 28 22 21 78 39 16 10 33 30 29 33 30 45 33 36 23 31 ...
result:
ok 6741 lines
Test #4:
score: 5
Accepted
time: 11ms
memory: 10432kb
input:
3 3748 4382 1320 3727 1198 3101 2145 793 2375 2101 2862 2544 242 604 2744 134 2157 3398 429 3187 33 804 830 511 128 2441 2558 1603 3731 3161 1873 3697 2057 2553 394 635 1566 3413 1365 2416 3692 3338 762 3664 3474 2808 1357 914 1571 2884 2772 2389 840 1711 2275 2160 2324 2670 103 257 1317 28 2163 153...
output:
6 38 6 27 19 33 27 13 25 22 14 26 1 18 17 33 20 6 39 41 26 36 15 9 39 30 12 23 45 21 42 26 25 40 7 1 25 33 19 18 21 17 29 41 26 29 34 25 20 18 18 18 24 25 14 44 6 21 21 30 29 27 17 30 29 44 22 5 3 24 43 21 40 16 42 13 24 41 38 6 6 31 32 18 36 7 14 28 18 38 15 47 19 33 31 8 7 26 24 16 45 5 34 4 45 39...
result:
ok 6212 lines
Test #5:
score: 5
Accepted
time: 17ms
memory: 10376kb
input:
3 5000 5000 1819 180 3088 312 1963 2811 4857 4770 300 2152 4759 3872 245 4439 3874 3127 2479 1936 3765 1768 2194 2485 160 1992 1760 533 2113 2337 4701 252 2502 2391 1053 600 28 1932 4998 669 3996 2157 4481 4154 4240 4059 4421 266 4730 1363 2964 101 3238 3926 941 1276 1939 4154 784 3856 3871 3495 477...
output:
0 16 0 0 59 2 75 77 30 75 24 60 47 59 1 14 25 22 70 24 29 0 11 26 32 80 23 14 43 95 28 41 49 75 26 38 13 48 24 100 20 36 3 9 37 16 54 85 63 72 21 52 82 8 58 14 89 50 6 79 11 41 54 82 12 58 15 57 45 8 71 39 68 55 18 55 58 11 20 79 45 18 89 70 39 30 14 32 43 71 66 18 77 32 70 86 77 20 87 44 72 13 53 9...
result:
ok 7504 lines
Test #6:
score: 5
Accepted
time: 13ms
memory: 10608kb
input:
3 5000 5000 2595 2044 1369 2070 4147 3320 2661 3652 1198 2984 2636 1033 2431 3650 4461 3438 2156 2971 437 2848 1687 1625 2602 4656 2542 2423 1260 612 3556 516 4294 2516 3669 3420 274 2253 4238 1069 3642 1794 3586 252 2768 1582 4198 22 2335 155 3222 3159 2471 6 957 798 2693 4872 1874 4183 3128 374 5 ...
output:
0 56 19 21 35 31 58 43 71 9 59 5 23 37 38 10 33 28 17 100 44 21 38 4 19 33 71 2 46 49 26 10 46 23 29 38 68 53 40 59 54 46 8 60 56 22 41 55 33 72 28 38 31 79 47 53 26 45 22 45 77 39 16 25 23 79 55 15 23 82 12 11 21 29 69 46 48 27 32 39 24 19 34 85 31 26 83 32 43 71 80 17 51 80 105 68 33 26 69 40 42 4...
result:
ok 8263 lines
Test #7:
score: 5
Accepted
time: 191ms
memory: 21580kb
input:
3 80753 79382 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 51 ...
output:
0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 119073 lines
Test #8:
score: 5
Accepted
time: 264ms
memory: 25636kb
input:
3 100000 100000 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 5...
output:
1 1 0 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 149961 lines
Test #9:
score: 5
Accepted
time: 234ms
memory: 23160kb
input:
3 85306 96255 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 51 ...
output:
0 20929 1117 39620 30865 26113 28573 16622 51710 12826 65894 7348 60055 71547 3734 21494 36153 619 29407 23212 10079 18401 30621 20023 33453 3421 3412 1863 30525 37532 7448 13231 50073 11674 11952 23503 6022 5485 30126 8058 14680 41405 17046 8090 4234 48556 48720 27505 32307 58400 58330 71649 19722 ...
result:
ok 127775 lines
Test #10:
score: 5
Accepted
time: 285ms
memory: 24856kb
input:
3 100000 100000 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 5...
output:
24303 42249 4144 3055 698 32261 9589 36548 24443 53848 47026 24879 60517 60599 66694 730 67826 12460 60987 46524 56325 55782 19336 10349 24339 12330 29913 78906 30710 7266 20028 56241 35971 38209 1986 35413 5779 44484 51040 43662 48585 78430 62492 41972 2866 72696 42806 23409 54922 18465 23865 19911...
result:
ok 149908 lines
Test #11:
score: 5
Accepted
time: 409ms
memory: 20796kb
input:
3 97203 94161 44820 65179 65179 61439 61439 73263 73263 77468 77468 84098 84098 16816 16816 87458 87458 75540 75540 25930 25930 15686 15686 53399 53399 50620 50620 71205 71205 72887 72887 40025 40025 75694 75694 30817 30817 54444 54444 53761 53761 32609 32609 43392 43392 66768 66768 5020 5020 59550 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 147867 lines
Test #12:
score: 5
Accepted
time: 285ms
memory: 22556kb
input:
3 75542 80437 19963 55367 55367 4361 4361 33808 33808 18119 18119 1765 1765 6558 6558 20580 20580 74183 74183 16658 16658 4165 4165 29389 29389 70762 70762 64930 64930 11518 11518 58871 58871 40781 40781 60462 60462 38675 38675 2241 2241 12696 12696 37564 37564 33100 33100 72437 72437 45638 45638 15...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 136491 lines
Test #13:
score: 5
Accepted
time: 413ms
memory: 21708kb
input:
3 100000 100000 11698 62060 62060 5345 5345 19041 19041 6205 6205 9172 9172 22236 22236 63405 63405 75901 75901 51825 51825 75629 75629 6492 6492 36485 36485 77384 77384 54779 54779 58192 58192 75576 75576 60729 60729 68607 68607 4424 4424 19234 19234 63754 63754 95475 95475 6402 6402 57023 57023 89...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 166606 lines
Test #14:
score: 5
Accepted
time: 380ms
memory: 22348kb
input:
3 100000 100000 61704 48070 48070 82948 82948 8908 8908 98947 98947 86428 86428 82915 82915 51940 51940 83640 83640 64655 64655 37694 37694 17204 17204 16152 16152 34222 34222 63303 63303 18924 18924 16228 16228 76950 76950 37608 37608 75769 75769 7852 7852 83829 83829 57099 57099 49908 49908 16984 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 166524 lines
Test #15:
score: 5
Accepted
time: 72ms
memory: 11940kb
input:
3 16143 13827 2266 7230 7230 10028 10028 14162 14162 13128 13128 4201 4201 6762 6762 2379 2379 22 22 11312 11312 6945 6945 3012 3012 14651 14651 14057 14057 8400 8400 10591 10591 14094 14094 261 261 10274 10274 7514 7514 14695 14695 648 648 712 712 1377 1377 9916 9916 11801 11801 6939 6939 14820 148...
output:
16 11 2 17 17 31 24 10 51 43 32 7 16 0 2 43 6 29 22 5 56 22 22 48 0 8 12 21 31 28 49 20 8 28 25 13 25 38 36 20 4 6 37 1 16 25 1 26 4 13 29 17 46 27 18 44 15 27 52 23 15 55 46 15 10 19 52 34 1 24 30 35 10 43 34 15 23 16 13 15 39 35 3 25 5 16 60 23 22 30 34 21 40 6 52 13 15 14 33 31 25 16 11 11 1 19 3...
result:
ok 26693 lines
Test #16:
score: 5
Accepted
time: 59ms
memory: 10264kb
input:
3 20000 20000 19539 12265 12265 17534 17534 3954 3954 5924 5924 6333 6333 2247 2247 2198 2198 18380 18380 6704 6704 6466 6466 4334 4334 680 680 8984 8984 9068 9068 9292 9292 19855 19855 18513 18513 15340 15340 6641 6641 14302 14302 15898 15898 16810 16810 8968 8968 1871 1871 11736 11736 16886 16886 ...
output:
11 40 0 16 52 35 24 13 36 32 22 22 27 0 61 27 40 2 5 64 0 38 9 10 5 4 56 6 10 20 24 12 22 50 38 3 36 27 38 53 0 51 51 10 31 28 46 34 51 34 4 36 41 23 10 4 50 29 11 24 46 11 10 22 34 43 13 23 30 44 1 6 41 30 3 18 17 11 6 7 50 21 20 22 31 65 24 50 4 26 2 1 8 14 2 5 46 3 43 4 14 0 7 6 31 15 14 42 50 57...
result:
ok 33125 lines
Test #17:
score: 5
Accepted
time: 404ms
memory: 17100kb
input:
3 76695 67966 56425 31646 31646 59459 59459 37624 37624 57860 57860 65929 65929 4666 4666 51436 51436 9891 9891 12967 12967 13631 13631 43482 43482 28423 28423 43744 43744 29260 29260 74681 74681 5829 5829 54747 54747 42982 42982 8731 8731 34518 34518 64770 64770 39919 39919 32001 32001 66142 66142 ...
output:
1 18 50 21 6 22 7 26 8 8 44 42 17 13 15 17 7 0 20 39 10 37 10 26 40 43 3 11 10 17 24 4 8 22 23 43 41 24 14 5 22 32 35 5 14 8 26 7 12 28 48 58 32 5 7 33 1 15 33 8 22 16 27 17 32 44 27 44 1 8 56 51 49 9 51 2 35 42 13 19 9 59 3 26 45 32 44 54 24 4 8 56 53 17 19 39 8 39 18 14 11 39 11 1 15 2 40 13 58 34...
result:
ok 132245 lines
Test #18:
score: 5
Accepted
time: 405ms
memory: 19508kb
input:
3 88368 77279 30630 86625 86625 20534 20534 65929 65929 77511 77511 40182 40182 63591 63591 29184 29184 66661 66661 55108 55108 87420 87420 71371 71371 7396 7396 76428 76428 29032 29032 12480 12480 46843 46843 53896 53896 26905 26905 20769 20769 83597 83597 77572 77572 9339 9339 64901 64901 80992 80...
output:
13 28 17 16 25 28 24 52 14 28 39 31 6 5 11 19 6 21 12 46 1 4 20 9 28 5 29 10 21 29 0 7 12 27 27 41 52 41 41 3 52 25 4 37 33 3 3 37 18 37 19 3 42 48 53 14 14 3 12 10 16 1 37 27 38 11 7 19 8 24 18 9 5 41 41 25 56 39 1 64 2 5 36 34 27 26 55 19 45 9 16 25 10 19 11 39 8 20 37 34 18 6 50 4 10 15 55 22 7 8...
result:
ok 136450 lines
Test #19:
score: 5
Accepted
time: 483ms
memory: 21476kb
input:
3 100000 100000 78746 26777 26777 80762 80762 78780 78780 90725 90725 325 325 59763 59763 89996 89996 69707 69707 666 666 12511 12511 19026 19026 90674 90674 21918 21918 18930 18930 47467 47467 36299 36299 97733 97733 15682 15682 69920 69920 32575 32575 82734 82734 31361 31361 99748 99748 51727 5172...
output:
1 3 46 3 12 65 18 14 34 21 2 45 4 10 37 0 27 28 40 24 17 21 55 34 32 45 23 28 51 9 41 15 45 65 7 11 50 56 7 33 10 36 15 48 15 15 32 1 58 7 34 38 53 2 6 8 4 0 17 27 28 47 29 30 14 10 32 46 3 34 8 27 8 9 23 45 11 15 40 6 66 0 22 5 4 21 10 25 6 47 51 17 13 6 35 9 9 53 2 21 40 13 5 0 33 33 12 50 20 34 3...
result:
ok 166718 lines
Test #20:
score: 5
Accepted
time: 599ms
memory: 22232kb
input:
3 100000 100000 55651 6780 6780 23348 23348 7670 7670 58893 58893 79852 79852 61518 61518 20795 20795 62023 62023 93634 93634 37598 37598 84149 84149 19931 19931 98776 98776 31452 31452 3000 3000 92083 92083 69668 69668 52244 52244 41889 41889 96128 96128 8508 8508 32863 32863 12469 12469 20195 2019...
output:
9 12 20 10 34 24 45 4 13 25 13 15 3 6 18 30 8 31 25 55 22 13 44 21 17 8 8 29 6 32 25 32 4 8 30 62 6 29 20 3 7 14 6 35 29 39 31 6 30 5 0 19 11 36 40 52 27 22 39 35 45 42 39 23 29 13 38 29 13 22 9 30 17 32 54 14 38 14 8 39 45 53 37 27 36 6 6 24 19 26 8 23 10 28 29 23 8 25 6 18 25 34 48 9 1 13 15 11 9 ...
result:
ok 166789 lines
Extra Test #1:
score: 100
Accepted
time: 1ms
memory: 10120kb
input:
1 7 7 1 2 1 3 3 4 3 5 3 6 6 7 1 1 7 2 1 4 2 2 7 1 1 5 2 2 7 1 2 1 2 1 7
output:
1 3 2 1
result:
ok 4 lines
Extra Test #2:
score: 100
Accepted
time: 13ms
memory: 10424kb
input:
3 4982 4379 1987 588 636 1884 426 4443 2903 1092 827 4303 2234 1429 3767 399 3897 4290 2940 1259 2611 3501 4531 225 1129 899 2947 1533 3913 2674 1686 2892 654 4918 2473 340 1828 2435 3813 1347 2550 4049 465 3925 999 4622 1355 578 106 967 800 1276 1128 2595 4666 580 1550 4965 4517 2982 1652 223 1092 ...
output:
31 6 8 1 16 44 28 28 24 10 37 41 36 9 10 33 1 22 19 48 46 13 15 20 0 37 41 40 15 32 23 41 1 36 14 39 8 7 17 37 41 65 66 3 72 30 25 21 54 29 36 47 18 8 49 57 32 68 34 27 32 13 6 45 26 12 26 41 27 44 33 56 44 58 42 26 30 21 24 15 39 37 29 20 33 57 28 29 65 52 52 43 45 35 21 17 36 61 51 43 13 47 28 32 ...
result:
ok 6354 lines
Extra Test #3:
score: 100
Accepted
time: 229ms
memory: 24104kb
input:
3 81650 72756 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 51 ...
output:
0 46683 68542 12939 14393 27585 37647 635 38855 49099 8609 72677 39693 5913 26734 1606 13891 25518 8632 24844 8669 38988 57930 31300 27135 24637 29496 2684 43339 33975 15132 38906 11591 19780 45289 21107 22364 25943 22591 46425 62013 12972 8017 3126 14543 28729 36122 35000 3702 11721 2193 49397 2086...
result:
ok 116737 lines
Extra Test #4:
score: 100
Accepted
time: 444ms
memory: 16396kb
input:
3 80971 88027 27777 24 70730 28435 71811 76091 76586 29248 32955 59960 53189 61901 17124 34599 76813 32510 60382 55875 54469 19084 44493 36764 16490 63051 74400 74228 40044 64236 57013 21386 12485 51286 56623 75953 27465 35685 78480 588 74667 55448 74690 67659 13404 6049 73546 65118 60211 70066 3745...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 137274 lines
Extra Test #5:
score: 100
Accepted
time: 494ms
memory: 19496kb
input:
3 88209 90221 45321 23072 23072 55423 55423 74437 74437 55412 55412 15764 15764 36790 36790 28571 28571 6887 6887 15847 15847 10533 10533 60377 60377 26907 26907 57174 57174 46443 46443 84200 84200 19152 19152 43584 43584 19721 19721 46065 46065 19824 19824 57377 57377 85836 85836 76375 76375 66580 ...
output:
0 15 48 36 7 16 20 14 3 4 49 51 41 20 0 0 37 2 52 19 5 17 48 6 4 21 48 28 6 12 20 4 38 30 18 46 52 10 12 4 17 33 12 12 6 12 13 4 7 12 25 43 2 17 36 10 8 27 18 21 7 59 0 24 9 57 36 25 38 47 40 3 5 35 41 23 36 31 17 33 36 53 15 39 16 33 15 51 11 14 46 31 24 11 29 35 49 11 34 5 19 19 10 5 37 31 20 21 8...
result:
ok 150459 lines
Extra Test #6:
score: 100
Accepted
time: 839ms
memory: 16032kb
input:
3 100000 100000 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 11 5 12 6 13 6 14 7 15 7 16 8 17 8 18 9 19 9 20 10 21 10 22 11 23 11 24 12 25 12 26 13 27 13 28 14 29 14 30 15 31 15 32 16 33 16 34 17 35 17 36 18 37 18 38 19 39 19 40 20 41 20 42 21 43 21 44 22 45 22 46 23 47 23 48 24 49 24 50 25 51 25 52 26 53 2...
output:
result:
ok 0 lines