QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#43682#4240. Tree CirclesjustcylWA 83ms3996kbC++202.9kb2022-08-09 22:09:062022-08-09 22:09:24

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-09 22:09:24]
  • Judged
  • Verdict: WA
  • Time: 83ms
  • Memory: 3996kb
  • [2022-08-09 22:09:06]
  • Submitted

answer

#include <bits/stdc++.h>
#define F(i, x, y) for (int i = x; i <= y; i++)
#define D(i, x, y) for (int i = x; i >= y; i--)
#define pr printf
#define mst(a,b) memset(a,b,sizeof a)
#define SZ(x) ((int)x.size())
#define ll long long
#define x first
#define y second
#define pb emplace_back
#define mp make_pair
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr) 
#define YN(ok) cout << (ok ? "YES" : "NO") << '\n';

#ifdef LOCAL_DEFINE
#include "bits/debug.h"
#else
    #define DEB(...)  
#endif

using namespace std;

void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) { x=0;int ch=getchar(),f=0;while(ch<'0'||ch>'9') { if (ch=='-') f=1;ch=getchar();}while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}if(f)x=-x;read(oth...);}

const int N = 6e5 + 10,M=N*2,De=20,mo=998244353;
int to[M*2],lst[N],nxt[M*2],tot;

void initGraph(int n){
    tot=0;
    F(i,1,n) lst[i]=0;
}
void addEdge(int x,int y){
    to[++tot]=y;
    nxt[tot]=lst[x];
    lst[x]=tot;
}
int gf[N];
int getfather(int x){
    return gf[x]==x?x:gf[x]=getfather(gf[x]);
}
int n,m,nn;
int dep[N],fa[N][De+1],dfn[N];
int tim=0;
void dfs(int u,int pre){
    fa[u][0]=pre;
    dep[u]=dep[pre]+1;
    dfn[u]=++tim;
    for(int j=lst[u];j;j=nxt[j]){
        int v=to[j];
        if(v==pre) continue;
        
        dfs(v,u);
    }
}
bool cmp(int u,int v){
    return dfn[u]<dfn[v];
}
void preLCA(){
    F(j,1,De){
        F(i,1,n){
            fa[i][j]=fa[fa[i][j-1]][j-1];
        }
    }
}
int LCA(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    D(j,De,0){
        if(dep[fa[u][j]]>=dep[v]) u=fa[u][j];
    }
    // DEB(u,v);
    if(u==v) return u;
    D(j,De,0){
        if(fa[u][j]!=fa[v][j]){
            u=fa[u][j];
            v=fa[v][j];
        }
    }
    return fa[u][0];
}
signed main()
{
#ifdef LOCAL_DEFINE
   freopen("temp.in", "r", stdin);
#endif
    read(n);
    F(i,1,n*2+1) gf[i]=i;
    nn=n;
    F(i,1,n-1){
        int x,y;
        read(x,y);
        x=getfather(x),y=getfather(y);
        nn++;
        gf[x]=nn,gf[y]=nn;
        addEdge(nn,x);
        addEdge(nn,y);
    }
    dfs(nn,0);
    // F(i,1,nn){
    //     DEB(i,dep[i]);
    // }
    // DEB(LCA(1,2));
    int _;
    read(_);
    while(_--){
        int m;
        read(m);
        if(m==1) pr("%d\n",n);
        else{
            ll ans=1;
            vector<int> a;
            F(i,1,m){
                int x;
                read(x);
                a.pb(x);
            }
            sort(a.begin(),a.end(),cmp);
            DEB(a);
            F(i,0,m-1){
                int x=n;
                if(i!=0) x=min(LCA(a[i],a[i-1])-n,x);
                if(i!=m-1) x=min(LCA(a[i],a[i+1])-n,x);
                
                ans=1ll*ans*x%mo;
            }
            pr("%lld\n",ans);
        }
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3804kb

input:

3
1 2
2 3
2
3 1 2 3
2 1 3

output:

2
4

result:

ok 2 number(s): "2 4"

Test #2:

score: -100
Wrong Answer
time: 83ms
memory: 3996kb

input:

1000
251 1
610 251
1 621
610 534
617 1
27 617
54 534
251 435
610 984
1 850
291 610
251 461
51 27
376 617
461 310
36 850
36 351
456 461
461 171
456 294
949 294
688 1
833 610
174 534
435 841
841 60
556 251
251 423
655 376
688 188
610 448
456 549
894 841
65 688
65 522
421 435
382 65
894 613
617 789
880...

output:

103692246
890276899
688409059
168919245
970395612
717569254
745502159
247984856
405664929
439354332
593512354
930769278
705569304
213178240
728839014
957211456
11775217
656851740
253005072
693357588
682380603
97270105
259151687
99403216
48173992
681236362
381708391
589097919
820090626
942373415
5213...

result:

wrong answer 1st numbers differ - expected: '275623202', found: '103692246'