QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#594961#7869. 建设终末树byron1000045 1854ms851324kbC++145.4kb2024-09-28 11:36:352024-09-28 11:36:48

Judging History

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

  • [2024-09-28 11:36:48]
  • 评测
  • 测评结果:45
  • 用时:1854ms
  • 内存:851324kb
  • [2024-09-28 11:36:35]
  • 提交

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=2e7,MAXM=6e7;
    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,sol[MAXN]; bool instk[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(){
        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,1){
        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];
void dfs3(int u){
    for(int v:G[u]){
        if(v!=fa[u][0]) dfs3(v),mark[u]|=mark[v];
    }
}
vector<int> A[MAXN];
struct{ vector<int> U,S; } Q[MAXQ];
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;
    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){
        fill_n(mark+1,n,0);
        auto& S=A[i];
        for(int u:S) mark[u]=1;
        int r=S[0];
        RNG(j,1,int(S.size())-1) r=lca(r,S[j]);
        dfs3(r);
        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));
        }
    }
    // 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){
            bool flag=0;
            for(int v:G[u]){
                int x=(v==fa[u][0]?var(id[i][u],0):var(id[i][v],1));
                flag|=ts.sol[x];
            }
            if(!flag){ ans[i]=u; continue; }
        }
    }
    RNG(i,1,m) cout<<ans[i]<<" ";
    cout<<"\n";
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1854ms
memory: 772308kb

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: 1733ms
memory: 844724kb

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: 1690ms
memory: 830128kb

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: 1631ms
memory: 772856kb

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: 1547ms
memory: 772116kb

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: 1646ms
memory: 851324kb

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: 1598ms
memory: 802988kb

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: 4ms
memory: 35492kb

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: 0ms
memory: 34164kb

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: 34412kb

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: 37268kb

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: 0ms
memory: 37120kb

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: 0ms
memory: 35508kb

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: 34324kb

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: 33604kb

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: 4ms
memory: 36852kb

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: 34012kb

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: 3ms
memory: 34744kb

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: 68ms
memory: 122816kb

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: 74ms
memory: 117648kb

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: 77ms
memory: 122928kb

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: 77ms
memory: 117884kb

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: 70ms
memory: 120864kb

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: 74ms
memory: 118556kb

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: 80ms
memory: 121152kb

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: 75ms
memory: 120052kb

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: 65ms
memory: 119180kb

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: 0
Wrong Answer

Dependency #2:

100%
Accepted

Test #28:

score: 0
Wrong Answer
time: 71ms
memory: 121536kb

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 369 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 74 442 222 488 28 479 488 488 222 28 298 42 2...

result:

wrong answer restrict 76 is not satisfied.

Subtask #5:

score: 0
Skipped

Dependency #3:

100%
Accepted

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #5:

0%