QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#216957 | #7177. Many Many Cycles | ExplodingKonjac | WA | 1ms | 3648kb | C++20 | 6.0kb | 2023-10-16 09:57:24 | 2023-10-16 09:57:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define OPENIOBUF
namespace FastIO
{
class FastIOBase
{
protected:
#ifdef OPENIOBUF
static const int BUFSIZE=1<<16;
char buf[BUFSIZE+1];
int buf_p=0;
#endif
FILE *target;
FastIOBase(FILE *f): target(f){}
~FastIOBase()=default;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
};
class FastOutput final: public FastIOBase
{
private:
void __putc(char x)
{
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE) flush();
#else
putc(x,target);
#endif
}
template<typename T>
void __write(T x)
{
char stk[numeric_limits<T>::digits10+1],*top=stk;
if(x<0) return __putc('-'),__write(-x);
do *(top++)=x%10,x/=10; while(x);
for(;top!=stk;__putc(*(--top)+'0'));
}
public:
FastOutput(FILE *f=stdout): FastIOBase(f) {}
#ifdef OPENIOBUF
~FastOutput() { flush(); }
void flush() { fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
FastOutput &operator <<(char x)
{ return __putc(x),*this; }
FastOutput &operator <<(const char *s)
{ for(;*s;__putc(*(s++)));return *this; }
FastOutput &operator <<(const std::string &s)
{ return (*this)<<s.c_str(); }
template<typename T>
std::enable_if_t<std::is_integral<T>::value,FastOutput&> operator <<(const T &x)
{ return __write(x),*this; }
template<typename ...T>
void writesp(const T &...x)
{ std::initializer_list<int>{(this->operator<<(x),__putc(' '),0)...}; }
template<typename ...T>
void writeln(const T &...x)
{ std::initializer_list<int>{(this->operator<<(x),__putc('\n'),0)...}; }
template<typename Iter>
void writesp(Iter begin,Iter end)
{ while(begin!=end) (*this)<<*(begin++)<<' '; }
template<typename Iter>
void writeln(Iter begin,Iter end)
{ while(begin!=end) (*this)<<*(begin++)<<'\n'; }
}qout;
class FastInput final: public FastIOBase
{
private:
bool __eof;
public:
FastInput(FILE *f=stdin): FastIOBase(f),__eof(false)
#ifdef OPENIOBUF
{ buf_p=BUFSIZE; }
void flush() { buf[fread(buf,1,BUFSIZE,target)]=EOF,buf_p=0; }
bool eof()const { return buf[buf_p]==EOF; }
#else
{}
bool eof()const { return feof(target); }
#endif
char get()
{
if(__eof) return EOF;
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
char ch=buf[buf_p++];
#else
char ch=getc(target);
#endif
return ~ch?ch:(__eof=true,EOF);
}
void unget(char c)
{
__eof=false;
#ifdef OPENIOBUF
buf[--buf_p]=c;
#else
ungetc(c,target);
#endif
}
explicit operator bool()const { return !__eof; }
FastInput &operator >>(char &x)
{ while(isspace(x=get()));return *this; }
template<typename T>
std::enable_if_t<std::is_integral<T>::value,FastInput&> operator >>(T &x)
{
char ch,sym=0;x=0;
while(isspace(ch=get()));
if(__eof) return *this;
if(ch=='-') sym=1,ch=get();
for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=get());
return unget(ch),sym?x=-x:x,*this;
}
FastInput &operator >>(char *s)
{
while(isspace(*s=get()));
if(__eof) return *this;
for(;!isspace(*s) && !__eof;*(++s)=get());
return unget(*s),*s='\0',*this;
}
FastInput &operator >>(std::string &s)
{
char str_buf[(1<<8)+1]={0},*p=str_buf;
char *const buf_end=str_buf+(1<<8);
while(isspace(*p=get()));
if(__eof) return *this;
for(s.clear(),p++;;p=str_buf)
{
for(;p!=buf_end && !isspace(*p=get()) && !__eof;p++);
if(p!=buf_end) break;
s.append(str_buf);
}
unget(*p),*p='\0',s.append(str_buf);
return *this;
}
template<typename ...T>
void read(T &...x)
{ std::initializer_list<int>{(this->operator>>(x),0)...}; }
template<typename Iter>
void read(Iter begin,Iter end)
{ while(begin!=end) (*this)>>*(begin++); }
}qin;
} // namespace FastIO
using FastIO::qin,FastIO::qout;
using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;
#ifndef DADALZY
#define FILEIO(file) freopen(file".in","r",stdin),freopen(file".out","w",stdout)
#define LOG(...) void()
#else
#define FILEIO(file)
#define LOG(...) fprintf(stderr,__VA_ARGS__)
#endif
int n,m;
vector<pair<int,int>> G[5005];
#define ctz(x) __builtin_ctzll(x)
inline ULL fastgcd(ULL a,ULL b)
{
int az=ctz(a),bz=ctz(b),z=min(az,bz);
b>>=bz;
while(a)
{
a>>=az;
if(a<b) swap(a,b);
az=ctz(a-=b);
}
return b<<z;
}
vector<tuple<int,int,int>> E;
int fa[5005];
inline int findFa(int x)
{ return fa[x]!=x?fa[x]=findFa(fa[x]):x; }
inline void merge(int x,int y)
{ fa[findFa(y)]=findFa(x); }
int tot,eul[10005],pos[5005],f[20][10005];
LL dep[5005];
void dfs(int u,int fa=0)
{
eul[pos[u]=++tot]=u;
for(auto &[v,w]: G[u])
{
if(v==fa) continue;
dep[v]=dep[u]+w;
dfs(v,u),eul[++tot]=u;
}
}
inline bool cmpdep(int x,int y) { return dep[x]<dep[y]; }
void buildST()
{
for(int i=1;i<=tot;i++) f[0][i]=eul[i];
for(int i=1;(1<<i)<=tot;i++)
for(int j=1;j+(1<<i)-1<=tot;j++)
f[i][j]=min(f[i-1][j],f[i-1][j+(1<<(i-1))],cmpdep);
}
inline int lca(int u,int v)
{
tie(u,v)=minmax(pos[u],pos[v]);
int s=__lg(v-u+1);
return min(f[s][u],f[s][v-(1<<s)+1],cmpdep);
}
inline LL dist(int u,int v)
{
int w=lca(u,v);
return dep[u]+dep[v]-2*dep[w];
}
int main()
{
freopen("../input.in","r",stdin);
qin>>n>>m;
iota(fa+1,fa+n+1,1);
for(int i=1,u,v,w;i<=m;i++)
{
qin>>u>>v>>w;
if(findFa(u)==findFa(v))
E.emplace_back(u,v,w);
else
{
merge(u,v);
G[u].emplace_back(v,w);
G[v].emplace_back(u,w);
}
}
for(int i=1;i<=n;i++)
{
if(findFa(i)!=i) continue;
G[0].emplace_back(i,0);
}
dfs(0),buildST();
LL ans=0;
for(auto &[u,v,w]: E)
{
if(pos[u]>pos[v]) swap(u,v);
LL len=dist(u,v)+w;
ans=fastgcd(ans,len);
}
for(auto &[u1,v1,w1]: E)
{
int z1=lca(u1,v1);
LL len1=dist(u1,v1);
for(auto &[u2,v2,w2]: E)
{
if(u1==u2 && v1==v2) continue;
int z2=lca(u2,v2);
if(dep[z1]>dep[z2] || dist(u1,z2)+dist(z2,v1)!=len1) continue;
LL len2=dist(u2,v2);
int k1=max(lca(u2,u1),lca(u2,v1),cmpdep),
k2=max(lca(v2,u1),lca(v2,v1),cmpdep);
LL len=len1+len2-2*dist(k1,k2)+w1+w2;
ans=fastgcd(ans,len);
}
}
qout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3648kb
input:
4 4 1 2 1 2 3 1 3 4 1 4 1 1
output:
0
result:
wrong answer expected '4', found '0'