QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#478722 | #21608. 行列式 | WrongAnswer_90# | RE | 0ms | 0kb | C++20 | 5.4kb | 2024-07-15 10:34:50 | 2024-07-15 10:34:50 |
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 n,m,cnt,root,minn,all,head[100010],to[200010],nex[200010],v[200010],ans[110],siz[100010],a[110];
inline void add(int x,int y,int z){to[++cnt]=y,v[cnt]=z,nex[cnt]=head[x],head[x]=cnt;}
bool vis[100010];
void findrt(int x,int fa)
{
int maxn=0;siz[x]=1;
for(int i=head[x];i;i=nex[i])
{
if(to[i]==fa||vis[to[i]])continue;
findrt(to[i],x),siz[x]+=siz[to[i]],Mmax(maxn,siz[to[i]]);
}
if(Mmin(minn,max(maxn,all-siz[x])))root=x;
}
vector<pii> ve;
void dfs(int x,int fa,int dep,int col)
{
ve.eb(mp(col,dep));
for(int i=head[x];i;i=nex[i])if(to[i]!=fa&&!vis[to[i]])
dfs(to[i],x,dep+v[i],col);
}
inline bool cmp(pii x,pii y){return x.se<y.se;}
void starch(int x)
{
minn=inf,findrt(x,0),minn=inf,findrt(x=root,0);
assert(minn<=all/2);
ve.clear(),ve.eb(mp(x,0)),vis[x]=1;
for(int i=head[x];i;i=nex[i])if(!vis[to[i]])dfs(to[i],x,v[i],to[i]);
sort(ve.begin(),ve.end(),cmp);
for(int i=1;i<=m;++i)
{
for(int j=0,k=ve.size()-1;j<(int)ve.size();++j)
{
while(k>=0&&(ve[j].se+ve[k].se>a[i]||ve[j].fi==ve[k].fi))--k;
if(k>=0&&ve[j].se+ve[k].se==a[i])
assert(ve[j].fi!=ve[k].fi),ans[i]=1;
}
}
for(int i=head[x];i;i=nex[i])if(!vis[to[i]])all=siz[to[i]],starch(to[i]);
}
inline void mian()
{
all=n,read(n,m);int x,y,z;
for(int i=1;i<n;++i)read(x,y,z),add(x,y,z),add(y,x,z);
for(int i=1;i<=m;++i)read(a[i]);
// exit(0);
starch(1);
for(int i=1;i<=m;++i)
if(ans[i])puts("Yes");else puts("No");
}
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
494 507979999 844753235 308697058 577366689 725069158 935333779 504374900 25818576 590205152 640101368 622693010 938297920 872742027 301114974 734834637 556531110 842083217 975440662 921805913 100862321 393656903 213191224 795146059 30475198 812681603 711143306 28681751 642978178 605226383 94538558 ...