QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#143420#6526. CanvasMaxBlazeResFireWA 10ms27384kbC++232.9kb2023-08-21 11:19:432023-08-21 11:19:45

Judging History

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

  • [2023-08-21 11:19:45]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:27384kb
  • [2023-08-21 11:19:43]
  • 提交

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 );
	}
}

int cc[MAXN];
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( pair<int,int> ele : P ){
		int u = ele.first,v = ele.second;
		col[bel[u]] = col[bel[v]] = 1;
		sta[bel[u]] = u,sta[bel[v]] = v;
	}
	int Ansc = 0;
	for( int i = 1 ; i <= Scnt ; i ++ )
		if( !deg[i] && !col[i] ) sta[i] = Scc[i][0];
	for( int i = 1 ; i <= Scnt ; i ++ ) if( !deg[i] ) get_ans( sta[i] );
	for( int i = 1 ; i <= m ; i ++ )
		if( N[i].x == 1 && N[i].y == 1 ) Ans.emplace_back( i );
	reverse( Ans.begin() , Ans.end() );
	for( int r : Ans ){
		int u = N[r].u,v = N[r].v;
		Ansc -= cc[u],Ansc -= cc[v];
		cc[u] = N[r].x,cc[v] = N[r].y;
		Ansc += cc[u],Ansc += cc[v];
	}
	printf("%lld\n",Ansc);
	for( int ele : Ans ) printf("%lld ",ele); puts("");
	for( int i = 1 ; i <= n ; i ++ ) dfn[i] = low[i] = st[i] = inst[i] = cc[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: 0ms
memory: 27376kb

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: 1ms
memory: 27156kb

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 11 8 10 9 7 6 5 4 2 1 3 12 

result:

ok Correct. (1 test case)

Test #3:

score: 0
Accepted
time: 5ms
memory: 27144kb

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 1 4 5 2 

result:

ok Correct. (1 test case)

Test #4:

score: 0
Accepted
time: 5ms
memory: 27168kb

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 2 1 6 5 3 

result:

ok Correct. (1 test case)

Test #5:

score: 0
Accepted
time: 5ms
memory: 27120kb

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
3 5 4 2 1 

result:

ok Correct. (1 test case)

Test #6:

score: 0
Accepted
time: 0ms
memory: 27344kb

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:

8
6 2 4 1 5 3 

result:

ok Correct. (1 test case)

Test #7:

score: -100
Wrong Answer
time: 10ms
memory: 27384kb

input:

2000
15 16
2 2 3 1
12 2 15 1
3 2 9 1
6 2 14 1
2 1 15 2
5 2 6 1
7 1 10 1
9 2 15 1
2 2 3 1
4 2 12 1
2 2 9 1
5 2 8 2
3 2 13 1
12 1 13 2
9 2 13 1
5 1 14 2
15 15
5 2 11 1
1 2 8 1
8 1 15 2
6 2 8 2
8 2 9 1
1 1 6 2
6 1 9 2
2 2 5 1
2 1 10 2
7 2 10 1
1 1 15 2
5 2 15 1
7 1 11 2
1 1 2 1
5 2 9 1
15 14
3 1 5 2
1 ...

output:

23
7 6 4 16 8 11 15 9 13 14 10 2 5 1 3 12 
20
14 11 15 1 13 10 9 8 12 3 5 7 6 2 4 
21
2 11 13 6 10 3 9 12 7 8 4 1 14 5 
18
7 9 10 14 13 12 6 4 8 3 1 5 11 2 
21
6 11 14 10 7 2 13 3 19 18 9 12 17 8 4 5 1 15 
21
3 6 2 11 7 12 13 8 9 14 5 4 10 1 
21
3 14 8 1 5 2 11 9 7 15 6 13 4 12 10 
19
11 7 10 9 14 6...

result:

wrong answer Integer parameter [name=p_i] equals to 21, violates the range [1, 19] (test case 5)