QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#202151 | #6526. Canvas | OccDreamer | WA | 7ms | 50424kb | C++14 | 3.4kb | 2023-10-05 20:19:00 | 2023-10-05 20:19:01 |
Judging History
answer
//code by Emissary
#include<bits/stdc++.h>
#define fi first
#define se second
#define vc vector
#define db double
#define ll long long
#define mk make_pair
#define pb push_back
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << " -_- " << endl
#define debug cerr << " ------------------- " << endl
#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)
#define NO puts("No")
#define YES puts("Yes")
//#define int long long
using namespace std;
namespace IO{
inline int read(){
int X=0, W=0; char ch=getchar();
while(!isdigit(ch)) W|=ch=='-', ch=getchar();
while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
return W?-X:X;
}
inline void write(int x){
if(x<0) x=-x, putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void sprint(int x){write(x), putchar(32);}
inline void eprint(int x){write(x), putchar(10);}
}using namespace IO;
const int MAXN = 5e5+5;
vc<PI> G[MAXN];
vc<int> P[MAXN];
int hd, tl, Q[MAXN];
int bel[MAXN], du[MAXN], node[MAXN], colcnt;
int n, m, topf, stk[MAXN], dfn[MAXN], low[MAXN], tot;
int head[MAXN], ne[MAXN<<1], to[MAXN<<1], weight[MAXN<<1], cnt;
bool mark[MAXN], ins[MAXN], vis[MAXN], ind[MAXN];
inline void add(int x, int y, int w){++cnt;to[cnt]=y;ne[cnt]=head[x];head[x]=cnt;weight[cnt]=w;}
inline void tarjan(int x){
stk[++topf]=x; dfn[x]=low[x]=++tot; ins[x]=1;
for(int i=head[x];i;i=ne[i]){
if(dfn[to[i]]){
if(ins[to[i]]) low[x]=min(low[x],dfn[to[i]]);
}
else tarjan(to[i]), low[x]=min(low[x],low[to[i]]);
}
if(low[x]==dfn[x]){
int t; stk[topf+1]=-1; ++colcnt;
while(stk[topf+1]!=x){
t=stk[topf];
ins[t]=0; bel[t]=colcnt; node[colcnt]=t;
--topf;
}
}
return ;
}
inline void DFS(int x){
vis[x]=1;
for(int i=head[x];i;i=ne[i]){
if(vis[to[i]] || bel[to[i]]!=bel[x]) continue;
DFS(to[i]); P[bel[x]].pb(weight[i]); ind[weight[i]]=1;
}
return ;
}
inline void solve(){
int a, b, c, d; vc<int> A, B;
n=read(), m=read(); cnt=0; tot=0; colcnt=0;
for(int i=0;i<=n;++i) vis[i]=0, dfn[i]=0, du[i]=0;
for(int i=0;i<=n;++i) mark[i]=0, head[i]=0, ind[i]=0, G[i].clear();
for(int i=1;i<=m;++i){
a=read(), b=read();
c=read(), d=read();
mark[a]=mark[c]=1;
if(b+d==2) A.pb(i), ind[i]=1;
if(b+d==3){
if(d==1) swap(a,c);
add(a,c,i);
}
if(b+d==4) add(0,a,0), add(0,c,0), B.pb(i), ind[i]=1;
}
int ans=0; mark[0]=1;
for(int i=1;i<=n;++i) ans+=mark[i];
for(int i=0;i<=n;++i){
if(dfn[i] || !mark[i]) continue;
tarjan(i);
}
for(int i=0;i<=n;++i)
for(int j=head[i];j;j=ne[j]){
if(bel[i]!=bel[to[j]]){
node[bel[to[j]]]=to[j];
G[bel[to[j]]].pb(mk(bel[i],weight[j])); du[bel[i]]++; ind[weight[j]]=1;
}
}
hd=1, tl=0;
for(int i=1;i<=colcnt;++i) if(du[i]==0) Q[++tl]=i;
(ans<<=1); ans-=tl-1; eprint(ans); for(auto i:A) sprint(i);
for(int i=1;i<=colcnt;++i) P[i].clear(), DFS(node[i]);
for(int i=1;i<=m;++i) if(ind[i]==0) sprint(i);
while(hd<=tl){
int t=Q[hd++];
for(auto i:P[t]) if(i) sprint(i);
for(auto ver:G[t]){
if(ver.se) sprint(ver.se);
if((--du[ver.fi])==0) Q[++tl]=ver.fi;
}
}
for(auto i:B) sprint(i); putchar(10);
}
signed main(){
int t=read();
while(t--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 49076kb
input:
2 4 4 1 1 2 2 3 2 4 1 1 2 3 2 2 1 4 1 4 2 3 2 4 1 1 2 3 1
output:
7 4 2 1 3 5 2 1
result:
ok Correct. (2 test cases)
Test #2:
score: 0
Accepted
time: 7ms
memory: 49220kb
input:
1 10 13 1 1 2 2 2 1 3 2 1 2 3 1 3 1 4 2 4 1 5 2 5 1 6 2 4 2 6 1 7 1 8 2 8 1 9 2 7 2 9 1 5 2 9 1 8 2 10 2 1 1 10 1
output:
19 13 3 5 8 7 6 4 11 2 1 10 9 12
result:
ok Correct. (1 test case)
Test #3:
score: 0
Accepted
time: 0ms
memory: 50424kb
input:
1 7 5 2 1 6 2 1 2 6 1 1 1 5 1 2 2 7 1 1 1 7 2
output:
8 3 2 1 4 5
result:
ok Correct. (1 test case)
Test #4:
score: 0
Accepted
time: 3ms
memory: 50360kb
input:
1 7 6 2 1 7 2 2 1 4 2 1 2 4 1 2 1 6 1 1 1 6 2 2 2 6 1
output:
9 4 3 1 2 6 5
result:
ok Correct. (1 test case)
Test #5:
score: 0
Accepted
time: 3ms
memory: 49208kb
input:
1 7 5 5 2 7 1 5 1 6 2 3 2 7 1 3 2 6 1 6 1 7 2
output:
7 1 4 3 5 2
result:
ok Correct. (1 test case)
Test #6:
score: -100
Wrong Answer
time: 3ms
memory: 50280kb
input:
1 7 6 1 2 5 1 2 1 7 2 1 2 7 1 2 2 7 1 1 1 5 2 1 2 3 1
output:
9 1 4 5 6 3 2
result:
wrong answer Participant's solution is incorrect. (test case 1)