QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#853617 | #905. 三元环枚举 | white_tiger | WA | 0ms | 52696kb | C++14 | 1.7kb | 2025-01-11 17:51:37 | 2025-01-11 17:51:39 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,p=1e9+7,M=N*2;
int n,m,u[N],v[N],w[N],ans;
namespace hand_bitset{
struct list{
int nxt,lst,id;
bitset<700>val;
}ls[M];int idx;
struct hbt{int fs;}ed[N];
int insert(int l,int r,int id){
int cc=++idx;
ls[cc].lst=l,ls[cc].nxt=r;
ls[l].nxt=cc,ls[r].lst=cc;
return ls[cc].id=id,cc;
}void ad(hbt &nw,int ps){
int l=0,r=nw.fs,id=ps/700;
if(ls[r].id>id||!r){
int cc=insert(l,r,id);
ls[cc].val[ps-id*700]=1;
nw.fs=cc;return;
}while(r){
if(ls[r].id>id) break;
if(ls[r].id==id){
ls[r].val[ps-id*700]=1;
return;
}l=r,r=ls[r].nxt;
}int cc=insert(l,r,id);
ls[cc].val[ps-id*700]=1;
}int count(bitset<700>x,int y){
int sum=0;
for(int i=0;i<700;i++)
if(x[i]) sum+=w[y*700+i];
return sum;
}int add(hbt x,hbt y){
int sum=0;
for(int i=x.fs,j=y.fs;i&&j;){
if(ls[i].id==ls[j].id){
sum+=count(ls[i].val&ls[j].val,ls[i].id);
i=ls[i].nxt,j=ls[j].nxt;
}else if(ls[j].id<ls[i].id)
j=ls[j].nxt;else i=ls[i].nxt;
}return sum;
}
}using namespace hand_bitset;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=m;i++) cin>>u[i]>>v[i];
for(int i=1;i<=m;i++)
ad(ed[u[i]],v[i]),ad(ed[v[i]],u[i]);
for(int i=1;i<=m;i++)
ans+=add(ed[u[i]],ed[v[i]]);
cout<<ans/3;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 52696kb
input:
4 5 1 2 3 4 0 3 2 0 2 1 2 3 1 3
output:
3
result:
wrong answer 1st words differ - expected: '36', found: '3'