QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#485555 | #4892. 序列 | zyxawa | 0 | 12ms | 57476kb | C++14 | 1.7kb | 2024-07-20 19:55:29 | 2024-07-20 19:55:29 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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%