QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#266542 | #7869. 建设终末树 | zhouhuanyi | 90 | 2480ms | 759336kb | C++14 | 6.1kb | 2023-11-26 15:17:02 | 2023-11-26 15:17:03 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<bitset>
#define N 2000
#define M 16000000
#define K 30000000
#define S 11
#define W 4000000
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int x,y;
};
reads tong[N+1],st[N+1];
struct node
{
int v,nxt;
};
node edge[K+1];
int n,m,q,maxn,top,lengt,lengs,lengths,cater,len,depth[N+1],wrt[W+1],dfnt[N+1],sz[N+1],lca[N+1][N+1],lg[N+1],head[M+1],length,leng,cst[N+1],cnt[N+1],a[N+1][N+1],b[N+1],c[N+1],sfa[N+1][N+1],fa[N+1][S+1],A[N+1],B[N+1],dfn[M+1],low[M+1],stk[M+1],belong[M+1],ans[N+1],ST[N+1][N+1][S+1],rt[S+1][W+1],rts[W+1],dis[N+1][N+1],scnt;
bool usedt[M+1],vis[M+1],cl[N+1];
vector<int>E[N+1];
bitset<N+1>Bs;
int F(int x,int y)
{
return (x-1)*n+y;
}
int find(int k,int x)
{
if (rt[k][x]==x) return x;
return rt[k][x]=find(k,rt[k][x]);
}
void unionn(int k,int x,int y)
{
rt[k][find(k,x)]=find(k,y);
return;
}
int finds(int x)
{
if (rts[x]==x) return x;
return rts[x]=finds(rts[x]);
}
inline void unionns(int x,int y)
{
if (scnt>=4000000) return;
x=finds(x),y=finds(y);
if (x!=y) rts[x]=y,scnt++;
return;
}
void add(int x,int y)
{
E[x].push_back(y),E[y].push_back(x);
return;
}
void add_edge(int x,int y)
{
edge[++len]=(node){y,head[x]},head[x]=len;
return;
}
bool LENG(int x,int y)
{
return dfnt[x]<=dfnt[y]&&dfnt[y]<=dfnt[x]+sz[x]-1;
}
bool LENGS(int x,int y,int z)
{
return dis[x][y]+dis[y][z]==dis[x][z];
}
void dfs(int x)
{
dfnt[x]=++lengt,sz[x]=1;
for (int i=0;i<E[x].size();++i)
if (!dfnt[E[x][i]])
depth[E[x][i]]=depth[x]+1,fa[E[x][i]][0]=sfa[E[x][i]][1]=x,dfs(E[x][i]),st[++lengths]=(reads){x,E[x][i]},sz[x]+=sz[E[x][i]];
return;
}
void dfs2(int x,int y)
{
if (LENG(x,y)) lca[y][x]=x;
for (int i=0;i<E[x].size();++i)
if (fa[E[x][i]][0]==x)
lca[y][E[x][i]]=lca[y][x],dfs2(E[x][i],y);
return;
}
void tarjan(int x)
{
dfn[x]=low[x]=++lengs,usedt[x]=1,stk[++top]=x;
for (int i=head[x];i>0;i=edge[i].nxt)
{
if (!dfn[edge[i].v]) tarjan(edge[i].v),low[x]=min(low[x],low[edge[i].v]);
else if (usedt[edge[i].v]) low[x]=min(low[x],dfn[edge[i].v]);
}
if (dfn[x]==low[x])
{
++cater;
while (stk[top]!=x) belong[stk[top]]=cater,usedt[stk[top]]=0,top--;
belong[stk[top]]=cater,usedt[stk[top]]=0,top--;
}
return;
}
void adder(int d1,int d2,int x,int y)
{
int z=lca[x][y],d;
if (dis[x][y]<=20)
{
while (x!=z)
{
if (!Bs[x]) unionns(F(d1,x),F(d2,x)),Bs[x]=1;
x=fa[x][0];
}
while (y!=z)
{
if (!Bs[y]) unionns(F(d1,y),F(d2,y)),Bs[y]=1;
y=fa[y][0];
}
}
else
{
if (x!=z) d=lg[depth[x]-depth[z]],unionn(d,F(d1,x),F(d2,x)),unionn(d,F(d1,sfa[x][depth[x]-depth[z]-(1<<d)]),F(d2,sfa[x][depth[x]-depth[z]-(1<<d)]));
if (y!=z) d=lg[depth[y]-depth[z]],unionn(d,F(d1,y),F(d2,y)),unionn(d,F(d1,sfa[y][depth[y]-depth[z]-(1<<d)]),F(d2,sfa[y][depth[y]-depth[z]-(1<<d)]));
}
return;
}
int main()
{
int t1,t2,x,y,d;
bool op;
for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
n=read(),m=read(),q=read(),leng=(n*m)<<1;
for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
depth[1]=1,dfs(1);
for (int i=1;i<=n;++i) maxn=max(maxn,depth[i]);
for (int i=1;i<=lg[maxn];++i)
for (int j=1;j<=n;++j)
fa[j][i]=fa[fa[j][i-1]][i-1];
for (int i=1;i<=n;++i)
{
sfa[i][0]=i;
for (int j=1;j<=n;++j) sfa[i][j]=fa[sfa[i][j-1]][0];
}
for (int i=1;i<=n;++i) dfs2(1,i);
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
dis[i][j]=depth[i]+depth[j]-(depth[lca[i][j]]<<1);
for (int i=1;i<=m;++i)
{
cst[i]=read();
for (int j=1;j<=cst[i];++j) a[i][j]=read();
}
for (int i=1;i<=n*m;++i) rts[i]=i;
for (int i=0;i<=lg[maxn];++i)
for (int j=1;j<=n*m;++j)
rt[i][j]=j;
for (int i=1;i<=q;++i)
{
t1=read();
for (int j=1;j<=t1;++j) b[j]=read(),cnt[b[j]]=1;
t2=read();
for (int j=1;j<=t2;++j) c[j]=read();
for (int j=2;j<=t1;++j)
{
vis[j]=1;
for (int k=2;k<=j-1;++k)
if (LENGS(b[1],b[j],b[k]))
vis[j]=0;
}
for (int j=1;j<=t2-1;++j)
{
Bs.reset();
for (int k=2;k<=t1;++k)
if (vis[k])
adder(c[j],c[j+1],b[1],b[k]);
}
}
for (int i=lg[maxn];i>=1;--i)
for (int j=1;j<=m;++j)
for (int k=1;k<=n;++k)
if (F(j,k)!=find(i,F(j,k)))
{
unionn(i-1,F(j,k),find(i,F(j,k)));
if (fa[k][i-1])
{
d=find(i,F(j,k));
if (fa[(d-1)%n+1][i-1]) unionn(i-1,F(j,fa[k][i-1]),find(i,F((d+n-1)/n,fa[(d-1)%n+1][i-1])));
}
}
for (int i=1;i<=n*m;++i)
if (finds(i)!=i)
unionn(0,finds(i),i);
for (int i=1;i<=n*m;++i) wrt[i]=find(0,i);
for (int i=1;i<=m;++i)
{
for (int j=1;j<=n;++j) cnt[j]=0;
for (int j=1;j<=cst[i];++j) cnt[a[i][j]]=1;
for (int j=1;j<=lengths;++j) cnt[st[j].x]+=cnt[st[j].y];
for (int j=2;j<=n;++j)
{
if (!cnt[j]) add_edge(wrt[F(i,j)],wrt[F(i,j)]+n*m);
if (cnt[j]==cst[i]) add_edge(wrt[F(i,j)]+n*m,wrt[F(i,j)]);
}
for (int j=1;j<=n;++j)
{
length=0;
if (j!=1) tong[++length]=(reads){wrt[F(i,j)]+n*m,wrt[F(i,j)]};
for (int k=0;k<E[j].size();++k)
if (fa[E[j][k]][0]==j)
tong[++length]=(reads){wrt[F(i,E[j][k])],wrt[F(i,E[j][k])]+n*m};
A[1]=tong[1].y;
for (int k=2;k<=length;++k) A[k]=++leng,add_edge(A[k],A[k-1]),add_edge(A[k],tong[k].y);
B[length]=tong[length].y;
for (int k=length-1;k>=1;--k) B[k]=++leng,add_edge(B[k],B[k+1]),add_edge(B[k],tong[k].y);
for (int k=1;k<=length;++k)
{
if (k!=1) add_edge(tong[k].x,A[k-1]);
if (k!=length) add_edge(tong[k].x,B[k+1]);
}
}
}
for (int i=1;i<=leng;++i)
if (!dfn[i])
tarjan(i);
for (int i=1;i<=m;++i)
for (int j=1;j<=n;++j)
if (belong[wrt[F(i,j)]]==belong[wrt[F(i,j)]+n*m])
{
puts("-1");
return 0;
}
for (int i=1;i<=m;++i)
{
for (int j=1;j<=n;++j) cl[j]=belong[wrt[F(i,j)]]>belong[wrt[F(i,j)]+n*m];
for (int j=1;j<=n;++j)
{
op=1;
for (int k=0;k<E[j].size();++k)
if (fa[E[j][k]][0]==j)
op&=cl[E[j][k]];
if (j!=1) op&=(!cl[j]);
if (op) ans[i]=j;
}
}
for (int i=1;i<=m;++i) printf("%d ",ans[i]);
puts("");
return 0;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1494ms
memory: 593280kb
input:
1999 1998 27199 1368 233 233 617 233 388 233 1127 1905 233 907 233 233 40 233 1325 233 1940 1739 233 501 233 233 33 735 233 233 283 233 1427 1992 233 233 632 233 685 1188 233 648 233 233 344 233 1321 986 233 848 233 770 233 256 233 164 233 936 233 1206 233 53 233 1054 233 1430 233 1714 233 86 233 11...
output:
1294 1264 1662 1036 1036 1450 899 641 906 1005 1005 1683 1547 1547 878 1654 1630 1085 503 1338 1654 641 1388 1388 878 1904 1547 1036 1662 1388 906 906 1662 987 878 1683 467 815 1662 1909 1388 1654 899 9 1338 1450 1909 1610 1671 899 1671 181 1036 906 987 467 899 815 705 705 641 1547 899 1904 1662 154...
result:
ok Accepted.
Test #2:
score: 0
Accepted
time: 1447ms
memory: 590940kb
input:
1998 2000 25224 1860 579 579 1400 720 579 579 1379 579 1628 579 69 579 400 1941 579 579 811 579 252 1816 579 579 1786 579 335 579 1467 1480 579 98 579 579 755 579 55 579 1059 650 579 579 1846 1437 579 579 861 338 579 1687 579 579 1248 579 1827 579 1169 1613 579 579 1494 579 1502 1090 579 612 579 579...
output:
219 942 158 865 295 1458 219 158 1855 906 557 295 1855 1545 422 557 1545 937 1855 906 634 872 872 1442 1458 1450 158 239 872 295 422 942 295 937 1689 1213 295 634 219 1183 1855 1213 443 1450 1458 872 1117 488 239 1577 698 865 422 219 1699 443 1823 1183 1689 634 488 1117 1545 323 1458 323 1458 443 90...
result:
ok Accepted.
Test #3:
score: 0
Accepted
time: 1674ms
memory: 590720kb
input:
1999 1999 17845 621 466 466 254 1001 466 466 326 466 779 466 40 527 466 466 1130 466 504 466 1136 466 73 466 1156 963 466 466 1095 247 466 466 1146 1361 466 466 1340 774 466 466 422 466 1649 466 948 466 1803 466 1765 686 466 466 551 612 466 608 466 318 466 466 132 1215 466 466 310 1962 466 466 1999 ...
output:
1046 842 80 647 1792 1241 1483 904 981 1483 1046 1732 904 80 647 544 1085 904 1399 1345 1792 647 904 647 1483 1345 594 1732 380 544 1792 1471 1792 586 1046 1120 544 1478 1399 1792 1732 380 1345 1190 1824 1046 594 647 647 904 1792 1732 380 1732 1478 1085 1120 1860 586 1013 1824 1471 981 1995 1190 147...
result:
ok Accepted.
Test #4:
score: 0
Accepted
time: 1482ms
memory: 589068kb
input:
1999 1999 23606 1568 1784 784 1568 1253 1568 1568 869 1568 1404 1601 1568 262 1568 1661 1568 1568 335 1839 1568 1568 208 1154 1568 1568 400 1576 1568 1112 1568 187 1568 1568 1370 1568 1451 1568 293 1568 344 1037 1568 13 1568 1568 1240 518 1568 1568 1912 1121 1568 1005 1568 1568 887 1510 1568 1568 71...
output:
-1
result:
ok Accepted.
Test #5:
score: 0
Accepted
time: 1659ms
memory: 588424kb
input:
1998 1998 17047 512 545 545 1651 497 545 545 1154 545 1847 545 1201 898 545 1304 545 545 915 495 545 545 71 1361 545 545 1508 1070 545 545 221 545 593 1612 545 545 1011 545 13 913 545 1659 545 545 1557 545 1425 545 1065 1673 545 545 170 1602 545 680 545 982 545 1600 545 545 1784 678 545 1484 545 191...
output:
-1
result:
ok Accepted.
Test #6:
score: 0
Accepted
time: 1370ms
memory: 591588kb
input:
2000 1999 30204 1179 128 586 1179 1179 1556 1179 330 1412 1179 83 1179 147 1179 636 1179 1179 1584 1429 1179 212 1179 1179 1724 19 1179 1179 160 1179 1326 964 1179 1179 624 1179 1498 1137 1179 442 1179 1179 1027 1179 309 1179 1767 1179 721 198 1179 899 1179 211 1179 1179 1740 1746 1179 1179 828 568 ...
output:
1987 49 881 880 1837 47 627 89 49 1159 1896 49 1671 627 727 881 639 49 1837 737 49 1528 1671 1226 627 727 1837 608 1585 1933 737 737 1837 842 880 1755 47 28 1755 28 1671 880 28 1387 1528 608 608 1159 1755 1154 1249 639 1528 371 1987 47 881 1243 842 639 637 1154 1528 49 627 1243 1226 1528 637 1159 18...
result:
ok Accepted.
Test #7:
score: 0
Accepted
time: 1272ms
memory: 606028kb
input:
1999 1998 32159 467 1459 467 522 467 1297 467 1095 1751 467 1347 467 1771 467 1939 467 467 589 467 782 467 1947 11 467 467 1008 1841 467 467 615 467 1837 467 999 467 1674 572 467 1204 467 926 467 659 467 1579 467 467 1663 533 467 467 491 996 467 467 1355 467 596 530 467 467 1205 642 467 676 467 1206...
output:
-1
result:
ok Accepted.
Subtask #2:
score: 15
Accepted
Test #8:
score: 15
Accepted
time: 0ms
memory: 32328kb
input:
10 10 8 4 2 2 9 6 9 8 7 4 10 7 2 5 2 2 1 5 3 3 10 7 2 2 10 2 2 4 10 2 10 4 2 8 2 2 4 10 1 8 2 2 10 1 1 1 10 2 10 9 3 10 3 4 2 7 1 3 10 6 3 2 4 8 2 3 2 4 2 9 4 6 2 5 7 2 3 9 2 2 1 4 10 6 8 5 4 10 6 1 2 2 1 4 2 7 5 2 5 3 2 8 3
output:
10 10 10 10 2 10 8 2 1 10
result:
ok Accepted.
Test #9:
score: 0
Accepted
time: 0ms
memory: 32368kb
input:
10 10 9 9 10 3 5 2 3 9 2 2 6 1 3 8 5 1 7 6 4 1 7 1 8 2 10 2 4 8 5 1 2 2 10 9 2 2 7 1 8 4 1 8 5 2 2 10 6 4 9 2 4 3 2 3 10 2 5 3 2 8 3 2 8 5 2 5 3 2 6 5 2 5 9 2 9 3 2 9 8 2 1 8 3 7 1 6 2 2 8 2 10 2 3 8 1 4 2 9 5 3 1 6 8 3 9 4 3 2 1 7
output:
7 8 9 2 9 3 8 3 9 4
result:
ok Accepted.
Test #10:
score: 0
Accepted
time: 0ms
memory: 34408kb
input:
10 10 8 7 1 3 2 6 1 2 1 3 5 10 8 4 7 9 2 6 10 1 9 2 3 5 2 10 8 3 9 1 5 1 9 2 1 8 1 10 4 2 7 9 3 3 9 3 6 3 1 9 3 3 3 1 2 3 8 2 9 2 1 9 2 8 9 2 4 2 3 2 8 9 3 4 9 6 3 7 3 6 2 7 10 2 5 8 2 5 9 2 1 5 3 9 7 1 2 9 4 3 8 3 7 3 7 6 3
output:
9 5 10 2 9 10 10 3 3 3
result:
ok Accepted.
Test #11:
score: 0
Accepted
time: 0ms
memory: 32052kb
input:
10 10 6 8 1 3 10 6 1 9 2 8 5 3 7 9 7 6 4 6 3 2 1 6 3 6 10 3 1 8 4 10 1 4 3 3 3 1 6 3 1 4 10 2 9 2 2 9 2 3 6 1 4 2 7 10 3 3 2 9 3 3 4 6 5 4 8 10 5 9 5 5 6 4 9 1 2 5 9 4 2 6 5 10 3 7 3 8 3 1 9 2 3 2 8 9 2 10 2 4 10 5 3 2 3 6 2 10
output:
-1
result:
ok Accepted.
Test #12:
score: 0
Accepted
time: 0ms
memory: 32368kb
input:
10 10 9 1 7 7 5 7 8 3 7 7 10 4 7 7 9 6 7 2 7 3 6 3 9 3 8 2 4 6 2 7 5 3 6 8 3 4 5 10 4 6 4 10 9 7 5 10 4 6 9 8 1 6 8 9 4 10 5 2 3 4 5 1 7 7 8 5 1 10 9 6 2 8 7 2 3 7 2 6 2 2 3 6 3 3 9 2 2 10 1 2 8 1 2 8 5 2 9 5 2 7 3 2 5 3 3 2 10 8 2 5 8 2 1 3 2 8 4 3 4 5 6 2 9 2 2 10 9 3 3 8 9
output:
7 2 2 7 7 7 2 7 7 7
result:
ok Accepted.
Test #13:
score: 0
Accepted
time: 0ms
memory: 30500kb
input:
10 10 6 4 9 8 4 4 7 3 4 5 4 2 4 4 6 1 4 10 4 9 8 1 6 4 9 10 5 3 2 5 4 2 10 7 3 2 4 6 2 6 4 8 2 6 10 5 3 9 1 8 8 7 9 10 6 5 3 2 1 8 7 8 10 5 2 1 9 3 8 5 10 7 6 2 9 8 3 9 10 5 7 1 8 9 3 2 6 6 3 2 6 10 5 7 3 5 2 4 2 10 4 4 10 6 8 2 3 10 5 2 4 3 1 8 5 2 6 9 3 7 4 10 6 8 9 7 3 6 1 4 3 8 7 2 3 5 10 2 2 5 ...
output:
2 4 4 4 9 2 2 2 4 4
result:
ok Accepted.
Test #14:
score: 0
Accepted
time: 0ms
memory: 30316kb
input:
10 10 7 10 6 10 4 2 10 8 10 10 1 5 10 3 10 7 10 9 10 5 8 1 3 5 6 10 2 10 8 5 7 9 3 6 4 1 7 4 8 6 10 3 5 9 2 1 10 7 7 6 10 8 4 1 9 1 5 9 9 4 6 10 1 7 2 3 5 10 6 4 3 9 1 5 8 7 2 10 2 8 2 8 6 1 3 5 7 4 8 9 3 8 5 4 3 10 5 4 2 10 4 3 4 2 10 3 6 7 1 3 4 10 5 2 6 3 2 7 2 4 8 7 6 4 3 8 3 9 4 10 8 4 5 3 10 2...
output:
10 7 3 10 10 5 10 2 10 10
result:
ok Accepted.
Test #15:
score: 0
Accepted
time: 2ms
memory: 34596kb
input:
10 10 9 8 7 5 3 1 8 7 6 10 4 3 6 1 2 5 9 9 4 5 7 6 9 1 10 3 10 5 9 2 9 6 2 3 4 5 10 6 5 4 3 3 9 3 8 4 3 8 2 10 3 8 4 2 5 3 9 10 8 2 1 5 2 5 7 2 7 4 2 10 7 2 7 9 2 6 5 2 8 1 2 8 1 2 3 5 2 3 10 4 5 8 3 7 3 2 4 5 2 7 5 3 5 1 2 2 1 6 2 2 10 2 8 4 2 2 8 2 7 1
output:
10 5 5 5 5 5 5 5 5 5
result:
ok Accepted.
Test #16:
score: 0
Accepted
time: 0ms
memory: 32148kb
input:
10 10 9 2 7 1 8 2 5 9 4 5 3 10 7 4 6 10 8 6 1 2 7 5 4 1 4 10 9 2 1 2 5 10 9 4 2 7 3 1 9 4 2 8 9 4 6 8 3 2 2 8 1 3 2 1 9 4 5 8 9 4 2 9 10 2 1 7 2 10 8 2 7 8 2 3 10 2 7 6 2 8 6 2 5 10 2 6 2 2 5 10 3 5 9 8 2 4 10 2 1 5 2 2 9 2 5 7 3 3 10 1 3 8 4 5 3 5 10 9
output:
-1
result:
ok Accepted.
Test #17:
score: 0
Accepted
time: 0ms
memory: 34384kb
input:
10 10 6 8 10 3 5 4 1 9 6 7 10 7 9 2 8 3 1 4 6 1 1 2 10 9 3 3 6 2 2 8 10 2 10 7 2 8 7 5 9 4 3 10 5 3 8 9 10 1 7 2 2 10 3 4 1 5 3 10 9 5 3 1 9 10 3 6 4 10 5 9 6 1 2 8 4 4 2 5 3 2 4 7 3 9 2 4 3 7 1 3 4 5 8 2 4 4 3 10 1 9 3 10 8 3
output:
1 10 10 10 10 10 10 10 7 10
result:
ok Accepted.
Test #18:
score: 0
Accepted
time: 0ms
memory: 34408kb
input:
10 10 8 3 4 2 8 1 4 1 9 7 5 7 6 5 8 6 10 10 9 2 10 2 3 10 1 2 4 8 5 7 1 2 10 2 1 10 4 1 9 8 5 6 4 8 6 5 2 9 2 1 9 4 7 1 9 2 6 10 2 4 3 9 8 2 9 4 3 1 4 2 2 7 4 3 6 8 7 2 7 8 2 10 7 3 7 3 1 3 2 9 1 3 10 1 3 2 4 1 3 8 5 6 2 4 9 2 8 1 2 9 2 3 3 6 2 3 6 7 8
output:
2 2 8 2 10 9 9 9 8 7
result:
ok Accepted.
Subtask #3:
score: 20
Accepted
Test #19:
score: 20
Accepted
time: 78ms
memory: 100208kb
input:
500 498 5000 60 409 462 125 461 410 42 178 133 372 137 265 358 27 450 294 45 454 76 405 132 118 333 331 365 230 114 218 112 377 49 429 60 299 488 95 85 362 89 33 426 308 427 198 468 481 289 363 195 430 61 21 162 55 12 487 395 85 79 475 391 215 244 351 331 43 452 186 247 271 224 390 206 347 447 165 9...
output:
498 368 6 72 163 77 212 74 6 269 322 74 74 359 243 48 373 402 253 1 500 71 184 361 455 36 104 235 25 390 305 390 469 369 74 309 415 133 239 429 231 425 74 389 47 429 235 74 200 235 341 253 275 174 1 378 452 74 29 485 266 213 4 47 1 21 479 342 390 375 207 365 235 472 378 253 435 92 402 350 431 322 10...
result:
ok Accepted.
Test #20:
score: 0
Accepted
time: 67ms
memory: 100548kb
input:
500 500 5000 297 429 444 310 304 235 470 8 33 395 174 34 276 320 298 478 149 117 400 211 118 399 448 268 446 484 268 180 465 471 68 443 33 358 256 431 490 452 110 389 304 418 286 219 498 16 416 376 495 173 408 138 473 228 317 199 344 279 31 469 159 16 377 397 492 402 308 107 461 11 332 105 377 77 31...
output:
39 252 124 376 313 200 48 31 336 117 179 31 481 203 415 380 65 292 114 244 60 6 15 60 357 441 370 279 296 500 41 65 44 133 422 463 65 179 423 79 446 469 405 83 357 376 472 65 223 371 354 265 481 280 377 74 87 70 171 481 436 471 203 163 237 409 65 13 114 280 249 321 65 481 13 416 348 110 357 235 306 ...
result:
ok Accepted.
Test #21:
score: 0
Accepted
time: 89ms
memory: 102276kb
input:
499 498 5000 28 246 54 26 13 312 346 225 377 80 274 410 352 446 394 386 204 453 54 355 337 480 313 263 90 395 388 61 193 71 213 265 125 121 65 120 154 216 331 206 475 413 263 332 322 306 75 290 335 222 149 360 89 139 52 10 91 132 202 88 211 106 205 422 19 467 250 156 382 223 161 486 4 8 495 16 64 12...
output:
147 176 407 490 57 147 62 438 354 405 442 225 434 33 117 57 269 136 57 211 369 176 442 438 441 47 24 221 98 405 277 198 375 172 136 6 475 57 314 62 377 166 57 107 305 200 344 57 229 136 71 200 10 369 78 301 6 57 221 200 438 172 48 358 458 21 7 395 254 455 133 405 274 200 298 412 117 200 200 355 342 ...
result:
ok Accepted.
Test #22:
score: 0
Accepted
time: 84ms
memory: 104304kb
input:
499 500 5000 71 225 374 470 413 420 422 368 357 141 479 360 172 237 21 40 16 386 434 274 188 207 249 16 9 259 152 63 488 264 166 467 51 70 90 417 209 411 43 101 102 206 320 29 110 408 182 333 115 394 138 458 29 296 73 241 392 145 235 428 197 114 271 125 131 401 122 377 215 252 186 253 38 309 11 491 ...
output:
66 299 375 188 163 22 391 82 378 357 4 497 260 82 188 378 82 82 260 378 220 4 220 363 378 4 390 363 260 163 323 82 391 497 357 463 295 363 82 66 21 497 91 82 497 390 91 497 220 497 375 91 378 22 390 295 118 93 260 284 497 82 22 91 463 375 463 497 22 21 391 93 21 299 263 21 4 22 463 82 391 497 22 263...
result:
ok Accepted.
Test #23:
score: 0
Accepted
time: 81ms
memory: 102324kb
input:
498 498 5000 181 300 371 226 361 224 82 101 233 476 366 273 212 240 90 169 488 477 22 374 164 369 276 390 350 61 101 165 331 274 72 325 371 190 472 404 250 449 179 451 64 153 447 267 97 24 495 168 139 170 203 407 493 225 413 216 29 490 306 332 257 309 43 279 189 94 294 287 297 319 289 406 221 338 74...
output:
178 489 439 71 71 326 44 448 270 71 274 8 63 145 8 71 96 326 274 178 109 437 491 391 437 326 96 140 63 343 270 437 439 489 274 224 178 491 324 481 448 270 391 8 251 489 437 274 491 97 473 124 8 97 343 491 8 44 473 124 491 63 391 178 489 97 448 343 489 324 448 481 481 439 489 489 489 178 437 391 71 2...
result:
ok Accepted.
Test #24:
score: 0
Accepted
time: 85ms
memory: 106468kb
input:
498 499 5000 49 110 380 351 80 59 60 4 378 224 383 28 95 381 220 227 287 440 251 493 278 388 157 339 489 377 98 308 122 403 267 47 109 207 140 31 461 264 210 481 130 216 31 410 383 9 141 13 343 448 45 324 297 449 371 149 474 214 41 154 185 138 299 34 412 411 492 327 277 229 33 494 237 12 97 420 6 18...
output:
426 412 483 390 412 483 93 483 412 483 483 390 412 483 483 412 483 93 412 93 426 412 426 483 431 93 426 483 390 426 93 483 390 390 390 93 426 390 483 426 93 426 93 390 426 426 426 426 412 483 426 483 426 483 426 483 483 390 426 93 483 412 412 426 483 412 483 426 412 390 483 390 483 426 412 390 93 41...
result:
ok Accepted.
Test #25:
score: 0
Accepted
time: 76ms
memory: 95952kb
input:
500 499 5000 368 181 285 335 445 454 267 331 22 212 294 281 454 121 19 31 57 14 101 152 130 284 329 396 406 500 446 115 337 61 421 68 203 119 352 238 313 450 16 259 167 307 326 255 173 256 77 42 203 270 249 402 153 135 146 450 172 73 185 149 398 15 426 213 407 368 351 124 159 356 371 418 319 156 304...
output:
355 210 461 310 461 210 210 310 355 461 461 19 461 487 487 461 19 355 310 461 310 487 355 487 487 487 310 487 355 487 210 487 210 210 355 355 487 461 487 355 19 355 355 487 210 487 487 310 355 461 210 355 487 310 487 487 487 487 19 355 19 461 461 487 461 19 224 210 210 210 461 355 19 461 210 461 210...
result:
ok Accepted.
Test #26:
score: 0
Accepted
time: 67ms
memory: 100240kb
input:
500 499 5000 350 140 294 337 407 172 180 28 139 287 2 413 498 218 4 449 245 412 45 247 397 482 427 165 202 490 53 323 178 209 247 341 253 485 478 203 34 305 306 173 111 14 188 64 213 9 278 59 347 454 83 448 356 336 148 239 378 272 145 402 457 189 299 209 291 368 96 110 187 270 218 304 358 217 6 455 ...
output:
-1
result:
ok Accepted.
Test #27:
score: 0
Accepted
time: 79ms
memory: 104460kb
input:
499 499 5000 75 164 439 163 466 334 370 484 25 201 107 165 250 122 355 17 411 164 169 9 463 497 428 442 93 50 7 326 15 207 479 112 454 391 329 96 127 290 1 2 99 347 39 84 407 405 147 271 57 298 472 129 195 377 296 35 441 440 232 176 388 92 325 198 425 267 23 100 487 433 78 416 193 365 348 352 324 28...
output:
-1
result:
ok Accepted.
Subtask #4:
score: 20
Accepted
Dependency #2:
100%
Accepted
Test #28:
score: 20
Accepted
time: 69ms
memory: 85644kb
input:
499 499 265 20 482 382 88 211 434 122 198 238 180 411 104 462 291 28 215 220 69 192 172 493 52 25 455 162 29 405 278 161 339 316 212 443 257 419 262 411 458 331 93 106 144 422 264 488 248 86 165 62 411 426 236 443 30 140 260 499 37 295 372 315 237 15 67 403 366 467 235 42 262 61 300 312 362 469 202 ...
output:
298 488 28 270 17 17 222 222 81 325 488 488 28 479 215 17 81 28 74 488 74 222 488 17 369 222 250 369 479 250 479 479 250 442 57 488 81 298 17 298 496 17 496 298 422 496 442 222 488 57 81 479 74 488 28 267 81 17 28 17 298 51 479 298 28 28 28 17 28 222 74 51 442 222 488 28 479 488 488 222 28 298 42 28...
result:
ok Accepted.
Test #29:
score: 0
Accepted
time: 62ms
memory: 84032kb
input:
500 498 275 323 261 41 144 117 22 223 61 412 79 403 191 166 56 401 274 42 204 439 277 439 175 475 382 320 164 179 397 143 302 68 276 11 9 252 25 421 419 109 353 451 165 63 461 28 241 7 91 302 420 60 284 283 113 418 176 443 177 64 412 144 497 493 14 483 209 287 375 287 100 298 376 298 193 188 321 288...
output:
156 491 491 11 339 168 11 420 11 157 420 208 193 76 157 157 160 208 76 339 208 76 11 229 193 157 491 191 193 56 191 156 491 420 157 157 420 11 156 144 420 156 76 160 160 156 76 193 420 420 302 156 11 420 156 193 193 156 11 420 41 420 11 156 11 237 156 160 11 156 156 156 11 420 11 11 157 420 491 237 ...
result:
ok Accepted.
Test #30:
score: 0
Accepted
time: 77ms
memory: 83880kb
input:
500 499 215 233 327 276 433 188 7 393 452 431 389 55 485 238 103 411 344 273 193 351 211 248 161 489 149 13 427 336 210 487 199 76 324 452 477 290 134 108 418 378 300 371 218 499 85 418 450 480 353 248 451 89 3 249 248 283 203 294 443 102 360 412 20 234 177 479 171 357 165 490 340 133 110 52 106 374...
output:
-1
result:
ok Accepted.
Test #31:
score: 0
Accepted
time: 65ms
memory: 89548kb
input:
499 499 260 157 101 80 132 333 13 206 419 136 233 322 168 48 362 32 485 426 214 493 349 179 181 245 284 332 366 234 63 407 254 429 337 32 217 469 130 18 129 147 42 223 473 9 310 330 6 242 483 233 228 154 498 31 351 171 377 455 328 497 301 343 244 355 144 386 489 437 247 307 493 134 316 185 256 199 2...
output:
-1
result:
ok Accepted.
Test #32:
score: 0
Accepted
time: 67ms
memory: 86056kb
input:
498 498 1951 289 275 304 352 50 441 95 466 432 162 324 216 367 399 413 154 163 345 290 127 450 195 437 41 326 421 236 299 248 449 60 233 31 183 278 228 184 444 384 448 135 462 39 486 215 123 136 120 12 200 182 416 475 292 180 40 381 334 324 310 113 429 177 398 393 447 67 350 112 46 133 23 205 218 33...
output:
136 381 233 255 416 173 137 39 416 137 100 136 44 416 136 151 262 173 185 173 402 44 151 137 311 137 154 198 151 136 416 68 44 185 11 198 327 475 416 416 334 136 402 262 255 100 475 44 100 475 151 107 39 381 68 68 173 173 173 173 262 11 416 39 136 173 398 446 255 475 260 100 416 137 152 262 311 352 ...
result:
ok Accepted.
Test #33:
score: 0
Accepted
time: 58ms
memory: 90036kb
input:
498 499 2728 88 127 472 81 109 272 124 323 459 371 316 200 321 29 306 46 458 36 95 143 148 205 207 308 252 440 39 74 131 100 237 277 298 341 16 473 349 492 83 461 98 382 17 13 295 198 65 83 165 426 127 412 413 327 237 268 183 211 207 255 221 41 128 433 100 217 40 9 151 64 426 360 189 322 209 26 290 ...
output:
-1
result:
ok Accepted.
Test #34:
score: 0
Accepted
time: 65ms
memory: 90052kb
input:
498 500 285 165 321 87 3 184 139 75 133 257 406 187 14 396 96 323 248 63 165 69 170 388 281 117 164 114 329 103 355 138 177 169 498 182 462 368 424 323 474 322 317 303 416 57 259 498 425 135 216 137 38 30 437 151 205 147 19 459 12 174 280 400 348 248 435 362 213 180 54 363 77 54 157 65 303 447 366 6...
output:
189 400 362 57 362 323 47 425 425 189 323 132 47 189 47 189 57 323 47 57 189 323 362 165 47 189 57 132 165 362 425 57 362 47 323 400 362 165 47 132 400 132 323 362 47 27 47 47 132 323 165 425 400 400 27 323 47 132 323 323 57 189 57 362 323 362 57 47 47 455 27 400 27 400 323 400 400 27 165 455 47 425...
result:
ok Accepted.
Test #35:
score: 0
Accepted
time: 58ms
memory: 82032kb
input:
499 500 371 4 44 100 459 299 107 478 284 421 197 56 90 381 198 305 237 137 260 451 188 381 435 230 458 354 76 100 157 431 198 133 394 181 340 221 198 180 15 269 386 287 330 378 152 198 129 274 318 139 38 150 385 11 352 114 428 408 154 248 44 206 76 264 56 35 222 457 194 196 272 494 443 96 453 439 43...
output:
222 294 157 76 294 76 294 222 76 44 76 294 157 381 294 381 428 294 76 76 381 222 157 381 157 381 294 428 222 381 381 157 294 44 76 76 157 76 76 428 157 428 294 44 294 157 157 76 381 157 428 157 157 157 76 157 44 428 381 157 428 44 428 76 157 381 157 157 157 381 381 76 76 294 44 76 381 157 381 428 38...
result:
ok Accepted.
Test #36:
score: 0
Accepted
time: 59ms
memory: 87668kb
input:
498 500 355 367 393 291 435 471 306 44 77 23 36 411 421 59 308 419 155 179 222 58 44 66 4 420 442 228 398 435 339 133 296 184 382 335 175 346 398 316 237 24 57 208 281 332 389 195 320 60 425 136 205 9 365 187 177 493 108 468 445 430 494 241 321 486 304 478 127 18 223 182 261 279 377 233 210 212 193 ...
output:
-1
result:
ok Accepted.
Test #37:
score: 0
Accepted
time: 92ms
memory: 98128kb
input:
500 498 215 80 358 454 116 72 463 139 277 370 436 202 220 16 188 1 213 38 59 494 217 497 424 426 135 35 302 419 26 326 499 209 10 311 315 451 285 54 60 161 103 168 413 393 104 234 308 434 39 442 49 306 374 311 158 342 287 74 14 199 102 285 51 379 459 411 125 101 210 84 321 369 111 45 334 65 471 143 ...
output:
466 397 192 199 93 258 35 240 8 19 159 84 341 459 177 50 438 447 186 192 91 98 469 274 239 122 91 447 41 175 393 258 54 215 24 60 400 447 379 285 392 5 177 24 199 328 6 15 54 201 407 481 91 8 287 366 8 87 175 25 156 481 366 397 466 215 177 35 287 24 392 240 201 199 24 330 79 15 400 24 253 348 91 414...
result:
ok Accepted.
Test #38:
score: 0
Accepted
time: 70ms
memory: 89960kb
input:
499 498 307 333 446 460 222 39 378 485 52 81 34 75 195 334 424 457 84 460 367 255 166 223 160 310 85 437 87 61 238 108 430 264 487 122 6 319 428 119 154 258 304 133 36 276 326 235 383 327 146 375 340 206 98 157 414 241 47 63 479 307 81 308 335 91 390 121 108 463 492 487 146 361 371 9 311 199 265 297...
output:
12 442 224 224 336 224 12 79 378 251 442 336 432 1 487 1 442 224 79 126 378 39 79 12 336 442 491 487 435 251 487 487 435 378 34 1 224 435 224 224 12 224 435 442 224 12 378 12 1 1 336 12 378 224 336 251 435 39 39 12 224 491 442 487 224 1 378 224 435 1 12 79 12 487 224 378 487 1 491 34 224 378 378 1 7...
result:
ok Accepted.
Test #39:
score: 0
Accepted
time: 77ms
memory: 85800kb
input:
498 499 314 282 244 343 470 265 268 88 151 423 412 198 242 421 306 203 225 297 471 63 170 290 497 83 91 132 248 11 395 127 81 387 98 422 222 108 122 29 375 419 297 144 324 151 58 96 345 330 475 177 68 144 28 35 448 394 371 328 124 141 279 231 67 208 340 10 403 298 77 170 127 274 378 305 439 81 442 3...
output:
406 144 406 144 144 144 144 144 144 406 146 406 146 144 144 144 144 144 144 144 155 144 146 144 144 144 406 144 144 144 144 406 144 144 144 144 144 144 144 144 144 406 146 144 144 144 155 469 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 406 155 144 144 144 155 144 406 ...
result:
ok Accepted.
Test #40:
score: 0
Accepted
time: 94ms
memory: 102544kb
input:
499 500 5000 262 245 206 378 294 422 331 197 13 210 57 31 239 117 278 155 209 272 182 479 200 209 178 150 371 388 286 42 104 405 356 494 171 235 362 305 361 269 34 20 256 137 233 425 346 311 170 69 76 319 168 110 366 162 305 265 199 194 107 182 59 157 48 243 153 435 469 22 226 54 360 187 72 363 293 ...
output:
475 206 96 249 384 7 358 150 192 287 357 343 494 324 308 249 435 435 5 40 466 182 292 486 262 182 455 471 140 2 140 7 497 82 176 75 486 220 192 227 365 342 350 463 428 51 104 96 260 494 102 202 230 249 426 343 96 323 192 270 475 388 479 217 205 180 287 455 96 412 407 233 131 343 453 90 345 136 114 4...
result:
ok Accepted.
Test #41:
score: 0
Accepted
time: 95ms
memory: 100328kb
input:
498 500 5000 306 1 215 389 341 416 374 34 262 125 476 288 444 90 342 85 215 31 472 463 2 111 325 349 59 275 435 49 448 82 497 167 233 428 407 232 155 109 365 49 322 318 381 10 84 226 422 345 388 168 206 304 301 282 275 47 38 489 210 442 332 118 339 125 393 67 210 421 270 388 380 354 358 352 310 228 ...
output:
243 36 34 465 414 441 359 206 355 379 438 434 44 205 482 88 243 96 372 285 348 93 240 167 498 469 131 457 348 453 298 400 175 394 93 73 449 243 149 4 193 374 372 221 205 127 416 410 70 416 31 187 175 143 44 348 364 113 355 439 419 8 31 242 379 283 446 387 94 187 285 457 245 179 263 387 217 127 235 3...
result:
ok Accepted.
Test #42:
score: 0
Accepted
time: 83ms
memory: 101992kb
input:
499 498 5000 395 382 498 86 410 99 157 411 263 304 133 323 163 150 111 220 38 124 305 157 398 491 269 82 9 376 91 239 285 185 370 362 121 456 414 63 306 140 454 183 206 60 417 483 34 482 138 412 358 173 75 346 477 324 429 59 10 486 202 412 426 246 360 267 200 439 394 363 77 348 320 187 442 428 120 5...
output:
-1
result:
ok Accepted.
Test #43:
score: 0
Accepted
time: 106ms
memory: 98024kb
input:
499 499 5000 56 232 281 262 375 216 390 313 244 105 298 227 349 160 115 400 455 98 147 463 25 371 97 131 255 345 187 342 93 207 207 432 330 216 301 346 415 377 166 265 399 495 94 276 354 139 74 50 230 385 42 480 276 457 419 239 264 97 413 157 436 401 154 203 284 425 414 389 358 93 60 308 285 259 144...
output:
436 232 181 67 159 245 52 245 168 194 159 481 17 371 293 91 336 324 207 15 422 481 294 427 171 171 112 422 293 207 161 159 80 43 168 161 324 206 110 293 52 481 293 283 343 303 468 213 348 436 294 348 336 15 354 112 236 277 236 17 293 378 226 168 17 194 17 348 213 422 481 28 226 381 293 422 213 371 3...
result:
ok Accepted.
Test #44:
score: 0
Accepted
time: 88ms
memory: 99920kb
input:
498 498 5000 466 442 188 316 306 215 336 277 11 225 2 23 426 316 396 299 463 201 280 428 288 440 104 398 238 363 341 6 289 106 142 49 192 481 4 195 323 278 185 213 461 475 465 317 324 465 68 187 434 491 222 268 141 334 72 108 61 360 321 471 498 18 166 206 396 377 96 127 5 91 213 456 29 286 191 224 2...
output:
448 226 341 237 376 351 457 376 435 482 374 414 457 238 71 405 401 482 416 91 67 373 360 376 236 91 482 44 416 265 329 101 359 265 113 405 448 351 461 341 385 329 416 101 405 461 373 107 414 156 113 176 416 341 150 70 150 384 416 70 46 265 46 360 236 114 226 238 376 91 360 384 341 439 482 176 482 46...
result:
ok Accepted.
Test #45:
score: 0
Accepted
time: 81ms
memory: 89804kb
input:
498 500 367 378 138 146 248 403 496 200 459 400 75 23 277 418 16 101 24 277 362 384 408 320 208 441 46 361 25 85 303 278 288 337 425 24 114 56 344 346 124 128 250 75 9 193 130 114 360 273 250 68 268 310 145 468 287 283 469 225 319 24 400 212 378 135 354 280 311 1 90 208 357 280 56 403 321 411 455 47...
output:
453 403 400 75 403 400 8 24 400 307 75 357 8 250 24 24 330 453 51 400 307 250 8 330 453 24 8 24 24 24 75 250 453 400 8 491 24 453 24 24 400 403 24 24 400 307 24 491 8 51 51 400 51 24 51 24 453 453 400 400 24 453 400 403 24 8 400 400 400 75 307 24 75 400 51 400 75 250 250 24 330 250 24 24 400 400 24 ...
result:
ok Accepted.
Test #46:
score: 0
Accepted
time: 75ms
memory: 87972kb
input:
498 498 294 286 177 26 389 64 73 369 155 345 299 409 106 94 9 286 191 199 354 43 307 107 441 258 222 264 129 456 23 462 275 344 156 193 445 401 360 215 267 33 442 209 465 170 1 257 189 418 15 324 377 175 120 486 498 303 353 30 172 104 43 344 76 126 325 264 455 445 310 47 12 420 381 394 331 391 233 1...
output:
416 498 471 28 179 365 471 28 365 238 238 28 498 371 416 371 416 28 76 471 177 177 28 286 416 179 471 365 76 238 371 179 76 177 76 371 365 365 238 76 76 498 76 177 371 471 286 371 471 383 179 76 177 177 371 28 371 498 498 286 286 498 416 498 471 177 179 177 177 286 498 286 498 416 416 383 28 365 286...
result:
ok Accepted.
Test #47:
score: 0
Accepted
time: 63ms
memory: 81916kb
input:
498 500 214 246 323 132 465 29 71 436 107 95 214 163 281 487 35 388 133 469 148 250 240 486 135 45 144 311 160 461 127 372 283 254 127 252 389 276 441 94 194 115 98 209 127 411 242 99 50 180 47 124 107 483 44 175 272 229 159 176 41 9 206 477 397 302 108 11 318 362 391 356 363 417 391 274 65 71 309 1...
output:
146 213 213 147 146 146 146 394 147 147 146 276 147 147 276 394 146 394 213 213 146 276 213 213 146 147 146 394 213 394 276 276 147 276 394 276 146 147 276 276 394 146 213 213 147 276 146 213 146 394 146 394 146 276 213 146 146 394 147 394 146 213 146 394 394 146 276 213 213 147 394 146 147 276 146 ...
result:
ok Accepted.
Subtask #5:
score: 25
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #48:
score: 25
Accepted
time: 1373ms
memory: 650848kb
input:
1999 1999 16990 734 609 971 297 1864 1528 1995 858 1223 411 1800 580 451 1384 800 866 1709 422 740 1381 1402 431 614 526 249 531 406 228 1589 456 1357 1731 852 869 557 1681 1072 632 1695 358 1686 186 1706 313 189 1115 907 1051 1645 1854 1794 1639 1857 1859 496 660 1784 578 311 100 1430 765 330 1319 ...
output:
1194 531 200 971 1592 54 901 869 1497 901 971 1196 919 824 311 311 919 1534 1759 531 311 1645 311 200 325 54 1196 869 1194 919 971 869 1196 901 1645 1668 1592 1990 1845 1695 1845 1527 1645 1527 639 54 325 1534 531 122 1196 1497 531 639 1534 54 311 1645 1194 1534 1527 1527 1534 531 824 325 971 1845 1...
result:
ok Accepted.
Test #49:
score: 0
Accepted
time: 1366ms
memory: 652696kb
input:
2000 1998 12882 650 855 532 1114 1227 1437 104 109 599 1148 1400 1487 993 78 1127 1447 1961 1896 1683 170 403 327 1883 1974 1392 1111 1803 571 738 717 1088 1311 411 654 1268 444 919 859 741 954 893 1815 967 1079 1070 1257 1368 643 825 199 7 799 1752 377 1560 1870 1693 748 1834 707 277 411 1175 598 1...
output:
633 633 967 1946 967 1946 1590 967 1988 967 13 292 1114 1946 1020 1020 13 1593 1174 1824 967 506 1632 967 506 573 1824 1174 1632 1632 1174 220 1946 1824 1632 1824 1824 506 1824 1038 1447 1447 13 967 1824 119 967 633 1114 967 633 893 13 1988 13 506 1632 119 1020 1593 1227 1114 893 1824 1174 1020 633 ...
result:
ok Accepted.
Test #50:
score: 0
Accepted
time: 1607ms
memory: 650820kb
input:
1999 1998 2748 1888 854 1797 419 1733 1121 1431 1009 622 1970 1348 1837 55 478 607 1747 1982 1626 1959 1099 1837 130 605 333 1805 1369 1202 35 1503 986 875 837 693 332 238 1200 41 222 314 925 5 194 1049 238 1493 1290 1206 374 1642 1107 363 1963 49 199 1440 687 75 1130 1131 985 1405 1814 219 953 1134...
output:
1052 984 1141 1496 789 1290 1405 1581 1141 385 1827 1141 1278 1257 1328 1827 1290 1052 1206 1290 1581 1496 1581 789 1278 1290 385 610 610 610 1257 789 1496 610 1830 1290 1141 385 1278 1141 789 1405 789 1052 610 1346 1257 85 238 1278 1278 299 1496 299 1278 1496 1052 1827 789 1257 1252 984 1141 1215 1...
result:
ok Accepted.
Test #51:
score: 0
Accepted
time: 1584ms
memory: 650676kb
input:
1998 2000 2456 1687 1024 311 1248 1239 1331 606 1760 1677 1623 853 1920 1163 1877 1523 1818 74 35 1019 1313 232 284 1892 7 583 400 226 1630 1664 478 242 1805 1814 91 519 169 1406 242 1953 506 767 451 1631 1421 916 1717 461 1635 1177 1193 1138 235 486 411 255 809 1157 155 33 1668 295 1772 1529 1369 1...
output:
782 782 785 1652 1520 94 94 180 1697 606 180 685 94 180 1652 1652 785 785 785 606 1840 782 1894 1746 1894 685 1520 685 1652 1349 1706 785 782 411 1652 1520 1349 1597 536 1772 1349 1697 782 1652 180 1706 785 1706 180 1597 1520 1652 1840 1746 785 180 1746 1923 536 411 1923 1772 606 1652 1697 782 785 7...
result:
ok Accepted.
Test #52:
score: 0
Accepted
time: 1656ms
memory: 646616kb
input:
1999 2000 2084 1907 1359 888 1314 963 598 1112 1636 1517 1034 1933 1578 813 973 972 78 1929 1119 1774 952 1471 1814 461 756 506 1085 803 1937 1220 18 38 1010 1375 1576 1800 1767 309 1072 382 888 739 1838 76 174 497 477 1600 1821 264 1359 1278 1546 445 520 968 501 1840 610 750 858 103 1112 1236 321 1...
output:
-1
result:
ok Accepted.
Test #53:
score: 0
Accepted
time: 1647ms
memory: 679420kb
input:
1999 2000 2517 1460 515 265 141 171 1521 1148 1253 1131 949 1922 1829 619 920 848 802 158 312 587 1813 1899 796 1228 1431 1228 1768 1128 1975 58 734 1668 1656 1441 517 1623 234 1242 1238 1787 169 1808 256 217 1547 1295 1866 568 1573 1255 1350 124 520 1606 852 1754 1602 1085 1206 796 91 1905 745 1607...
output:
-1
result:
ok Accepted.
Test #54:
score: 0
Accepted
time: 1642ms
memory: 683592kb
input:
1998 1998 2949 1605 573 1586 1754 1027 296 213 353 1981 396 535 1992 781 1237 1369 90 1255 400 1941 210 680 177 510 115 1303 285 403 244 55 1327 1605 1531 1968 1444 218 316 1502 689 1123 123 131 1558 1742 1730 1512 219 1647 1583 1653 1428 1132 65 549 462 406 584 1072 1879 716 1069 1860 543 351 1253 ...
output:
860 1032 465 417 972 268 20 621 481 860 860 462 1578 307 532 621 645 1982 1559 799 831 1145 386 1482 972 1952 1559 1286 1394 307 256 268 983 1701 1983 488 462 1982 1952 1063 972 972 1701 1631 777 1309 1113 1631 860 1982 28 1309 1347 375 1390 256 1740 683 1995 683 617 488 227 889 176 20 465 481 1993 ...
result:
ok Accepted.
Test #55:
score: 0
Accepted
time: 1598ms
memory: 662940kb
input:
1999 1998 2979 1386 1126 766 166 651 245 803 925 1737 60 1606 460 619 835 921 1145 491 1518 1718 1176 1250 761 841 999 761 394 823 756 1926 1159 1976 1122 1536 1288 1963 429 1199 584 1232 928 1233 1188 1968 709 1109 964 37 1690 508 523 839 1033 613 190 656 1354 531 1910 1431 1859 1890 972 982 40 126...
output:
1511 1144 1144 1585 499 1628 1523 1523 1696 678 532 678 1978 452 26 1518 37 1077 1093 1077 1518 1554 1171 1286 1523 260 1488 260 450 468 260 1511 933 1182 858 1523 1817 1554 532 186 1286 1300 364 468 1182 532 678 364 295 364 1817 858 1171 1978 1978 1096 858 1518 678 186 1093 94 364 1523 1518 391 933...
result:
ok Accepted.
Test #56:
score: 0
Accepted
time: 1674ms
memory: 667268kb
input:
1999 1999 2386 1948 1104 1966 963 1141 1282 1133 1069 455 517 1327 1603 1368 516 755 1717 1415 992 1786 1679 633 381 1545 1140 1277 1370 1219 285 1061 602 165 9 1144 387 952 1780 1953 578 968 799 183 598 1262 503 990 251 1786 814 1932 466 1869 1102 595 1338 1848 865 1425 362 647 21 1994 27 1377 716 ...
output:
839 975 1791 1791 1791 839 982 1235 362 686 982 1429 970 975 1791 1861 1791 1861 1791 1061 970 940 970 1791 1061 1039 1791 1491 1107 1627 1791 1279 1061 1302 1491 1235 1279 975 940 1997 199 1997 672 1061 1791 992 982 1861 1245 166 975 734 1491 1207 940 199 1997 1485 604 1834 199 1070 992 362 982 179...
result:
ok Accepted.
Test #57:
score: 0
Accepted
time: 1863ms
memory: 745132kb
input:
1998 1998 3943 1721 662 484 891 524 1161 483 1222 824 401 1039 1027 179 793 555 1800 61 1904 265 128 1830 82 1613 1795 1428 745 1120 1146 857 1776 230 75 763 1954 1111 1868 1014 215 110 536 783 399 267 433 1867 491 1713 595 903 833 865 1894 1001 593 1165 393 504 1208 1077 1202 855 635 1057 236 1776 ...
output:
1133 1149 1666 1683 1054 1384 1706 1482 1870 1778 1847 1270 1404 745 120 775 603 1662 1319 1868 126 635 355 1873 1946 1920 607 1267 1961 824 1981 1023 1093 1928 880 426 134 374 870 197 582 1334 555 282 566 1829 520 1532 699 1423 1577 1411 1904 1917 593 1461 232 1363 1971 755 787 824 1536 560 1477 13...
result:
ok Accepted.
Test #58:
score: 0
Accepted
time: 1554ms
memory: 679304kb
input:
1999 1998 32642 1546 1931 1475 669 810 1758 114 471 1167 1223 297 932 1921 1720 1640 519 1709 1618 1547 1434 981 1433 1132 1773 1522 232 760 1827 51 484 1648 870 1257 594 9 1538 1840 1490 773 9 1385 1968 1215 1326 1228 58 1197 403 1258 1938 1879 775 46 1880 195 542 684 1362 511 1555 1210 340 1359 16...
output:
225 1113 1038 304 1045 304 265 1630 870 304 1572 334 1938 872 936 1753 1657 665 1326 304 292 902 1677 225 1657 1088 220 427 1682 225 9 79 799 1649 297 902 902 885 725 225 1657 225 885 725 885 425 1753 1195 1040 565 1649 695 707 1040 1630 1840 1162 1715 1677 1257 707 1162 1326 92 732 649 466 872 742 ...
result:
ok Accepted.
Test #59:
score: 0
Accepted
time: 2451ms
memory: 757232kb
input:
1999 1998 50000 1244 222 642 583 279 699 1377 95 1321 1432 1030 1267 4 456 399 582 1867 304 121 745 65 424 1117 718 190 40 1172 807 535 725 169 1998 1712 1537 413 1600 313 496 7 1456 31 1977 1983 947 555 569 655 1195 617 955 68 1165 177 1479 262 1500 1533 1733 1507 927 1341 1587 1718 541 1839 362 18...
output:
15 248 976 132 1872 1571 285 1505 1601 444 1160 1553 191 474 1348 1763 976 1831 191 518 1350 1073 1839 1843 486 1676 1264 1775 1868 1171 576 665 1967 248 1899 487 84 1334 1763 1369 1133 1516 1399 361 47 1659 697 298 1219 944 1345 1372 1661 569 765 132 1110 1843 602 282 976 675 10 1750 1650 264 1633 ...
result:
ok Accepted.
Test #60:
score: 0
Accepted
time: 2387ms
memory: 743200kb
input:
1999 1998 50000 1481 1787 923 1228 245 1382 1097 1350 1585 563 1940 461 468 270 1534 291 1877 202 1738 924 160 1380 1665 1458 1859 1053 1685 1036 390 1385 1740 1719 1499 29 554 1258 1690 530 140 76 341 685 906 1383 1275 123 1933 1020 1892 1119 46 73 1400 1408 490 59 1205 1395 1551 83 1071 1457 505 2...
output:
914 393 131 809 757 65 277 1130 1544 1209 1369 1645 959 545 636 156 714 247 215 247 1277 125 1090 1161 1501 937 1463 701 1845 288 1035 353 247 196 607 932 192 1090 1768 1222 830 247 959 236 1481 1731 1348 1954 1542 1922 893 744 1768 1559 1736 889 175 821 1226 1041 82 1952 1871 185 1269 628 63 932 19...
result:
ok Accepted.
Test #61:
score: 0
Accepted
time: 2384ms
memory: 759136kb
input:
1998 1999 50000 129 669 1774 926 1477 254 527 377 1454 588 1541 1133 264 292 189 1686 898 1858 300 1737 238 647 1116 1906 647 1496 1595 1296 1212 177 656 1016 1366 233 956 1907 1344 1411 1629 863 1441 874 848 193 130 1396 791 1137 40 173 1560 523 1698 1181 1395 1749 1057 1427 288 742 546 1069 902 25...
output:
509 1730 1537 1752 388 1206 509 155 159 1384 772 772 1730 891 1114 159 643 1836 627 1581 114 871 489 1621 1114 1114 99 1730 1359 772 159 1470 1385 1761 388 388 1836 114 1004 388 772 1206 353 1004 1384 509 1172 1384 1384 772 1836 1910 643 1658 1752 1239 1239 1385 1621 200 200 114 1239 1746 1910 643 4...
result:
ok Accepted.
Test #62:
score: 0
Accepted
time: 2480ms
memory: 757312kb
input:
2000 1999 50000 1946 632 1829 219 1133 1145 1239 328 781 650 935 558 1930 1633 1909 1093 1708 1914 27 44 1134 1309 699 273 1160 1567 817 253 1398 1633 964 647 341 250 764 1865 1404 1610 597 795 1082 202 1276 1705 1193 331 307 1697 1234 1386 491 267 765 1132 1580 1318 527 181 1152 1170 1504 637 714 2...
output:
1838 291 783 1742 951 503 1064 1365 1354 239 464 503 239 720 464 503 1820 715 1002 394 1354 1386 503 1459 783 1221 1039 32 1221 1002 661 1078 265 1882 394 32 1838 1078 291 1085 1874 503 1459 1265 110 1446 291 239 951 1064 715 1221 1459 1221 1365 1078 994 32 1039 239 1265 1590 1446 1459 1874 1358 179...
result:
ok Accepted.
Test #63:
score: 0
Accepted
time: 2275ms
memory: 759336kb
input:
2000 1998 50000 853 34 127 1282 1878 301 235 947 1292 1642 1125 122 264 779 121 736 1417 1995 82 1846 305 380 1505 1954 1532 47 1022 633 117 178 521 735 1582 1016 352 256 1901 871 1115 1577 453 1133 1718 909 471 1376 990 1298 1075 282 1167 1018 903 191 1969 1851 1990 1443 1628 773 323 1829 1477 174 ...
output:
-1
result:
ok Accepted.
Subtask #6:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #5:
100%
Accepted
Test #64:
score: 10
Accepted
time: 1889ms
memory: 650776kb
input:
2000 1999 58321 444 202 1301 594 1824 45 1172 931 1071 1931 1891 654 66 1894 775 1506 1542 979 419 246 25 380 1118 813 1433 1691 572 346 1519 1626 1198 1332 352 1380 1031 1436 843 1428 994 1236 878 328 1337 1461 1717 1038 1096 1811 1191 1527 1426 629 1426 33 108 752 1587 304 367 934 944 621 330 574 ...
output:
542 1071 1173 1173 1173 595 426 878 1842 330 878 595 159 595 595 330 1379 159 595 473 1063 1429 595 1885 1063 473 878 174 1885 1063 473 542 174 878 1379 401 878 595 1368 1885 401 878 174 1173 401 473 330 174 878 878 1071 1429 1885 878 229 1063 1173 595 1379 427 1379 426 174 330 878 159 878 229 878 1...
result:
ok Accepted.
Test #65:
score: 0
Accepted
time: 1725ms
memory: 650708kb
input:
1999 1999 120206 325 133 1513 265 1066 365 71 254 958 824 67 965 869 1570 1336 401 727 1032 578 691 1019 1324 628 297 1142 400 257 1762 824 275 483 1513 1487 236 1253 859 1742 1500 1567 1713 1513 50 1709 773 472 242 1878 958 106 92 168 1447 546 301 1816 1941 1721 1293 1611 169 1179 1240 604 1198 190...
output:
79 1434 86 1001 1893 1542 1703 1703 1542 958 86 1001 1515 847 1893 847 651 1332 931 1513 1066 958 958 1515 1066 870 958 702 702 1001 1703 847 79 1542 1513 958 1332 1332 1001 847 86 651 1332 137 1290 847 1747 958 870 870 1893 1332 1332 1513 702 79 1332 1703 1332 958 1549 1893 1066 1170 1515 958 1515 ...
result:
ok Accepted.
Test #66:
score: -10
Time Limit Exceeded
input:
2000 1998 11568 789 1898 271 1158 841 1494 550 1984 849 947 168 1329 1197 1475 33 571 1630 1528 914 1244 1299 1366 517 1835 1072 1263 1093 169 83 1279 185 1646 276 516 1166 642 935 1544 1332 1129 1000 1183 1981 1751 1410 413 195 1361 1146 341 1431 1340 1507 1517 1031 1577 384 1945 1001 311 1955 466 ...