QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #416153 | #8547. Whose Land? | WrongAnswer_90 | RE | 0ms | 47792kb | C++20 | 6.6kb | 2024-05-21 16:30:50 | 2024-05-21 16:30:50 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vp vector<pii>
#define mp make_pair
//#define LOCALJUDGE
//#define int ll
bool ST;
static const ll MOD=998244353,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,INF=4557430888798830399;
static const double eps=1e-8,pi=3.1415926535;
char in[1<<20],*p1=in,*p2=in;
using namespace std;
//#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
struct tup{int x,y,z;tup(int X=0,int Y=0,int Z=0){x=X,y=Y,z=Z;}};
namespace FastIO
{
template<typename T> inline void write(T x,char ch=' ')
{
if(is_same<char,T>::value)putchar(x);
else
{
if(x<0)x=-x,putchar('-');
static char st[25];int top=0;
do{st[top++]=x%10+'0',x/=10;}while(x);
while(top)putchar(st[--top]);
}
ch!='~'?putchar(ch):0;
}
inline void write(const char*x,char ch=' ')
{
for(int i=0;x[i]!='\0';++i)putchar(x[i]);
ch!='~'?putchar(ch):0;
}
inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
inline void read(char s[])
{
int len=0;char st;
do st=getchar();while(st=='\n'||st==' ');
s[++len]=st,st=getchar();
while(st!='\n'&&st!=' ')s[++len]=st,st=getchar();
s[++len]='\0';
}
template<typename T> inline void read(T &s)
{
s=0;char ch=getchar();
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
bool tf=(ch=='-')&&(ch=getchar());
while((ch>='0')&&(ch<='9'))s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
s=(tf?-s:s);
}
template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
}
using namespace FastIO;
namespace MTool
{
inline int Cadd(int a,int b){return (ll)a+b>=MOD?(ll)a+b-MOD:a+b;}
inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
inline int sqr(int a){return 1ll*a*a%MOD;}
inline void Madd(int&a,int b){a=((ll)a+b>=MOD?(ll)a+b-MOD:a+b);}
inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
int cnt,T,n,m,q,N,dep[500010],head[500010],to[1000010],nex[1000010];
int tot,L,R,mid,ans[500010],pos[500010],F[20][500010],dfn[500010];
vector<int> ve[500010];
vector<pii> qu[500010];
inline void add(int x,int y){to[++cnt]=y,nex[cnt]=head[x],head[x]=cnt;}
inline int get(int x,int y){return dfn[x]<dfn[y]?x:y;}
struct Node{
int l,r,v;
Node(int L,int R=0,int V=0){l=L,r=R,v=V;}
bool operator <(const Node nd1)const{return l<nd1.l;}
};
namespace BIT{
int t[500010];
inline void tadd(int x,int y){for(;x;x-=x&-x)t[x]+=y;}
inline int ask(int x){int s=0;for(;x<=n;x+=x&-x)s+=t[x];return s;}
}
using namespace BIT;
struct ODT
{
set<Node> st;
#define ni set<Node>::iterator
inline ni split(int x)
{
ni it=st.upper_bound(Node(x));
if((--it)->r<x)return st.end();
if(it->l==x)return it;
int l=it->l,r=it->r,v=it->v;
st.erase(it),st.insert(Node(l,x-1,v));
return st.insert(Node(x,r,v)).fi;
}
inline void assign(int l,int r,int x)
{
ni itr=split(r+1),itl=split(l);
for(auto p=itl;p!=itr;++p)
tadd(p->v,-((p->r)-(p->l)+1));
tadd(x,r-l+1),st.erase(itl,itr),st.insert(Node(l,r,x));
}
}st[500010];
void dfs(int x,int fa)
{
ve[dep[x]=dep[fa]+1].eb(x),Mmax(N,dep[x]);
F[0][dfn[x]=++tot]=fa,pos[x]=ve[dep[x]].size()-1;
for(int i=head[x];i;i=nex[i])if(to[i]!=fa)dfs(to[i],x);
}
inline int LCA(int x,int y)
{
if(x==y)return x;
if((x=dfn[x])>(y=dfn[y]))swap(x,y);
int k=__lg(y-x++);
return get(F[k][x],F[k][y-(1<<k)+1]);
}
inline int DIS(int x,int y){return dep[x]+dep[y]-2*dep[LCA(x,y)];}
inline void mian()
{
read(T);int x,y;
while(T--)
{
read(n,m,q),cnt=N=tot=0;
for(int i=1;i<=n;++i)head[i]=t[i]=0,qu[i].clear(),ve[i].clear();
for(int i=1;i<n;++i)read(x,y),add(x,y);
dfs(1,0);
for(int i=1;i<20;++i)
{
for(int j=1;j+(1<<i)-1<=n;++j)
F[i][j]=get(F[i-1][j],F[i-1][j+(1<<(i-1))]);
}
for(int i=1;i<=N;++i)
{
st[i].st.clear();
st[i].st.e(Node(1,ve[i].size(),0));
}
for(int i=1;i<=q;++i)read(x,y),qu[y].eb(mp(x,i));
for(int i=1;i<=n;++i)
{
int nw=i,d=dep[i];
for(int j=1;j<=m&&head[nw];++j)++d,nw=to[head[nw]];
for(;d>=max(1,dep[i]-m);--d,nw=F[0][dfn[nw]])
{
L=0,R=pos[d];
while(L<R)
{
mid=L+((R-L)>>1);
if(DIS(i,ve[d][mid])<=m)R=mid;
else L=mid+1;
}
int x=L;L=pos[d],R=ve[d].size()-1;
while(L<R)
{
mid=L+((R-L+1)>>1);
if(DIS(i,ve[d][mid])<=m)L=mid;
else R=mid-1;
}
if(x>L)return write("!!!!!!");
st[d].assign(x,L,i);
}
for(auto p:qu[i])ans[p.se]=ask(p.fi);
}
for(int i=1;i<=q;++i)write(ans[i],'\n');
}
}
}
bool ED;
signed main()
{
#ifdef LOCALJUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
double st=clock();
WrongAnswer_90::mian();
double ed=clock();
#ifndef LOCALJUDGE
cerr<<endl;
#endif
cerr<<"Time: "<<ed-st<<" ms\n";
#ifdef LOCALJUDGE
cerr<<" ";
#endif
cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 47792kb
input:
2 5 1 2 1 2 1 3 2 4 2 5 2 2 2 3 8 2 3 1 2 1 3 2 4 2 5 4 6 5 7 7 8 2 2 2 5 3 4
output:
4 5 7 8 6
result:
ok 5 number(s): "4 5 7 8 6"
Test #2:
score: -100
Runtime Error
input:
1000 500 1 500 291 2 406 9 207 13 71 15 351 17 442 18 496 19 104 20 208 23 448 34 80 42 187 44 352 45 290 46 116 47 318 50 226 52 129 55 83 59 100 60 54 61 73 65 63 66 454 67 43 71 26 74 68 26 320 75 388 76 425 79 170 81 350 83 48 85 153 86 221 90 290 95 130 96 82 98 124 82 36 99 213 100 121 101 132...
output:
6 5 6 3 6 6 6 1 6 6 7 6 1 5 6 7 4 3 6 5 1 7 1 7 6 4 1 6 6 1 5 6 3 4 6 7 7 7 1 5 1 7 5 5 6 3 5 1 1 1 1 7 7 6 3 7 4 1 3 6 6 6 6 1 7 1 7 3 6 3 5 6 1 6 7 6 1 1 4 6 4 6 5 5 6 6 3 1 7 6 6 6 1 7 6 5 4 1 6 1 6 7 7 7 6 1 5 6 7 7 7 1 5 3 1 6 1 6 5 1 6 7 7 6 3 1 7 6 7 1 3 6 6 3 3 3 1 6 6 7 3 3 7 3 6 7 7 6 7 4 ...