QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#265870 | #7869. 建设终末树 | grass8cow | 65 | 1972ms | 715268kb | C++17 | 5.2kb | 2023-11-25 21:59:35 | 2023-11-25 21:59:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,q,N,O;
#define pb push_back
int ans[4010000];
struct DSU{
int fa[2010],sz[2010];
inline void build(){for(int i=1;i<=m;i++)fa[i]=i,sz[i]=1;}
int F(int x){if(x==fa[x])return x;return fa[x]=F(fa[x]);}
inline void mer(int u,int v){u=F(u),v=F(v);if(u==v)return;if(sz[u]<sz[v])swap(u,v);fa[v]=u,sz[u]+=sz[v];}
}wc[2010],fz[2010];
void ad(DSU &a,DSU b){for(int i=1;i<=m;i++)if(b.fa[i]!=i)a.mer(b.fa[i],i);}
namespace SAT2{
int hd[16010000],nxt[44010000],to[44010000],sta[16010010],col[16001000],cn,scc;
int dfn[16001000],low[16001000],top;bool vis[16001000];
void add(int u,int v){nxt[++cn]=hd[u],to[cn]=v,hd[u]=cn;}
int sp[16001000],tt;
void dfs(int x){
dfn[x]=low[x]=++dfn[0],sta[++top]=x,vis[x]=1;
for(int i=hd[x];i;i=nxt[i]){
int v=to[i];
if(!dfn[v])dfs(v),low[x]=min(low[x],low[v]);
else if(vis[v])low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x]){
col[x]=++scc,vis[x]=0;
while(sta[top]!=x)col[sta[top]]=scc,vis[sta[top]]=0,top--;
top--;
}
}
void sol(){
for(int i=1;i<=O;i++)if(!dfn[i]){
tt=1,sp[1]=i;
while(tt){
int u=sp[tt];
if(!dfn[u])dfn[u]=low[u]=++dfn[0],sta[++top]=u,vis[u]=1;
if(!hd[u]){
if(dfn[u]==low[u]){
col[u]=++scc,vis[u]=0;
while(sta[top]!=u)col[sta[top]]=scc,vis[sta[top]]=0,top--;
top--;
}
if(tt>1)low[sp[tt-1]]=min(low[sp[tt-1]],low[u]);
tt--;
}
else{
int v=to[hd[u]];hd[u]=nxt[hd[u]];
if(!dfn[v])sp[++tt]=v;
else if(vis[v])low[u]=min(low[u],dfn[v]);
}
}
}
for(int i=1;i<=N;i++){
if(col[i]==col[i+N]){puts("-1");exit(0);}
ans[i]=(col[i]<col[i+N])?0:1;
}
}
}
int id[2010][2010];
vector<int>g[2010];int jr[2010];
vector<int>gg[501000];
struct ed{int u,v,i;};
vector<ed>T[20];
namespace Tree{
int f[2010][20],d[2010],bel[2010];
void dfs(int x){
bel[++bel[0]]=x;
for(int v:g[x])if(v!=jr[x]){
jr[v]=f[v][0]=x;for(int i=1;i<20;i++)f[v][i]=f[f[v][i-1]][i-1];
d[v]=d[x]+1,dfs(v);
}
}
int lca(int u,int v){
if(d[u]<d[v])swap(u,v);int a=d[u]-d[v];
for(int i=10;i>=0;i--)if((a>>i)&1)
u=f[u][i];if(u==v)return u;
for(int i=10;i>=0;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
return f[u][0];
}
int sz[2010];
void pf(int o){
memset(sz,0,sizeof(sz));int ii,uu;scanf("%d",&ii);for(int i=0;i<ii;i++)
scanf("%d",&uu),sz[uu]=1;
for(int i=n;i>=2;i--)sz[jr[bel[i]]]+=sz[bel[i]];
for(int i=2;i<=n;i++){
if(!sz[i])SAT2::add(id[i][o],id[i][o]+N);
if(sz[i]==ii)SAT2::add(id[i][o]+N,id[i][o]);
}
for(int i=1;i<=n;i++){
int hm=(int)g[i].size();
if(hm==1)continue;
for(int j=0;j+1<hm;j++){
int v=g[i][j];
O++,SAT2::add(O,(v!=jr[i])?(id[v][o]+N):id[i][o]);
int v2=g[i][j+1];
SAT2::add((v2!=jr[i])?id[v2][o]:(id[i][o]+N),O);
if(j)SAT2::add(O,O-1);
}
for(int j=hm-1;j;j--){
int v=g[i][j];
O++,SAT2::add(O,(v!=jr[i])?(id[v][o]+N):id[i][o]);
int v2=g[i][j-1];
SAT2::add((v2!=jr[i])?id[v2][o]:(id[i][o]+N),O);
if(j!=hm-1)SAT2::add(O,O-1);
}
}
}
}
namespace DFZ{
bool vis[2010];int sz[2010],fa[2010];
int S,rt,mx;
void dfs(int x,int f){
sz[x]=1;int mm=-1;
for(int v:g[x])if(v!=f&&!vis[v])dfs(v,x),sz[x]+=sz[v],mm=max(mm,sz[v]);
mm=max(mm,S-sz[x]);
if(mm<mx)mx=mm,rt=x;
}
int d[2010],f[2010][20],D,be[2010][20],sg[20];
void dfs2(int x){
sg[D]++,be[sg[D]][D]=x,sz[x]=1;
for(int v:g[x])if(v!=f[x][D]&&!vis[v])f[v][D]=x,dfs2(v),sz[x]+=sz[v];
}
void so(int u){
D=d[u],vis[u]=1;
dfs2(u);
for(int v:g[u])if(!vis[v])S=sz[v],mx=S+1,rt=-1,dfs(v,0),fa[rt]=u,d[rt]=d[u]+1,so(rt);
}
void ptsd(int u,int v,int w){
int a=u,b=v;while(a!=b){if(d[a]<d[b])swap(a,b);a=fa[a];}
T[d[a]].push_back((ed){u,v,w});
}
void build(){memset(vis,0,sizeof(vis)),S=n,mx=n+1,dfs(1,0);so(rt);}
void push(){
for(int i=0;i<13;i++)if(!T[i].empty()){
for(int j=1;j<=n;j++)fz[j].build();
for(ed t:T[i]){
int w=t.i,fi=gg[w][0];
for(int o:gg[w])fz[t.u].mer(fi,o),fz[t.v].mer(fi,o);
}
for(int j=sg[i];j>=1;j--){
int u=be[j][i];
if(f[u][i]&&f[u][i]!=u){
ad(fz[f[u][i]],fz[u]);
ad(wc[(jr[u]==f[u][i])?u:f[u][i]],fz[u]);
}
}
}
}
}
int va[60];
bool np[2010];
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=2;i<=n;i++)for(int j=1;j<=m;j++)id[i][j]=(i-2)*m+j;
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
g[u].push_back(v),g[v].push_back(u);
}
Tree::dfs(1),DFZ::build();
N=(n-1)*m;O=N*2;
for(int i=1;i<=m;i++)Tree::pf(i);
for(int i=2;i<=n;i++)wc[i].build();
for(int i=1,st,sm;i<=q;i++){
scanf("%d",&st);for(int j=1;j<=st;j++)scanf("%d",&va[j]);
scanf("%d",&sm);for(int j=1,og;j<=sm;j++)scanf("%d",&og),gg[i].push_back(og);
for(int j=2;j<=st;j++)DFZ::ptsd(va[1],va[j],i);
}
DFZ::push();
for(int i=2;i<=n;i++)for(int j=1;j<=m;j++)if(wc[i].fa[j]!=j){
int u=id[i][j],v=id[i][wc[i].fa[j]];
SAT2::add(u,v),SAT2::add(v,u);
SAT2::add(u+N,v+N),SAT2::add(v+N,u+N);
}
SAT2::sol();
for(int i=1;i<=m;i++){
memset(np,0,sizeof(np));
for(int j=2;j<=n;j++){if(ans[id[j][i]])np[j]=1;else np[jr[j]]=1;}
int rt=-1;
for(int j=1;j<=n;j++)if(!np[j])rt=j;
printf("%d ",rt);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1282ms
memory: 706364kb
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: 1300ms
memory: 706472kb
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: 1295ms
memory: 715268kb
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: 1248ms
memory: 690540kb
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: 1277ms
memory: 698344kb
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: 1280ms
memory: 697612kb
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: 1281ms
memory: 699864kb
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: 31944kb
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: 33072kb
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: 6ms
memory: 30580kb
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 3 10 3 9 10 10 3 3 3
result:
ok Accepted.
Test #11:
score: 0
Accepted
time: 0ms
memory: 30460kb
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: 31484kb
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: 30716kb
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 4 2 2 2 2 4
result:
ok Accepted.
Test #14:
score: 0
Accepted
time: 0ms
memory: 33016kb
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 10 10 10 10 5 10 2 2 10
result:
ok Accepted.
Test #15:
score: 0
Accepted
time: 0ms
memory: 30764kb
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:
3 5 6 3 3 3 3 3 3 5
result:
ok Accepted.
Test #16:
score: 0
Accepted
time: 0ms
memory: 31736kb
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: 3ms
memory: 32940kb
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 8 10 8 7 2
result:
ok Accepted.
Test #18:
score: 0
Accepted
time: 3ms
memory: 31900kb
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 2 7
result:
ok Accepted.
Subtask #3:
score: 20
Accepted
Test #19:
score: 20
Accepted
time: 76ms
memory: 84656kb
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 466 48 259 402 253 1 500 71 297 361 471 36 104 242 25 390 305 390 469 369 74 309 415 133 494 429 231 425 74 389 47 429 211 74 296 2 341 253 275 174 1 378 452 74 29 132 266 213 4 47 1 21 479 342 390 375 207 365 2 472 378 253 435 92 402 350 431 322 104 47...
result:
ok Accepted.
Test #20:
score: 0
Accepted
time: 59ms
memory: 91308kb
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:
362 116 499 207 313 403 470 31 468 227 103 31 481 181 429 412 65 87 94 458 2 117 83 2 357 441 105 6 69 38 231 65 44 60 422 283 65 103 423 162 367 489 371 42 357 455 472 65 256 300 468 414 481 48 240 185 325 373 227 481 82 30 181 144 461 464 65 349 281 29 249 202 65 481 349 229 165 110 357 387 381 41...
result:
ok Accepted.
Test #21:
score: 0
Accepted
time: 74ms
memory: 84432kb
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:
128 43 407 420 57 128 62 459 204 358 390 225 96 395 421 57 202 98 57 418 209 43 390 408 117 344 110 363 98 358 187 198 375 172 98 240 234 57 226 62 482 85 57 391 162 37 153 57 309 98 193 37 33 209 238 5 240 57 363 262 459 172 96 13 338 21 400 153 309 455 483 358 284 291 483 459 421 37 37 256 266 192...
result:
ok Accepted.
Test #22:
score: 0
Accepted
time: 80ms
memory: 89792kb
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 264 133 163 22 322 2 378 141 4 497 29 2 133 378 2 2 29 378 108 4 108 363 378 4 390 363 29 163 323 2 322 497 141 312 295 363 2 66 21 497 91 2 497 390 91 497 108 497 264 91 378 22 390 295 467 93 29 113 497 2 22 91 312 264 312 497 22 21 322 93 21 299 29 21 4 22 312 2 322 497 22 29 93 141 93 295 ...
result:
ok Accepted.
Test #23:
score: 0
Accepted
time: 77ms
memory: 84488kb
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 161 393 439 489 489 489 178 437 391 71 2...
result:
ok Accepted.
Test #24:
score: 0
Accepted
time: 64ms
memory: 84588kb
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:
187 412 483 390 412 483 93 483 412 483 483 390 412 483 483 412 483 93 412 93 187 412 187 483 431 93 187 483 390 187 93 483 390 390 390 93 187 390 483 187 93 187 93 390 187 187 187 187 412 483 187 483 187 483 187 483 483 390 187 93 483 412 412 187 483 412 483 187 412 390 483 390 483 187 412 390 93 41...
result:
ok Accepted.
Test #25:
score: 0
Accepted
time: 64ms
memory: 84908kb
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: 86ms
memory: 86604kb
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: 86ms
memory: 92660kb
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: 86ms
memory: 91028kb
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 81 28 17 81 28 74 488 369 222 488 17 380 222 250 369 81 250 479 479 250 442 57 488 81 298 17 267 496 17 496 267 422 496 442 222 488 57 81 479 380 488 28 267 81 17 28 17 298 51 479 298 2 2 28 17 28 222 380 51 442 222 488 28 479 488 488 222 28 298 42 28 5...
result:
ok Accepted.
Test #29:
score: 0
Accepted
time: 63ms
memory: 85356kb
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 2 2 11 339 168 11 420 144 157 420 208 193 76 157 157 160 208 76 339 208 76 11 229 193 157 178 191 193 56 191 156 469 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 2 237 160 1...
result:
ok Accepted.
Test #30:
score: 0
Accepted
time: 76ms
memory: 86048kb
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: 64ms
memory: 86416kb
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: 57ms
memory: 82040kb
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 2 39 416 256 100 136 44 416 136 151 262 173 185 173 402 44 151 256 311 306 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 256 152 262 311 352 15...
result:
ok Accepted.
Test #33:
score: 0
Accepted
time: 64ms
memory: 86128kb
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: 67ms
memory: 89760kb
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 132 47 132 323 2 57 189 57 362 323 362 57 47 47 455 27 400 27 400 323 400 400 27 165 455 47 425 3...
result:
ok Accepted.
Test #35:
score: 0
Accepted
time: 59ms
memory: 87548kb
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 391 428 294 44 294 2 157 76 381 157 428 157 157 157 76 157 44 428 381 157 428 44 428 76 391 381 408 391 157 381 381 76 76 294 44 76 381 157 381 428 381 ...
result:
ok Accepted.
Test #36:
score: 0
Accepted
time: 58ms
memory: 86028kb
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: 71ms
memory: 87648kb
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:
98 98 192 307 93 258 35 240 8 19 2 84 341 459 177 274 438 447 186 400 91 98 469 351 239 122 91 447 41 175 393 258 54 397 24 60 400 447 379 285 392 5 177 24 92 2 6 15 54 348 407 481 91 8 287 366 8 87 175 25 156 481 366 333 458 2 177 35 287 24 392 240 494 34 24 330 79 15 400 24 458 2 91 414 276 129 2 ...
result:
ok Accepted.
Test #38:
score: 0
Accepted
time: 76ms
memory: 89768kb
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 264 126 79 39 487 12 336 442 491 2 435 251 487 487 435 79 34 1 224 435 224 224 12 224 435 442 224 432 378 12 1 1 336 12 378 224 336 251 435 39 39 12 224 491 442 487 224 1 79 224 435 1 12 79 12 264 224 378 487 1 491 34 224 79 378 1 487 ...
result:
ok Accepted.
Test #39:
score: 0
Accepted
time: 62ms
memory: 84744kb
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 2 406 144 144 296 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 296 144 144 144 144 144 399 144 144 406 146 144 144 144 155 469 144 144 296 144 144 144 144 144 144 144 144 144 144 144 144 144 144 36 144 406 155 144 144 144 155 144 406 144...
result:
ok Accepted.
Test #40:
score: 0
Accepted
time: 83ms
memory: 84992kb
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 454 7 358 150 192 287 357 343 494 324 308 249 435 435 5 40 466 182 292 486 262 182 455 471 81 2 81 7 497 82 4 75 486 220 192 227 365 342 350 496 428 51 104 96 260 494 102 202 230 249 426 343 96 381 192 270 475 388 479 217 205 180 287 455 96 412 407 233 25 343 453 90 345 136 4 475 116 ...
result:
ok Accepted.
Test #41:
score: 0
Accepted
time: 69ms
memory: 87460kb
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 163 414 441 353 350 104 379 438 292 189 27 482 408 243 239 403 307 348 93 128 55 498 246 230 457 348 453 241 400 90 394 93 73 177 243 356 4 463 374 403 221 27 328 416 470 70 416 31 187 90 143 189 348 364 113 104 165 419 8 31 304 379 283 446 408 94 187 225 457 232 179 263 408 217 328 235 17...
result:
ok Accepted.
Test #42:
score: 0
Accepted
time: 88ms
memory: 90992kb
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: 70ms
memory: 86276kb
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 436 67 159 245 52 245 168 194 159 481 17 371 4 91 336 324 207 15 422 481 294 427 171 171 112 422 4 207 161 159 80 43 168 161 324 206 110 4 52 481 4 4 4 4 468 213 348 436 294 348 336 15 354 112 236 277 236 17 4 4 226 168 17 194 17 348 213 422 481 28 226 381 4 422 213 371 371 4 66 43 17 207 11...
result:
ok Accepted.
Test #44:
score: 0
Accepted
time: 70ms
memory: 84216kb
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:
356 226 341 237 474 351 457 474 435 482 31 414 457 377 71 127 401 482 416 91 310 373 137 474 236 91 482 44 416 265 329 101 359 265 184 405 356 351 138 341 385 329 416 101 127 138 373 35 414 156 184 346 416 341 150 70 150 384 416 70 46 265 46 137 236 20 226 377 474 91 137 384 341 439 482 346 482 46 3...
result:
ok Accepted.
Test #45:
score: 0
Accepted
time: 74ms
memory: 90860kb
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 2 357 8 250 24 24 330 453 51 400 307 250 8 330 453 24 8 24 24 24 2 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 2 307 24 177 400 51 400 2 250 250 24 330 250 24 24 400 400 24 330...
result:
ok Accepted.
Test #46:
score: 0
Accepted
time: 65ms
memory: 90176kb
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 238 471 28 179 365 471 28 365 238 238 28 498 371 416 371 416 28 76 471 177 177 28 191 416 179 471 365 76 238 371 179 76 177 76 371 365 365 238 76 76 238 76 177 371 471 2 371 471 383 179 76 177 177 371 28 371 498 498 2 2 498 416 498 471 177 179 177 177 2 498 2 498 416 416 383 28 365 2 371 416 371...
result:
ok Accepted.
Test #47:
score: 0
Accepted
time: 64ms
memory: 91528kb
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: 0
Time Limit Exceeded
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #48:
score: 25
Accepted
time: 1470ms
memory: 611608kb
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 1588 1645 1527 639 54 325 1534 531 122 1196 1497 531 639 1534 54 311 1645 1194 1534 1525 2 1534 531 824 325 971 1845 1497...
result:
ok Accepted.
Test #49:
score: 0
Accepted
time: 1454ms
memory: 617860kb
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 2 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 11...
result:
ok Accepted.
Test #50:
score: 0
Accepted
time: 1565ms
memory: 657284kb
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: 1606ms
memory: 665048kb
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 2 1706 785 1706 113 1597 1520 1652 1840 1746 785 180 1746 1923 536 411 1923 1772 606 1652 1697 782 785 782...
result:
ok Accepted.
Test #52:
score: 0
Accepted
time: 1623ms
memory: 651720kb
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: 1761ms
memory: 632964kb
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: 1777ms
memory: 648356kb
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 521 972 268 20 621 481 860 860 462 1578 307 532 2 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 621 683 617 488 227 889 176 20 465 481 1993 306...
result:
ok Accepted.
Test #55:
score: 0
Accepted
time: 1740ms
memory: 645492kb
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 834 1286 1300 364 468 1182 532 678 364 295 364 1817 858 1171 1978 1978 1096 858 1518 678 1372 1093 94 364 1523 1518 391 93...
result:
ok Accepted.
Test #56:
score: 0
Accepted
time: 1688ms
memory: 649224kb
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 1811 1061 1302 1491 1235 2 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 1791 1...
result:
ok Accepted.
Test #57:
score: 0
Accepted
time: 1972ms
memory: 630628kb
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 2 745 120 775 603 2 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 1343 699...
result:
ok Accepted.
Test #58:
score: 0
Accepted
time: 1744ms
memory: 599644kb
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 1412 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 367 92 732 649 466 872 742 8...
result:
ok Accepted.
Test #59:
score: 0
Accepted
time: 1824ms
memory: 655804kb
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:
558 558 8 132 1264 1571 285 1505 1190 8 1160 1063 191 474 1348 1763 8 1831 191 518 1350 1073 1839 1843 486 1676 1263 1775 1868 1171 576 665 1967 558 1899 487 558 1334 1763 1369 1133 1516 1399 361 47 1609 7 298 1219 8 1345 1372 1661 18 765 132 1110 1843 602 282 8 675 10 1750 1650 810 1633 1945 8 699 ...
result:
ok Accepted.
Test #60:
score: 0
Accepted
time: 1843ms
memory: 655768kb
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:
164 616 594 574 1187 648 1117 101 402 1451 363 1645 1758 602 761 156 1207 247 161 247 683 140 1090 25 1843 1041 1463 547 52 252 832 353 247 196 382 6 192 1090 475 686 1962 247 1758 70 1311 1774 1742 1662 1542 1260 972 11 475 1511 1736 81 175 350 1231 18 396 281 253 1681 886 628 3 1390 1990 800 522 3...
result:
ok Accepted.
Test #61:
score: 0
Accepted
time: 1759ms
memory: 663540kb
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 1986 1038 883 1179 1756 509 155 159 1384 772 772 1986 1937 1114 159 1162 1836 488 1581 1973 1447 43 1000 1114 1114 397 1986 651 772 159 768 1385 1761 1179 1254 1836 1973 418 1179 772 1756 353 418 1384 509 1886 1384 1384 772 1836 1276 1162 1658 883 78 78 1385 1000 1650 1650 1973 78 515 1276 1162 ...
result:
ok Accepted.
Test #62:
score: 0
Accepted
time: 1774ms
memory: 665676kb
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 1744 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 17...
result:
ok Accepted.
Test #63:
score: -25
Time Limit Exceeded
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:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #5:
0%