QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#425723 | #6452. Ski Resort | lmeowdn | WA | 6ms | 13508kb | C++14 | 4.5kb | 2024-05-30 16:14:27 | 2024-05-30 16:14:28 |
Judging History
answer
//Shirasu Azusa 2024.5
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=1e5+5;
int n,m,q,p[N],deg[N],fa[N][22],d[N],dfn[N],tick,b[N],sz[N],f[N][7],K,L;
vi e[N],r[N],t[N],g[N];
namespace Reach {
int vst[N],dfn[N],tick,sz[N]; bool rt[N];
vi p; bitset<N> fr[55],to[55];
void dfs(int u) {
dfn[u]=++tick, sz[u]=1; vst[u]=1;
for(int v:e[u]) {
if(vst[v]) rt[u]=1;
else dfs(v), sz[u]+=sz[v];
}
}
void work(int d,int s) {
queue<int>q; fr[d][s]=1; q.push(s);
while(!q.empty()) {
int u=q.front(); q.pop();
for(int v:e[u]) if(!fr[d][v]) fr[d][v]=1, q.push(v);
} to[d][s]=1; q.push(s);
while(!q.empty()) {
int u=q.front(); q.pop();
for(int v:r[u]) if(!to[d][v]) to[d][v]=1, q.push(v);
}
}
bool reach(int x,int y) {
if(dfn[x]<=dfn[y]&&dfn[y]<dfn[x]+sz[x]) return 1;
rep(i,0,(int)p.size()-1) if(fr[i][y]&&to[i][x]) return 1;
return 0;
}
void init() {
dfs(1);
rep(i,1,n) if(rt[i]) p.eb(i);
rep(i,0,(int)p.size()-1) work(i,p[i]);
}
} using Reach::reach;
int lca(int x,int y) {
if(d[x]<d[y]) swap(x,y); if(!x||!y) return x+y;
per(h,18,0) if(d[fa[x][h]]>=d[y]) x=fa[x][h];
per(h,18,0) if(fa[x][h]!=fa[y][h]) x=fa[x][h], y=fa[y][h];
return x==y?x:fa[x][0];
}
int climb(int x,int y) {
per(h,18,0) if(y&(1<<h)) x=fa[x][h]; return x;
}
void buildom() {
queue<int>q; q.push(1); d[1]=1;
while(!q.empty()) {
int u=q.front(); q.pop();
d[u]=d[fa[u][0]]+1, t[fa[u][0]].eb(u);
rep(h,1,20) fa[u][h]=fa[fa[u][h-1]][h-1];
for(int v:e[u]) {
fa[v][0]=lca(fa[v][0],u);
if(!--deg[v]) q.push(v);
}
}
}
void dfs(int u) {
dfn[u]=++tick, sz[u]=1;
for(int v:t[u]) dfs(v), sz[u]+=sz[v];
}
bool cmp(const int &x,const int &y) {return dfn[x]<dfn[y];}
bool chk(int x) {
//cout<<"chk "<<x<<" "<<L<<endl;
for(int y:g[L]) {
//cout<<" "<<y<<" "<<reach(x,y)<<endl;
if(dfn[y]<=dfn[x]&&dfn[x]<dfn[y]+sz[y]) continue;
else if(dfn[x]<=dfn[y]&&dfn[y]<dfn[x]+sz[x]) continue;
else if(reach(x,y)) return 0;
} return 1;
}
void dfs2(int u,int faa,int tp=0) {
//cout<<"DFSX "<<u<<" "<<faa<<endl;
rep(i,0,K) f[u][i]=0; f[u][0]=1; int resu=(u==L?0:chk(u));
if(!b[u]) {
for(int v:g[u]) {
dfs2(v,u,resu);
static int h[10];
rep(i,0,K) h[i]=0;
rep(i,0,K) rep(j,1,K-i) h[i+j]+=f[u][i]*f[v][j];
rep(i,0,K) f[u][i]=h[i];
}
}
if(tp) {
f[u][1]+=d[u]-d[faa];
} else if(resu||u==L) {
int x=u;
per(h,18,0) if(d[fa[x][h]]>d[faa]) {
if(chk(fa[x][h])) x=fa[x][h];
}
f[u][1]+=d[u]-d[x]+1;
}
//cout<<u<<" "<<f[u][0]<<" "<<f[u][1]<<" "<<f[u][2]<<endl;
}
int work() {
int k=read(), m=read(); L=0; vi ykn,ako; K=k;
rep(i,1,m) {int u=read(); L=lca(L,u); ykn.eb(u);}
if(k==1) return d[L];
for(int u:ykn) if(u==L) return 0;
sort(ykn.begin(),ykn.end(),cmp);
rep(i,0,m-2) ako.eb(lca(ykn[i],ykn[i+1]));
rep(i,0,m-1) ako.eb(ykn[i]), b[ykn[i]]=1;
sort(ako.begin(),ako.end(),cmp);
ako.resize(m=unique(ako.begin(),ako.end())-ako.begin());
rep(i,1,m-1) g[lca(ako[i-1],ako[i])].eb(ako[i]);
if(g[L].size()>k) return 0; dfs2(L,L);
for(int x:ako) b[x]=0, g[x].clear(); return f[L][k];
}
signed main() {
n=read(), m=read(), q=read();
rep(i,1,m) {
int u=read(), v=read();
e[u].eb(v), r[v].eb(u);
deg[v]++;
}
Reach::init();
buildom(); dfs(1);
rep(i,1,q) printf("%lld\n",work());
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 13136kb
input:
4 4 4 1 2 1 3 2 4 3 4 1 1 4 2 1 4 1 1 3 2 2 3 2
output:
2 0 2 1
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 6ms
memory: 13212kb
input:
8 10 4 1 2 2 3 1 3 3 6 6 8 2 4 2 5 4 7 5 7 7 8 2 3 4 5 6 2 2 6 8 1 1 6 1 1 8
output:
0 0 3 2
result:
ok 4 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 13468kb
input:
8 9 4 1 2 1 3 3 6 6 8 2 4 2 5 4 7 5 7 7 8 2 3 4 5 6 2 2 6 8 1 1 6 1 1 8
output:
2 0 3 2
result:
ok 4 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 13272kb
input:
8 8 2 1 2 1 3 2 4 4 5 5 8 3 6 6 7 7 8 2 2 5 7 1 1 8
output:
9 2
result:
ok 2 lines
Test #5:
score: -100
Wrong Answer
time: 6ms
memory: 13508kb
input:
8 8 1020 1 2 1 3 2 4 4 5 5 8 3 6 6 7 7 8 4 3 2 4 5 3 6 1 2 3 6 7 8 4 5 2 3 4 5 8 3 4 1 3 4 8 3 3 1 4 6 4 4 1 2 5 6 3 1 2 1 6 1 2 3 4 6 7 4 3 1 5 7 3 4 1 2 6 8 1 1 4 3 5 3 4 5 7 8 2 4 1 4 5 7 1 3 1 2 7 1 3 4 6 8 4 4 1 2 3 8 2 2 3 4 4 3 3 6 8 4 6 1 4 5 6 7 8 4 6 1 2 4 5 6 7 1 4 3 5 7 8 4 4 1 4 6 7 2 1...
output:
0 0 0 0 0 0 0 1 0 0 3 0 0 1 1 0 2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 0 3 1 1 0 0 0 1 0 4 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 ...
result:
wrong answer 89th lines differ - expected: '2', found: '0'