QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#595168 | #7869. 建设终末树 | byron10000 | 100 ✓ | 1978ms | 863636kb | C++14 | 6.0kb | 2024-09-28 12:48:42 | 2024-09-28 12:48:42 |
Judging History
answer
#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_) for(int V_=(A_), V_##_END=(B_); V_>=V_##_END; V_--)
#ifdef _WIN32
#define long __int64
#endif
#if defined(_LOCAL_) && 0
#undef assert
#define assert(expr) ({ if(!(expr)) asm("int3"); 0; })
#endif
using namespace std;
const int MAXN=2010,MAXQ=5e5+10;
int n,m,qn,ans[MAXN]; vector<int> G[MAXN];
// 2 Sat
int var(int i,int x){ return i*2+x; }
int neg(int u){ return u^1; }
struct TwoSat{
static const int MAXN=4e7,MAXM=8e7;
int nnd;
struct{ int v,nxt; } E[MAXM]; int head[MAXN],ecnt;
void _add(int u,int v){ E[++ecnt]={v,head[u]},head[u]=ecnt; }
void add(int u,int v){
_add(u,v);
if(!(neg(v)==u&&neg(u)==v)) _add(neg(v),neg(u));
}
int dfn[MAXN],low[MAXN],dfnc,stk[MAXN],stkp,col[MAXN],ncol; bool instk[MAXN],sol[MAXN];
void tarjan(int u){
dfn[u]=low[u]=++dfnc; stk[++stkp]=u,instk[u]=1;
for(int i=head[u]; i; i=E[i].nxt){
int v=E[i].v;
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(instk[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
col[u]=++ncol,instk[u]=0;
int v;
while((v=stk[stkp--])!=u) col[v]=ncol,instk[v]=0;
}
}
bool solve(){
assert(nnd*2+1<MAXN&&ecnt<MAXM);
RNG(u,2,2*nnd+1){
if(!dfn[u]) tarjan(u);
}
RNG(i,1,nnd){
if(col[var(i,0)]==col[var(i,1)]) return 0;
auto a=col[var(i,1)]<col[var(i,0)]; sol[var(i,0)]=!a,sol[var(i,1)]=a;
}
return 1;
}
} ts;
// Tree info
struct DSU{
int fa[MAXN];
void init(){ iota(fa+1,fa+m+1,1); }
int find(int u){ return u==fa[u]?u:fa[u]=find(fa[u]); }
void merge(int u,int v){
if((u=find(u))!=(v=find(v))) fa[v]=u;
}
} dsu[MAXN][11];
int dfn[MAXN],dfnc,fa[MAXN][11],dep[MAXN];
void dfs1(int u,int fa_){
fa[u][0]=fa_,dfn[u]=++dfnc,dep[u]=dep[fa_]+1,dsu[u][0].init();
RNG(i,1,__lg(dep[u])) fa[u][i]=fa[fa[u][i-1]][i-1],dsu[u][i].init();
for(int v:G[u]){
if(v!=fa_) dfs1(v,u);
}
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
int d=dep[u]-dep[v];
RNG(i,0,10){
if((d>>i)&1) u=fa[u][i];
}
if(u==v) return u;
IRNG(i,10,0){
if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
}
return fa[u][0];
}
// Merge edges
void upd(int u,int d,vector<int>& S){
if(!d||S.size()==1) return;
IRNG(i,10,0){
if((d>>i)&1){
RNG(j,1,int(S.size())-1) dsu[u][i].merge(S[0],S[j]);
u=fa[u][i];
}
}
}
void dfs2(int u){
for(auto v:G[u]){
if(v!=fa[u][0]) dfs2(v);
}
IRNG(i,__lg(dep[u]),1){
int v=fa[u][i-1];
RNG(x,1,m,y){
if((y=dsu[u][i].find(x))!=x) dsu[u][i-1].merge(x,y),dsu[v][i-1].merge(x,y);
}
}
}
int id[MAXN][MAXN];
// Mark connection block
bool mark[MAXN],mark1[MAXN];
void dfs3(bool* mark,int u){
for(int v:G[u]){
if(v!=fa[u][0]) dfs3(mark,v),mark[u]|=mark[v];
}
}
vector<int> A[MAXN];
struct{ vector<int> U,S; } Q[MAXQ];
int do_mark(bool* mark,const vector<int>& S){
fill_n(mark+1,n,0);
for(int u:S) mark[u]=1;
int r=S[0];
RNG(j,1,int(S.size())-1) r=lca(r,S[j]);
dfs3(mark,r);
return r;
}
int main(){
#if defined(_LOCAL_)
freopen("in","r",stdin);
freopen("out","w",stdout);
#else
// freopen("wukong.in","r",stdin);
// freopen("wukong.out","w",stdout);
#endif
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m>>qn;
// if(n>1000) return 0;
RNG(_,1,n-1,u,v) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
RNG(i,1,m){
int k; cin>>k; A[i].resize(k);
for(int& u:A[i]) cin>>u;
}
RNG(i,1,qn){
int k; cin>>k; Q[i].U.resize(k);
for(int& u:Q[i].U) cin>>u;
cin>>k; Q[i].S.resize(k);
for(int& x:Q[i].S) cin>>x;
}
dfs1(1,0);
// Restriction 2
RNG(i,1,qn){
auto& U=Q[i].U;
sort(U.begin(),U.end(),[](int u,int v){ return dfn[u]<dfn[v]; });
RNG(j,1,int(U.size())-1){
int u=U[j-1],v=U[j],w=lca(u,v);
upd(u,dep[u]-dep[w],Q[i].S),upd(v,dep[v]-dep[w],Q[i].S);
}
}
dfs2(1);
RNG(u,2,n){
RNG(i,1,m){
int& x=id[dsu[u][0].find(i)][u];
if(!x) x=++ts.nnd;
id[i][u]=x;
}
}
// Restriction 1
RNG(i,1,m){
auto& S=A[i];
int r=do_mark(mark,S);
if(r!=1) ts.add(var(id[i][r],0),var(id[i][r],1));
RNG(u,2,n){
if(!mark[u]&&mark[fa[u][0]]) ts.add(var(id[i][u],1),var(id[i][u],0));
}
S.clear();
RNG(u,1,n){
if(mark[u]) S.push_back(u);
}
}
// Only 1 output edge
RNG(i,1,m){
RNG(u,1,n){
int lst=0;
for(int v:G[u]){
int x=(v==fa[u][0]?var(id[i][u],0):var(id[i][v],1));
int y=var(++ts.nnd,1);
if(lst) ts.add(lst,y),ts.add(lst,neg(x));
ts.add(x,y);
lst=y;
}
}
}
if(!ts.solve()){ cout<<-1<<"\n"; return 0; }
RNG(i,1,m){
RNG(u,1,n){
int c=0;
for(int v:G[u]){
int x=(v==fa[u][0]?var(id[i][u],0):var(id[i][v],1));
c+=ts.sol[x];
}
assert(c<=1);
if(!c){ assert(!ans[i]); ans[i]=u; }
}
assert(ans[i]);
assert(find(A[i].begin(),A[i].end(),ans[i])!=A[i].end());
}
// RNG(i,1,qn){
// int r1=do_mark(mark,Q[i].U); mark[r1]=0;
// vector<int> S=Q[i].S;
// for(int& x:S) x=ans[x];
// int r2=do_mark(mark1,S); mark1[r2]=0;
// RNG(u,1,n) assert(!(mark[u]&&mark1[u]));
// }
RNG(i,1,m) cout<<ans[i]<<" ";
cout<<"\n";
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1568ms
memory: 803516kb
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: 10
Accepted
time: 1556ms
memory: 801028kb
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: 10
Accepted
time: 1539ms
memory: 795220kb
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: 10
Accepted
time: 1562ms
memory: 783608kb
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: 10
Accepted
time: 1558ms
memory: 774300kb
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: 10
Accepted
time: 1581ms
memory: 807728kb
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: 10
Accepted
time: 1550ms
memory: 809500kb
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: 37476kb
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: 15
Accepted
time: 4ms
memory: 38448kb
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 3 9 3 8 3 9 3
result:
ok Accepted.
Test #10:
score: 15
Accepted
time: 3ms
memory: 38000kb
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 2 9 10 10 3 3 1
result:
ok Accepted.
Test #11:
score: 15
Accepted
time: 0ms
memory: 36796kb
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: 15
Accepted
time: 3ms
memory: 36760kb
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 7 7 7 7 7 7 7 7 7
result:
ok Accepted.
Test #13:
score: 15
Accepted
time: 4ms
memory: 36872kb
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:
4 4 4 4 4 4 4 4 4 4
result:
ok Accepted.
Test #14:
score: 15
Accepted
time: 0ms
memory: 36712kb
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 10 10 10
result:
ok Accepted.
Test #15:
score: 15
Accepted
time: 4ms
memory: 35500kb
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: 15
Accepted
time: 0ms
memory: 37268kb
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: 15
Accepted
time: 0ms
memory: 37332kb
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 8
result:
ok Accepted.
Test #18:
score: 15
Accepted
time: 4ms
memory: 38544kb
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:
8 8 8 8 10 9 9 9 8 7
result:
ok Accepted.
Subtask #3:
score: 20
Accepted
Test #19:
score: 20
Accepted
time: 55ms
memory: 121452kb
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 112 341 253 275 174 1 378 452 74 29 132 266 213 4 47 1 21 479 342 390 375 207 365 112 472 378 253 435 92 402 350 431 322 10...
result:
ok Accepted.
Test #20:
score: 20
Accepted
time: 73ms
memory: 117104kb
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 272 117 83 272 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 38...
result:
ok Accepted.
Test #21:
score: 20
Accepted
time: 63ms
memory: 115476kb
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 472 96 33 421 57 269 136 57 211 369 176 442 438 117 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 193 200 10 369 440 301 6 57 221 200 438 172 96 358 458 21 7 395 254 455 133 405 274 200 298 412 421 200 200 355 266...
result:
ok Accepted.
Test #22:
score: 20
Accepted
time: 66ms
memory: 121356kb
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: 20
Accepted
time: 60ms
memory: 116940kb
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: 20
Accepted
time: 63ms
memory: 117588kb
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: 20
Accepted
time: 54ms
memory: 116960kb
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: 20
Accepted
time: 67ms
memory: 116452kb
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: 20
Accepted
time: 71ms
memory: 119172kb
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: 71ms
memory: 121884kb
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 71 71 28 17 28 222 380 51 442 222 488 28 479 488 488 222 28 298 42 28...
result:
ok Accepted.
Test #29:
score: 20
Accepted
time: 76ms
memory: 122328kb
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 293 293 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 293 237...
result:
ok Accepted.
Test #30:
score: 20
Accepted
time: 68ms
memory: 117916kb
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: 20
Accepted
time: 62ms
memory: 120876kb
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: 20
Accepted
time: 81ms
memory: 125232kb
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 306 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 ...
result:
ok Accepted.
Test #33:
score: 20
Accepted
time: 72ms
memory: 123908kb
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: 20
Accepted
time: 68ms
memory: 117508kb
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 298 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: 20
Accepted
time: 55ms
memory: 122364kb
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 391 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 38...
result:
ok Accepted.
Test #36:
score: 20
Accepted
time: 56ms
memory: 120540kb
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: 20
Accepted
time: 50ms
memory: 122380kb
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 390 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 390 6 15 54 348 407 481 91 8 287 366 8 87 175 25 156 481 366 333 458 390 177 35 287 24 392 240 494 34 24 330 79 15 400 24 458 390 91 414 27...
result:
ok Accepted.
Test #38:
score: 20
Accepted
time: 69ms
memory: 124312kb
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 352 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 48...
result:
ok Accepted.
Test #39:
score: 20
Accepted
time: 81ms
memory: 124100kb
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 399 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 1...
result:
ok Accepted.
Test #40:
score: 20
Accepted
time: 60ms
memory: 118460kb
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 275 384 7 279 280 249 287 357 351 499 498 292 275 435 435 461 40 466 2 252 486 262 2 308 230 140 26 140 154 497 82 176 417 486 10 249 195 26 309 350 463 185 185 104 96 203 499 102 460 92 275 403 351 96 323 249 270 475 69 26 179 407 480 287 308 96 99 239 308 131 351 434 90 193 467 114 475 ...
result:
ok Accepted.
Test #41:
score: 20
Accepted
time: 64ms
memory: 117240kb
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 350 104 379 438 292 189 27 482 88 243 96 403 307 348 93 128 167 498 469 131 457 348 453 241 400 90 394 93 73 449 243 356 4 193 374 403 221 27 328 416 410 70 416 31 187 90 143 189 348 364 113 104 439 419 8 31 304 379 283 446 387 94 187 225 457 111 179 263 387 217 328 235 111...
result:
ok Accepted.
Test #42:
score: 20
Accepted
time: 62ms
memory: 120644kb
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: 20
Accepted
time: 71ms
memory: 121808kb
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:
147 232 181 67 159 96 52 96 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 147 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 371...
result:
ok Accepted.
Test #44:
score: 20
Accepted
time: 59ms
memory: 121728kb
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: 20
Accepted
time: 61ms
memory: 117472kb
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 33 357 8 250 24 24 330 453 51 400 307 250 8 330 453 24 8 24 24 24 33 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 33 307 24 177 400 51 400 33 250 250 24 330 250 24 24 400 400 24...
result:
ok Accepted.
Test #46:
score: 20
Accepted
time: 57ms
memory: 122092kb
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 348 371 471 383 179 76 177 177 371 28 371 498 498 348 348 498 416 498 471 177 179 177 177 348 498 348 498 416 416 383 28 365 348...
result:
ok Accepted.
Test #47:
score: 20
Accepted
time: 67ms
memory: 118668kb
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: 1830ms
memory: 862184kb
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 1525 1534 531 824 325 971 1845 1...
result:
ok Accepted.
Test #49:
score: 25
Accepted
time: 1824ms
memory: 856624kb
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 1024 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: 25
Accepted
time: 1763ms
memory: 805276kb
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: 25
Accepted
time: 1762ms
memory: 800336kb
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 1678 1706 785 1706 113 1597 1520 1652 1840 1746 785 180 1746 1923 536 411 1923 1772 606 1652 1697 782 785 ...
result:
ok Accepted.
Test #52:
score: 25
Accepted
time: 1707ms
memory: 782148kb
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: 25
Accepted
time: 1725ms
memory: 783104kb
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: 25
Accepted
time: 1801ms
memory: 807080kb
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 1181 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 ...
result:
ok Accepted.
Test #55:
score: 25
Accepted
time: 1760ms
memory: 810760kb
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: 25
Accepted
time: 1751ms
memory: 806288kb
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 1811 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: 25
Accepted
time: 1932ms
memory: 814424kb
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 928 745 120 775 603 928 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...
result:
ok Accepted.
Test #58:
score: 25
Accepted
time: 1937ms
memory: 863636kb
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: 25
Accepted
time: 1762ms
memory: 770560kb
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 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 558 1899 487 558 1334 1763 1369 1133 1516 1399 361 47 1612 697 298 1219 944 1345 1372 1661 569 765 132 1110 1843 602 282 976 675 10 1750 1650 264 163...
result:
ok Accepted.
Test #60:
score: 25
Accepted
time: 1732ms
memory: 771864kb
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 131 574 1187 648 1117 101 1544 1451 1369 1645 959 602 761 156 714 247 161 247 683 125 1090 25 1843 937 1463 701 52 252 1035 353 247 196 607 6 192 1090 475 1222 830 247 959 70 1481 1774 1742 1662 1542 1260 972 11 475 1559 1736 195 175 350 1231 1041 82 1952 253 1681 1269 628 63 1390 1990 800 1...
result:
ok Accepted.
Test #61:
score: 25
Accepted
time: 1617ms
memory: 758176kb
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: 25
Accepted
time: 1610ms
memory: 762624kb
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 1759 464 503 1759 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 1759 951 1064 715 1221 1459 1221 1365 1078 994 32 1039 1759 1265 1590 1446 1459 1874 1358...
result:
ok Accepted.
Test #63:
score: 25
Accepted
time: 1776ms
memory: 779468kb
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: 10
Accepted
Dependency #1:
100%
Accepted
Dependency #5:
100%
Accepted
Test #64:
score: 10
Accepted
time: 1893ms
memory: 794780kb
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 1268 330 1379 159 595 473 1063 1429 1795 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...
result:
ok Accepted.
Test #65:
score: 10
Accepted
time: 1916ms
memory: 833312kb
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
Accepted
time: 1919ms
memory: 766024kb
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 ...
output:
886 479 1840 947 1898 224 877 1961 1625 1544 1544 1840 1332 1389 1625 1898 1466 886 224 617 1404 1052 1629 43 1629 877 1898 43 1404 1961 1544 390 1389 196 947 947 540 886 43 1389 362 947 1347 1840 224 1840 589 947 1389 1898 1625 43 1629 877 1961 691 1389 1961 479 1898 1840 479 390 617 1898 1544 1031...
result:
ok Accepted.
Test #67:
score: 10
Accepted
time: 1821ms
memory: 771056kb
input:
1998 1999 16058 691 172 248 257 1915 1925 797 1761 1123 812 74 221 983 1425 1180 126 1019 294 1402 1603 1501 406 657 619 619 1232 989 1045 979 475 100 65 902 159 824 1058 120 1115 659 582 400 579 1151 327 213 1884 1860 1632 361 800 1300 1232 1691 1929 1253 1977 1710 590 1447 672 1571 1618 1829 1912 ...
output:
1646 1737 610 834 181 1474 1474 619 849 505 1253 1253 619 741 1447 889 106 619 741 758 1198 619 1737 1447 1612 1737 373 1447 851 505 849 44 1547 800 181 373 834 322 373 1547 505 1554 758 619 949 849 979 741 1447 373 1737 322 466 44 1474 181 741 1547 949 466 1646 322 849 322 106 1646 1547 758 373 466...
result:
ok Accepted.
Test #68:
score: 10
Accepted
time: 1760ms
memory: 755752kb
input:
1999 2000 15762 727 1155 686 1728 592 1649 1843 1253 210 209 1302 1332 1597 736 783 47 208 1404 233 1678 1569 466 533 272 886 1008 1001 1080 1332 1998 1494 1653 1427 1005 1935 1615 1822 1861 1210 1264 889 1531 1981 228 1692 900 903 142 343 1148 1147 435 728 218 504 857 1931 568 1523 975 1422 1731 11...
output:
-1
result:
ok Accepted.
Test #69:
score: 10
Accepted
time: 1831ms
memory: 752132kb
input:
1998 1999 12015 1333 282 690 525 1915 571 1016 389 1491 1981 191 1379 1234 528 202 1277 1774 108 523 440 1918 1471 369 17 239 1883 269 291 901 1547 969 559 463 1086 589 493 570 1048 1308 916 1027 1948 1625 1183 111 52 957 1797 1068 1836 690 966 371 1313 1742 124 1948 1198 1669 1724 1719 1377 1377 59...
output:
-1
result:
ok Accepted.
Test #70:
score: 10
Accepted
time: 1978ms
memory: 808976kb
input:
1999 1999 105090 1544 1617 1033 9 1969 1798 1975 547 1420 884 663 844 682 1913 1460 1861 1603 1269 281 1009 258 467 812 1431 954 1663 1960 126 227 326 1256 1689 1968 1028 970 433 192 63 75 88 1476 1589 1058 1716 1645 1554 1570 1185 774 100 179 1514 1491 973 1974 168 603 1019 528 16 1536 1943 332 183...
output:
1527 1289 1280 1280 9 341 181 341 341 1925 1365 442 9 1025 1552 458 1167 1803 36 740 740 119 762 1514 36 349 1453 1552 9 9 88 558 740 349 9 1365 781 106 349 9 1025 1589 36 106 9 181 1280 885 903 430 1167 539 621 1514 1381 1202 848 1381 1925 1365 1202 88 1985 430 442 458 1373 36 1638 430 9 341 816 45...
result:
ok Accepted.
Test #71:
score: 10
Accepted
time: 1755ms
memory: 768548kb
input:
1998 1999 17168 249 98 1150 612 1350 1389 1802 1090 1275 1619 1408 1318 632 1274 1187 1410 1775 721 1323 467 164 889 292 30 1188 964 803 763 438 1380 42 1492 1066 742 36 747 1369 1674 487 858 25 493 1460 1600 349 440 1876 1290 1276 81 897 1772 204 1797 1204 1302 211 903 1169 1890 910 736 759 1614 34...
output:
48 1312 1426 1556 1285 30 698 1210 1115 1510 1566 889 1105 1749 831 1749 463 207 463 1719 1105 1791 619 267 1831 831 213 1749 411 1285 698 1285 1510 340 1306 1467 164 1513 1650 926 1513 530 111 889 583 267 1899 926 1509 908 1426 30 1510 926 1362 1306 889 1306 1873 1831 1899 1275 164 1077 1791 1080 5...
result:
ok Accepted.
Test #72:
score: 10
Accepted
time: 1851ms
memory: 767836kb
input:
1998 1999 12493 1763 1335 1363 1440 653 651 1963 1814 1872 1827 1780 1295 900 1346 1103 935 931 767 1148 1329 1819 1980 13 961 1935 1110 1765 1809 631 815 1023 513 956 691 1223 576 906 505 974 1252 69 1051 1895 126 313 1159 320 954 382 911 998 1778 1206 414 201 1393 1243 1472 584 1854 1144 1988 1171...
output:
343 1312 414 1251 885 792 1056 1056 1590 1179 16 1009 386 945 1081 1009 1636 718 1906 1549 1872 1590 718 670 386 36 1590 386 1251 1677 945 16 386 945 399 386 1331 228 228 885 1986 1312 414 426 1906 817 1331 718 1009 426 853 753 1081 1906 885 1590 753 1590 1912 1986 414 1351 414 853 1251 1986 414 853...
result:
ok Accepted.
Test #73:
score: 10
Accepted
time: 1847ms
memory: 770676kb
input:
2000 2000 13003 801 1607 625 1129 1318 743 1391 1618 16 160 1132 116 1478 1274 1942 1886 1397 1163 101 738 1467 261 1328 1884 979 1528 224 600 789 3 1065 1989 809 1038 151 1703 982 660 1023 1314 1426 400 293 1003 1455 1752 580 889 1437 798 747 1388 837 788 350 387 1743 435 1027 791 1532 1242 1306 60...
output:
70 1117 1117 1532 70 1920 1267 153 919 1835 1243 1532 227 1243 1855 1914 1311 928 1855 1915 1835 1074 1855 1835 1267 759 1267 153 43 81 247 1243 1532 1835 1128 1532 7 780 1855 780 979 1532 7 21 1536 1074 153 1532 823 43 1532 1128 1243 1001 7 247 928 1835 526 63 526 227 1532 1835 1536 247 526 1920 24...
result:
ok Accepted.
Test #74:
score: 10
Accepted
time: 1747ms
memory: 761196kb
input:
2000 2000 16786 1499 508 1291 200 970 1542 1250 838 951 302 951 380 1241 187 1038 1874 1248 152 1438 381 1056 1508 88 60 1468 694 529 1608 1014 573 1180 1960 1321 937 1764 497 1167 416 35 1925 430 1916 1753 613 1953 379 1774 1568 1542 1571 1235 1957 1206 1760 1972 26 257 1956 1475 317 770 72 511 188...
output:
1104 1268 190 1885 116 337 1035 1595 211 1634 1634 1593 1793 1694 64 177 1358 173 937 57 240 184 1506 1333 1853 1341 326 1816 1058 1693 1944 725 151 1867 1168 1793 1421 1291 1132 1171 1442 485 1532 900 769 1329 784 1990 213 57 1168 34 471 225 830 1181 1708 608 1512 1766 1498 1114 1596 1114 1056 837 ...
result:
ok Accepted.
Test #75:
score: 10
Accepted
time: 1902ms
memory: 776292kb
input:
1999 2000 250000 1881 1788 312 997 172 834 1247 846 297 645 108 841 613 1160 1497 906 182 311 1257 694 1761 1188 1825 1841 1291 1815 1583 144 903 389 739 1046 278 1356 636 1878 1636 325 1298 186 1886 89 73 1470 1738 825 372 208 487 453 45 408 1990 818 1087 1122 116 1030 344 1448 55 1994 653 683 549 ...
output:
180 90 1376 1170 923 1823 90 1457 1826 15 910 761 217 771 1845 1555 1107 192 1776 857 217 1563 1922 1900 845 1032 1542 1612 106 1792 265 1500 612 1127 1325 850 180 926 5 1905 90 739 420 1427 284 1462 826 865 943 1206 1589 1629 1754 942 1177 1808 1381 539 966 1610 1170 45 1198 976 517 384 1433 967 89...
result:
ok Accepted.
Test #76:
score: 10
Accepted
time: 1935ms
memory: 774532kb
input:
1998 1999 250000 49 951 742 1017 1058 1368 1185 1635 233 1956 1201 1123 192 1233 990 833 1024 701 1266 490 1912 1146 1750 1977 859 1685 1180 255 1055 1494 917 1 698 750 359 90 1889 543 1030 383 1097 1130 257 1751 1502 177 934 1898 1752 594 1254 246 1224 899 458 491 583 527 1730 55 193 69 886 165 172...
output:
497 875 1722 1643 1903 811 989 959 1264 911 1931 868 1235 1670 1006 682 1596 951 381 1100 124 394 1858 1493 1319 685 497 430 1274 1371 457 91 1122 1059 1100 822 1230 459 457 1460 1702 822 52 1428 449 1963 1561 1890 1428 1132 975 1038 1869 1224 1662 757 381 1232 1074 633 149 358 459 130 911 894 1580 ...
result:
ok Accepted.
Test #77:
score: 10
Accepted
time: 1899ms
memory: 777248kb
input:
1999 1998 250000 627 799 1306 397 1906 1040 1910 861 1909 334 570 219 1109 1213 1929 566 1636 992 1267 1914 981 123 228 1981 1406 1734 1624 59 1502 1042 480 1680 1281 916 663 1462 348 1159 77 36 1193 837 9 411 493 260 576 1763 218 222 1140 1625 1297 1140 1569 1334 835 118 1592 474 98 394 639 1940 27...
output:
1360 1606 1605 1586 1131 1027 1369 1360 1356 194 1852 1548 1324 653 1586 1832 1586 1892 791 1868 1548 1852 1479 144 1642 1525 627 1605 1868 1336 1586 913 29 144 1336 952 1336 1027 529 928 1892 144 913 1686 144 1336 928 1606 1356 1987 1892 3 1479 1336 1841 1642 1642 1369 1987 28 111 529 1323 610 1525...
result:
ok Accepted.
Test #78:
score: 10
Accepted
time: 1843ms
memory: 770140kb
input:
1998 2000 250000 536 1392 532 1072 687 636 880 477 1342 244 1103 1982 1288 1852 1153 467 161 870 1872 1537 751 1627 1269 1313 755 181 1272 142 302 1879 1558 720 314 405 86 1641 579 1188 497 172 1080 1747 1148 651 339 630 1035 592 810 917 882 1665 1157 1598 960 35 1599 277 467 1351 887 759 1786 472 4...
output:
373 1677 863 727 1737 388 727 1428 863 1301 1959 610 1677 436 214 1464 998 171 998 1871 1373 1905 556 1677 695 727 1297 646 47 1905 1959 47 1785 373 1179 703 1676 1228 373 138 343 556 1919 47 1871 47 1794 1493 550 1373 293 949 293 1434 47 949 343 214 556 368 138 214 1959 1905 1301 533 388 214 1664 4...
result:
ok Accepted.
Test #79:
score: 10
Accepted
time: 1958ms
memory: 786432kb
input:
1998 1999 250000 1628 1326 1311 363 1754 463 1309 883 238 469 726 1768 840 350 824 1191 241 4 1671 312 223 540 1948 1430 1510 133 1920 1181 1454 279 1205 113 195 1887 1837 805 591 1050 321 57 1624 310 1086 136 680 1055 1398 605 1372 1370 62 1962 236 19 658 1448 411 1889 1147 1170 1707 1048 1316 1378...
output:
-1
result:
ok Accepted.