QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#821749 | #9875. Don't Detect Cycle | WrongAnswer_90 | RE | 1ms | 3708kb | C++23 | 6.1kb | 2024-12-19 17:49:37 | 2024-12-19 17:49:38 |
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 vt vector<tup>
#define all(x) x.begin(),x.end()
#define mp make_pair
#define FastI
#define FastO
#define int ll
bool ST;
static const ll MOD=1e9+7,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,Inf=4294967296,INF=1e18;
static const ld eps=1e-9,pi=3.1415926535;
char in[1<<20],*p1=in,*p2=in;
char out[1<<20],*p3=out;
using namespace std;
struct tup
{
int x,y,z;
tup(int X=0,int Y=0,int Z=0)
{x=X,y=Y,z=Z;}
bool operator <(const tup nd)const
{return x<nd.x;}
};
#ifdef FastI
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
#ifdef FastO
#define putchar(x) (p3-out==1<<20?fwrite(out,1,1<<20,stdout),p3=out,0:0,*p3++=x)
#define puts(x) write(x,'\n')
#endif
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!=' '&&st!='\r')s[++len]=st,st=getchar();
s[++len]='\0';
}
template<typename T> inline void read(T &s)
{
char ch=getchar();s=0;
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;
}
inline void edl(){putchar('\n');}
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...);}
#ifdef FastO
struct Writer{~Writer(){fwrite(out,1,p3-out,stdout);}}Writ;
#endif
}
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;}
inline int Cmod(int x){return (x%MOD+MOD)%MOD;}
inline void Mmod(int&x){x=(x%MOD+MOD)%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;
int deg[4010];
pii edge[4010];
bool del[4010],vis[4010];
vi L,R;
map<pii,int> hash;
const int N=4000,M=8000;
int cnt=1,num,col,low[N+10],dfn[N+10],head[N+10],to[M+10],nex[M+10],c[N+10];
inline void add(int x,int y){to[++cnt]=y,nex[cnt]=head[x],head[x]=cnt;}
stack<int> st;
void tarjan(int x,int fromi)
{
dfn[x]=low[x]=++num,st.e(x);
for(int i=head[x];i;i=nex[i])
{
if(i==(fromi^1))continue;
if(!dfn[to[i]])
{
tarjan(to[i],i),low[x]=min(low[x],low[to[i]]);
if(low[to[i]]>dfn[x])
{
del[hash[mp(x,to[i])]]=1;
L.eb(hash[mp(x,to[i])]);
}
}
else low[x]=min(low[x],dfn[to[i]]);
}
if(low[x]==dfn[x])
{
int y;++col;
do y=st.top(),c[y]=col,st.pop();while(y!=x);
}
}
void mian()
{
int x,y;
hash.clear();
L.clear(),R.clear();
memset(del,0,sizeof(del));
read(n,m);
for(int i=1;i<=m;++i)
{
read(x,y),edge[i]=mp(x,y);
hash[mp(x,y)]=hash[mp(y,x)]=i;
}
while(L.size()+R.size()<m)
{
int pre=L.size()+R.size();
cnt=1,memset(head,0,sizeof(head)),memset(dfn,0,sizeof(dfn));
for(int i=1;i<=m;++i)if(!del[i])
add(edge[i].fi,edge[i].se),add(edge[i].se,edge[i].fi);
for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i,0);
memset(vis,0,sizeof(vis)),memset(deg,0,sizeof(deg));
for(int i=1;i<=m;++i)if(!del[i])
++deg[edge[i].fi],++deg[edge[i].se];
for(int i=1;i<=m;++i)if(!vis[c[edge[i].fi]])
{
if(deg[edge[i].fi]==2&°[edge[i].se]==2)
del[i]=1,vis[c[edge[i].fi]]=1,R.eb(i);
}
if(L.size()+R.size()==pre)
return puts("-1"),void();
}
reverse(all(R));
for(auto p:L)write(p);
for(auto p:R)write(p);
puts("");
}
inline void Mian()
{
int T=1,C;
read(T);
while(T--)mian();
}
}
bool ED;
signed main()
{
// ios::sync_with_stdio(0);
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
WrongAnswer_90::Mian();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3708kb
input:
1 4 4 1 2 2 3 3 4 4 2
output:
1 3 4 2
result:
ok Correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
4 4 5 1 2 2 3 3 4 3 1 1 4 5 3 1 2 2 3 3 4 9 10 3 5 1 8 5 8 4 9 6 7 7 9 1 2 1 4 2 4 4 6 8 10 1 4 3 8 2 5 3 4 1 5 5 8 2 8 5 7 4 5 3 7
output:
-1 3 2 1 1 3 2 10 6 4 9 8 7 5 -1
result:
ok Correct
Test #3:
score: -100
Runtime Error
input:
50 3214 2907 970 1929 2860 3033 1322 2296 931 1192 861 2505 831 2469 231 2549 1 2306 1765 1842 999 3171 177 2007 1798 1894 827 3180 673 1738 1163 1573 2213 2781 2766 3200 1663 2197 1797 2281 315 2637 442 2689 558 2874 1520 2591 651 1923 1133 2920 1747 2412 1104 1528 313 2487 632 3124 660 2182 1581 2...