QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#143411#6526. CanvasMaxBlazeResFireWA 3ms27168kbC++233.0kb2023-08-21 11:10:122023-08-21 11:10:13

Judging History

你现在查看的是最新测评结果

  • [2023-08-21 11:10:13]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:27168kb
  • [2023-08-21 11:10:12]
  • 提交

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)