QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#820234	#9881. Diverge and Converge	XY_Eleven	WA	26ms	11312kb	C++14	8.1kb	2024-12-18 20:17:16	2024-12-18 20:17:18

Judging History

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

[2024-12-18 20:17:18]
评测

测评结果：WA
用时：26ms
内存：11312kb

查看

[2024-12-18 20:17:16]
提交

answer

#include <bits/stdc++.h>
// #include <windows.h>
// #include <bits/extc++.h>
// using namespace __gnu_pbds;
using namespace std;
//#pragma GCC optimize(3)
#define DB double
#define LL long long
#define ULL unsigned long long
#define in128 __int128
#define cint const int
#define cLL const LL
#define For(z,e1,e2) for(int z=(e1);z<=(e2);z++)
#define Rof(z,e1,e2) for(int z=(e2);z>=(e1);z--)
#define For_(z,e1,e2) for(int z=(e1);z<(e2);z++)
#define Rof_(z,e1,e2) for(int z=(e2);z>(e1);z--)
#define inint(e) scanf("%d",&e)
#define inll(e) scanf("%lld",&e)
#define inpr(e1,e2) scanf("%d%d",&e1,&e2)
#define in3(e1,e2,e3) scanf("%d%d%d",&e1,&e2,&e3)
#define outint(e) printf("%d\n",e)
#define outint_(e) printf("%d%c",e," \n"[i==n])
#define outint2_(e,e1,e2) printf("%d%c",e," \n"[(e1)==(e2)])
#define outll(e) printf("%lld\n",e)
#define outll_(e) printf("%lld%c",e," \n"[i==n])
#define outll2_(e,e1,e2) printf("%lld%c",e," \n"[(e1)==(e2)])
#define exc(e) if(e) continue
#define stop(e) if(e) break
#define ret(e) if(e) return
#define ll(e) (1ll*(e))
#define pb push_back
#define ft first
#define sc second
#define pii pair<int,int> 
#define pli pair<long long,int> 
#define vct vector 
#define clean(e) while(!e.empty()) e.pop()
#define all(ev) ev.begin(),ev.end()
#define sz(ev) ((int)ev.size())
#define debug(x) printf("%s=%d\n",#x,x)
#define x0 __xx00__
#define y1 __yy11__
#define ffo fflush(stdout)
cLL mod=998244353,G=404;
// cLL mod[2]={1686688681ll,1666888681ll},base[2]={166686661ll,188868881ll};
template <typename Type> void get_min(Type &w1,const Type w2) { if(w2<w1) w1=w2; } template <typename Type> void get_max(Type &w1,const Type w2) { if(w2>w1) w1=w2; }
template <typename Type> Type up_div(Type w1,Type w2) { return (w1/w2+(w1%w2?1:0)); }
template <typename Type> Type gcd(Type X_,Type Y_) { Type R_=X_%Y_; while(R_) { X_=Y_; Y_=R_; R_=X_%Y_; } return Y_; } template <typename Type> Type lcm(Type X_,Type Y_) { return (X_/gcd(X_,Y_)*Y_); }
template <typename Type> Type md(Type w1,const Type w2=mod) { w1%=w2; if(w1<0) w1+=w2; return w1; } template <typename Type> Type md_(Type w1,const Type w2=mod) { w1%=w2; if(w1<=0) w1+=w2; return w1; }
void ex_gcd(LL &X_,LL &Y_,LL A_,LL B_) { if(!B_) { X_=1ll; Y_=0ll; return ; } ex_gcd(Y_,X_,B_,A_%B_); X_=md(X_,B_); Y_=(1ll-X_*A_)/B_; } LL inv(LL A_,LL B_=mod) { LL X_=0ll,Y_=0ll; ex_gcd(X_,Y_,A_,B_); return X_; }
template <typename Type> void add(Type &w1,const Type w2,const Type M_=mod) { w1=md(w1+w2,M_); } void mul(LL &w1,cLL w2,cLL M_=mod) { w1=md(w1*md(w2,M_),M_); } template <typename Type> Type pw(Type X_,Type Y_,Type M_=mod) { Type S_=1; while(Y_) { if(Y_&1) mul(S_,X_,M_); Y_>>=1; mul(X_,X_,M_); } return S_; }
template <typename Type> Type bk(vector <Type> &V_) { auto T_=V_.back(); V_.pop_back(); return T_; } template <typename Type> Type tp(stack <Type> &V_) { auto T_=V_.top(); V_.pop(); return T_; } template <typename Type> Type frt(queue <Type> &V_) { auto T_=V_.front(); V_.pop(); return T_; }
template <typename Type> Type bg(set <Type> &V_) { auto T_=*V_.begin(); V_.erase(V_.begin()); return T_; } template <typename Type> Type bk(set <Type> &V_) { auto T_=*prev(V_.end()); V_.erase(*prev(V_.end())); return T_; }
mt19937 gen(time(NULL)); int rd() { return abs((int)gen()); }
int rnd(int l,int r) { return rd()%(r-l+1)+l; }

