QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#485555#4892. 序列zyxawa0 12ms57476kbC++141.7kb2024-07-20 19:55:292024-07-20 19:55:29

Judging History

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

  • [2024-07-20 19:55:29]
  • 评测
  • 测评结果:0
  • 用时:12ms
  • 内存:57476kb
  • [2024-07-20 19:55:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define id(i,j,k) (i+1+sz[j]+k*500000)
int n,m,tot,cnt,top,a[100001][3],b[100001],w[100001],sz[100001],dfn[1000001],low[1000001],ins[1000001],scc[1000001],stk[1000001];
basic_string <int> s[100001],G[1000001];
void tarjan(int u){
	low[u]=dfn[u]=++tot,ins[u]=1,stk[++top]=u;
	for(int v:G[u]){
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(ins[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		while(stk[top]!=u) scc[stk[top]]=cnt,ins[stk[top--]]=0;
		scc[u]=cnt++,ins[u]=0,top--;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) s[i]+=1,s[i]+=1e9;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&a[i][0],&a[i][1],&a[i][2],&w[i]);
		for(int j:{0,1,2}) s[a[i][j]]+=w[i];
	}
	for(int i=1;i<=n;i++){
		sort(begin(s[i]),end(s[i]));
		s[i].erase(unique(begin(s[i]),end(s[i])),end(s[i]));
		sz[i]=sz[i-1]+s[i-1].size();
		for(int j=0;j<s[i].size()-1;j++) G[id(j,i,0)]+=id(j+1,i,0),G[id(j+1,i,1)]+=id(j,i,1);
	}
	for(int i=1;i<=m;i++){
		for(int j:{0,1,2}){
			for(int k:{0,1,2}){
				if(j==k) continue;
				int u=lower_bound(s[a[i][j]].begin(),s[a[i][j]].end(),w[i])-s[a[i][j]].begin(),v=lower_bound(s[a[i][k]].begin(),s[a[i][k]].end(),w[i])-s[a[i][k]].begin();
				G[id(u,a[i][j],0)]+=id(v,a[i][k],1);
				if(u+1<s[a[i][j]].size()&&v+1<s[a[i][k]].size()) G[id(u+1,a[i][j],1)]+=id(v+1,a[i][k],0);
			}
		}
	}
	for(int i=1;i<=1000000;i++) if(!dfn[i]) tarjan(i);
	for(int i=1;i<=n;i++){
		for(int j=0;j<s[i].size();j++) if(scc[id(j,i,0)]==scc[id(j,i,1)]) return printf("NO"),0;
		for(int j=s[i].size()-1;j>=0;j--) if(scc[id(j,i,1)]>scc[id(j,i,0)]) b[i]=s[i][j];
	}
	printf("YES\n");
	for(int i=1;i<=n;i++) printf("%d ",b[i]);
	return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 57000kb

input:

10 10
6 3 10 133562624
8 7 6 685486592
4 2 7 332482851
10 8 9 211550017
2 10 1 165556251
10 8 5 211550017
6 8 2 332482851
4 9 2 332482851
8 1 4 193658790
9 6 10 728674154

output:

YES
193658790 1000000000 1 332482851 1000000000 1000000000 1000000000 332482851 1000000000 165556251 

result:

wrong answer the 1-th condition is not satisfied

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 12ms
memory: 57476kb

input:

40 9880
4 19 31 610502845
10 19 33 190412843
21 24 39 649028784
16 22 40 569593239
5 9 37 550862419
11 23 40 654613112
6 18 23 492267246
22 23 30 538715841
6 16 24 407919735
5 16 18 388907784
2 16 18 388907784
21 24 28 281403057
7 12 27 451830401
3 11 16 508407438
15 33 36 561955959
6 23 29 70605893...

output:

YES
1000000000 209356929 538715841 624132238 222768149 718125822 657895429 645058340 561955959 72694954 655952999 143160363 407919735 399757770 569593239 451830401 812463588 396827347 197498120 660914927 854549869 610502845 508407438 72694954 744594798 832003778 457627673 388907784 1000000000 550862...

result:

wrong answer the 1-th condition is not satisfied

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #2:

0%