QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#43682 | #4240. Tree Circles | justcyl | WA | 83ms | 3996kb | C++20 | 2.9kb | 2022-08-09 22:09:06 | 2022-08-09 22:09:24 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'