QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#143411 | #6526. Canvas | MaxBlazeResFire | WA | 3ms | 27168kb | C++23 | 3.0kb | 2023-08-21 11:10:12 | 2023-08-21 11:10:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 500005
int n,m,Vis[MAXN];
struct node{
int u,x,v,y;
node(){}
node( int a , int b , int c , int d ): u(a),x(b),v(c),y(d){}
}N[MAXN];
vector< pair<int,int> > E[MAXN],P;
vector<int> Ans,Scc[MAXN];
int dfn[MAXN],low[MAXN],idx,st[MAXN],top,inst[MAXN];
int Scnt,bel[MAXN],deg[MAXN],vis[MAXN],col[MAXN];
int sta[MAXN];
void tarjan( int x ){
dfn[x] = low[x] = ++idx,inst[x] = 1,st[++top] = x;
for( pair<int,int> p : E[x] ){
int v = p.first;
if( !dfn[v] ) tarjan( v ),low[x] = min( low[x] , low[v] );
else if( inst[v] ) low[x] = min( low[x] , dfn[v] );
}
if( dfn[x] == low[x] ){
Scnt ++;
while( st[top] != x ){
int v = st[top];
bel[v] = Scnt,inst[v] = 0,Scc[Scnt].emplace_back( v );
top --;
}
bel[x] = Scnt,inst[x] = 0,Scc[Scnt].emplace_back( x );
top --;
}
}
int Ansvis[MAXN];
void get_ans( int x ){
for( pair<int,int> p : E[x] ){
int v = p.first,w = p.second;
if( !Ansvis[w] ) Ansvis[w] = 1,Ans.emplace_back( w ),get_ans( v );
}
}
inline void solve(){
scanf("%lld%lld",&n,&m);
for( int i = 1 ; i <= m ; i ++ ){
int u,x,v,y; scanf("%lld%lld%lld%lld",&u,&x,&v,&y);
N[i] = node( u , x , v , y );
if( x == 2 && y == 2 ) P.emplace_back( make_pair( u , v ) ),Ans.emplace_back( i );
if( x == 1 && y == 2 ) E[u].emplace_back( make_pair( v , i ) ),Vis[u] = Vis[v] = 1;
if( y == 1 && x == 2 ) E[v].emplace_back( make_pair( u , i ) ),Vis[v] = Vis[u] = 1;
}
for( int i = 1 ; i <= n ; i ++ ) if( !dfn[i] && Vis[i] ) tarjan( i );
for( int u = 1 ; u <= n ; u ++ ){
for( pair<int,int> p : E[u] ){
int v = p.first;
if( bel[u] != bel[v] ) if( !vis[bel[v]] ) deg[bel[v]] ++,vis[bel[v]] = 1;
}
for( pair<int,int> p : E[u] ){
int v = p.first;
vis[bel[v]] = 0;
}
}
// for( int i = 1 ; i <= Scnt ; i ++ ){
// for( int ele : Scc[i] ) cerr << ele << " ";
// cerr << "\n";
// }
for( pair<int,int> ele : P ){
int u = ele.first,v = ele.second;
col[bel[u]] = col[bel[v]] = 1;
//cerr << bel[u] << " " << bel[v] << "\n";
sta[bel[u]] = u,sta[bel[v]] = v;
}
int Ansc = 0;
for( int i = 1 ; i <= n ; i ++ )
if( Vis[i] ) Ansc += 2;
for( int i = 1 ; i <= Scnt ; i ++ )
if( !deg[i] && !col[i] ){
Ansc --;
sta[i] = Scc[i][0];
}
for( int i = 1 ; i <= Scnt ; i ++ ) get_ans( sta[i] );
for( int i = 1 ; i <= m ; i ++ )
if( N[i].x == 1 && N[i].y == 1 )
Ansc += !Vis[N[i].u] + !Vis[N[i].v],Ans.emplace_back( i );
printf("%lld\n",Ansc);
reverse( Ans.begin() , Ans.end() );
for( int ele : Ans ) printf("%lld ",ele); puts("");
for( int i = 1 ; i <= n ; i ++ ) dfn[i] = low[i] = st[i] = inst[i] = bel[i] = vis[i] = Vis[i] = col[i] = deg[i] = sta[i] = Ansvis[i] = 0;
for( int i = 1 ; i <= n ; i ++ ) E[i].clear(); P.clear(); Ans.clear();
for( int i = 1 ; i <= Scnt ; i ++ ) Scc[i].clear();
idx = top = Scnt = 0;
}
signed main(){
int testcase; scanf("%lld",&testcase);
while( testcase -- ) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 27152kb
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: -100
Wrong Answer
time: 3ms
memory: 27168kb
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:
18 13 11 8 10 9 7 6 5 4 2 1 3 12
result:
wrong answer Participant's solution is incorrect. (test case 1)