QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#153513#6526. CanvasqzezWA 10ms30344kbC++142.3kb2023-08-30 09:26:482023-08-30 09:26:49

Judging History

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

  • [2023-08-30 09:26:49]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:30344kb
  • [2023-08-30 09:26:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=5e5+10;
int T,n,m,use[N],col[N];
struct opts{
	int l,x,r,y;
}a[N];
vector<pair<int,int> >to[N];
#define v e.first
#define w e.second
int k,ans[N],vis[N];
void dfs(int u){
	if(vis[u])return;
	vis[u]=1;
	for(auto e:to[u]){
		ans[++k]=w;
		dfs(v);
	}
}
int sct,dft,top,scc[N],dfn[N],low[N],stk[N],in[N];
void tarjan(int u){
	low[u]=dfn[u]=++dft,stk[++top]=u;
	for(auto e:to[u])if(!vis[v]){
		if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
		else if(!scc[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		sct++;
		do scc[stk[top]]=sct;while(stk[top--]^u);
	}
}
void build(){
	for(int u=1;u<=n;u++)if(!vis[u]){
		for(auto e:to[u])if(!vis[v]){
			if(scc[u]^scc[v])in[scc[v]]++;
		}
	}
}
#undef v
#undef w
void get(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&a[i].l,&a[i].x,&a[i].r,&a[i].y);
		if(a[i].x+a[i].y==3){
			if(a[i].x==1)to[a[i].l].push_back({a[i].r,i});
			else to[a[i].r].push_back({a[i].l,i});
		}
	}
	for(int i=1;i<=m;i++){
		if(a[i].x+a[i].y==4){
			ans[++k]=i;
			dfs(a[i].l),dfs(a[i].r);
		}
	}
	for(int i=1;i<=n;i++)if(!dfn[i]&&!vis[i])tarjan(i);
	build();
	for(int i=1;i<=n;i++)if(!vis[i]&&!in[scc[i]])dfs(i);
	for(int i=1;i<=k;i++)use[ans[i]]=1;
	for(int i=1;i<=m;i++){
		if(!use[i])ans[++k]=i;
	}
	reverse(ans+1,ans+1+k);
	int res=0;
	// debug("ans",ary(ans,1,k));
	for(int i=1;i<=k;i++){
		col[a[ans[i]].l]=a[ans[i]].x;
		col[a[ans[i]].r]=a[ans[i]].y;
	}
	// debug("col",ary(col,1,n));
	printf("%d\n",accumulate(col+1,col+1+n,0));
	for(int i=1;i<=k;i++)printf("%d%c",ans[i],"\n "[i<k]);
}
void clr(){
	dft=sct=k=top=0;
	for(int i=1;i<=n;i++){
		to[i].clear();
		dfn[i]=col[i]=low[i]=vis[i]=in[i]=0;
	}
	for(int i=1;i<=m;i++){
		use[i]=0;
	}
}
int main(){
	for(scanf("%d",&T);T--;clr())get();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 30256kb

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: 28240kb

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

result:

ok Correct. (1 test case)

Test #3:

score: 0
Accepted
time: 8ms
memory: 28296kb

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: 2ms
memory: 30344kb

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

result:

ok Correct. (1 test case)

Test #5:

score: 0
Accepted
time: 3ms
memory: 28144kb

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

result:

ok Correct. (1 test case)

Test #6:

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

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

result:

ok Correct. (1 test case)

Test #7:

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

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 8 11 3 15 9 1 13 14 10 2 5 6 4 16 12
20
14 15 3 1 13 10 9 8 12 11 6 2 5 7 4
21
2 11 13 6 10 3 9 12 7 14 8 4 1 5
17
11 7 5 1 9 3 13 4 8 12 6 10 14 2
17
19 18 16 14 13 12 11 10 9 7 6 3 2 1 5 17 8 4 15
21
6 3 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
14 11 9 5 3 2 16 1...

result:

wrong answer Jury has better answer. Participant 17, jury 18 (test case 4)