void main_init()
{

}
cint N=1.02e5;
int n;
int deg[N];
vct <array<int,2> > v1[N],v2[N];
vct <array<int,2> > ans;
vct <int> v[N];
bool b[N],vis[N];
void dfs(int p)
{
    vis[p]=true;
    for(auto i:v[p]) if(!vis[i])
        dfs(i);
}
void fin(int p,int p2,vct <array<int,3> > &e)
{
    For(i,1,n) { v[i].clear(); vis[i]=false; }
    for(auto [x,y,id]:e) v[x].pb(y),v[y].pb(x);
    vis[p]=true;
    dfs(p2);
}
void clr(int p,vct <array<int,3> > &e)
{
    vct <array<int,3> > tmp; tmp.clear();
    for(auto [x,y,id]:e) if(x!=p&&y!=p)
        tmp.pb((array<int,3>){x,y,id});
    tmp.swap(e);
}
void check(vct <array <int,3> > &e)
{
    For(i,1,n) { v[i].clear(); vis[i]=false; }
    for(auto [x,y,id]:e) v[x].pb(y),v[y].pb(x);
    For(i,1,n) if(!b[i]) { dfs(i); break; }
    For(i,1,n) if((!b[i])&&(!vis[i]))
    {
        printf("boom\n");
        exit(1);
    }
    For(i,1,n) vis[i]=false;
    for(auto [x,y,id]:e)
    {
        if(vis[id])
        {
            printf("boom\n");
            exit(1);
        }
        vis[id]=true;
    }
}
void main_solve()
{
    inint(n);
    // n=1000;
    vct <array<int,3> > e1,e2; e1.clear(),e2.clear();
    ans.clear();
    For_(i,1,n)
    {
        int x,y; inpr(x,y);
        // int x=1,y=i+1; if(rnd(0,1)) swap(x,y);
        // printf("%d %d\n",x,y);
        e1.pb((array<int,3>){x,y,i});
    }
    // For_(i,0,n-1) swap(e1[i],e1[rnd(0,i)]);
    For_(i,1,n)
    {
        int x,y; inpr(x,y);
        // int x=rnd(1,i),y=i+1; if(rnd(0,1)) swap(x,y);
        // printf("%d %d\n",x,y);
        e2.pb((array<int,3>){x,y,i});
    }
    // For_(i,0,n-1) swap(e2[i],e2[rnd(0,i)]);
    For(i,1,n) b[i]=false;
    For_(round,1,n)
    {
        // assert(sz(e1)==n-round&&sz(e2)==n-round);
        For(i,1,n)
        { deg[i]=0; v1[i].clear(); v2[i].clear(); }
        for(auto [x,y,id]:e1)
        {
            deg[x]++; deg[y]++;
            v1[x].pb((array<int,2>){y,id}); v1[y].pb((array<int,2>){x,id});
        }
        for(auto [x,y,id]:e2)
        {
            deg[x]++; deg[y]++;
            v2[x].pb((array<int,2>){y,id}); v2[y].pb((array<int,2>){x,id});
        }
        int p=0;
        // For(i,1,n) if((!b[i])&&((!p)||deg[i]<deg[p]))
        //     p=i;
        For(i,1,n) if((!b[i])&&deg[i]<=3)
        {
            p=i;
            break;
        }
        b[p]=true;
        // printf("p=%d\n",p);
        // if(deg[p]<=1||v1[p].empty()||v2[p].empty())
        // {
        //     printf("yeah!!!\n");
        //     exit(1);
        // }
        // printf("> p=%d\n",p);
        if(deg[p]==2)
        { ans.pb((array<int,2>){v1[p][0][1],v2[p][0][1]}); }
        else if(sz(v1[p])==1)
        {
            fin(p,v2[p][1][0],e2);
            int k=(int)(vis[v1[p][0][0]]);
            ans.pb((array<int,2>){v1[p][0][1],v2[p][k][1]});
            e2.pb((array<int,3>){v2[p][(k^1)][0],v1[p][0][0],v2[p][(k^1)][1]});
        }
        else
        {
            fin(p,v1[p][1][0],e1);
            int k=(int)(vis[v2[p][0][0]]);
            // printf("> k=%d\n",k);
            // printf("%d,%d ; %d,%d , %d,%d\n",v2[p][0][0],v2[p][0][1],v1[p][0][0],v1[p][0][1],v1[p][1][0],v1[p][1][1]);
            // printf("> %d %d\n",v2[p][0][1],v1[p][k][1]);
            ans.pb((array<int,2>){v1[p][k][1],v2[p][0][1]});
            e1.pb((array<int,3>){v1[p][(k^1)][0],v2[p][0][0],v1[p][(k^1)][1]});
        }
        clr(p,e1); clr(p,e2);
        // for(auto [x,y,id]:e1) if(b[x]||b[y])
        // {
        //     printf("?!\n");
        //     exit(1);
        // }
        // for(auto [x,y,id]:e2) if(b[x]||b[y])
        // {
        //     printf("?!\n");
        //     exit(1);
        // }
        // printf("e1\n");
        // for(auto [x,y,id]:e1) printf("%d %d %d\n",x,y,id);
        // printf("e2\n");
        // for(auto [x,y,id]:e2) printf("%d %d %d\n",x,y,id);
        check(e1); check(e2);
    }
    For_(i,0,n-1) printf("%d ",ans[i][0]); printf("\n");
    For_(i,0,n-1) printf("%d ",ans[i][1]); printf("\n");
    // if(sz(ans)!=n-1)
    // {
    //     printf("???\n");
    //     exit(1);
    // }
    // For_(i,0,n-1) if(ans[i][0]<1||ans[i][0]>=n||ans[i][1]<1||ans[i][1]>=n)
    // {
    //     printf("???\n");
    //     exit(1);
    // }
    // For_(i,0,n-1) For_(j,i+1,n-1)
    // {
    //     if(ans[i][0]==ans[j][0]||ans[i][1]==ans[j][1])
    //     {
    //         printf("???\n");
    //         exit(1);
    //     }
    // }
    // printf("WA please\n");
}
int main()
{
    // ios::sync_with_stdio(0); cin.tie(0);
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // srand(time(NULL));
    main_init();
    // int _; inint(_); For(__,1,_) // T>1 ?
        // printf("\n------------\n\n"),
        main_solve();
    return 0;
}
/*
3,1,1
1,2,2
2,3,2
1,2,1
*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 3ms

memory: 11048kb

input:

output:

1 2 3 
1 3 2

result:

ok Correct, N = 4

Test #2:

score: 0

Accepted

time: 0ms

memory: 11312kb

input:

2
1 2
2 1

output:

1 
1

result:

ok Correct, N = 2

Test #3:

score: 0

Accepted

time: 2ms

memory: 11220kb

input:

output:

3 4 1 2 5 6 
6 4 1 2 5 3

result:

ok Correct, N = 7

Test #4:

score: -100

Wrong Answer

time: 26ms

memory: 11204kb

input:

output:

249 575 25 952 889 775 67 286 586 411 424 925 466 614 440 798 116 493 210 549 1 843 709 569 613 548 907 276 142 332 819 463 403 457 12 562 39 682 397 392 100 24 140 407 904 807 591 626 603 388 149 13 384 271 921 36 304 235 366 272 958 559 557 431 505 596 104 191 515 70 336 470 986 892 316 11 858 924...

result:

wrong answer Wrong, N = 1000, not forming a tree