QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#136903 | #241. Chiaki Sequence Revisited | Vengeful_Spirit# | 0 | 0ms | 0kb | C++20 | 3.6kb | 2023-08-09 13:52:24 | 2023-08-09 13:52:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int indec;
const int mo=1e9+7;
#define int long long
struct edge{
int u,v,l;
int f[2][2];
int g[2][2];
edge(){
memset(f,0,sizeof(f));
for(int i:{0,1})for(int j:{0,1})f[i][j]=0;
u = v = l=0;
}
edge(int uu, int vv,int ll) : u(uu), v(vv),l(ll){
f[0][0]=0; f[0][1]=0; f[1][0]=0; f[1][1]=ll;
g[0][0]=1; g[0][1]=0; g[1][0]=0; g[1][1]=1;
}
void rev(){
swap(u,v);
swap(f[0][1],f[1][0]);
swap(g[0][1],g[1][0]);
}
pair<int,int> cal(){
pair<int,int>ans={0,0};
for(int i:{0,1})for(int j:{0,1}){
ans=max(ans,{f[i][j],g[i][j]});
}
return ans;
}
}t[N<<2];
set<pair<int,int>>e[N];
int merge(edge a,edge b){
if(a.v==b.u){
}
else if(a.u==b.u){
a.rev();
}
else if(a.v==b.v){
b.rev();
}
else {
a.rev();
b.rev();
}
if(a.v!=b.u)assert(0);
++indec;
t[indec].u=a.u;
t[indec].v=b.v;
for(int i:{0,1})for(int j:{0,1})for(int k:{0,1})for(int l:{0,1}){
if(!(j&&k)){
if(t[indec].f[i][l]<a.f[i][j]+b.f[k][l]){
t[indec].f[i][l]=a.f[i][j]+b.f[k][l];
t[indec].g[i][l]=(1ll*a.g[i][j]*b.g[k][l])%mo;
}
else if(t[indec].f[i][l]==a.f[i][j]+b.f[k][l]){
t[indec].f[i][l]=a.f[i][j]+b.f[k][l];
(t[indec].g[i][l]+=(1ll*a.g[i][j]*b.g[k][l])%mo)%=mo;
}
}
}
return indec;
}
int place(edge a,edge b){
if(a.v!=b.v)a.rev();
++indec;
t[indec].u=a.u;
t[indec].v=a.v;
if(a.v!=b.v)assert(0);
for(int i:{0,1})for(int j:{0,1})for(int k:{0,1})for(int l:{0,1}){
if(!(i&&k)&&!(j&&l)){
if(t[indec].f[i|k][j|l]<a.f[i][j]+b.f[k][l]){
t[indec].f[i|k][j|l]=a.f[i][j]+b.f[k][l];
t[indec].g[i|k][j|l]=(1ll*a.g[i][j]*b.g[k][l])%mo;
}
else if(t[indec].f[i|k][j|l]==a.f[i][j]+b.f[k][l]){
t[indec].f[i|k][j|l]=a.f[i][j]+b.f[k][l];
(t[indec].g[i|k][j|l]+=(1ll*a.g[i][j]*b.g[k][l])%mo)%=mo;
}
}
}
return indec;
}
void insert(int x,int v,int c){
auto it=e[x].lower_bound({v,0});
if(it!=e[x].end()&&(*it).first==v){
int pre=(*it).second;
int cur=place(t[c],t[pre]);
e[x].erase({v,pre});
e[v].erase({x,pre});
e[x].insert({v,cur});
e[v].insert({x,cur});
}
else{
e[x].insert({v,c});
e[v].insert({x,c});
}
}
int ban[N];
void solve(int n){
for(int i=1;i<=n;i++)ban[i]=0;
queue<int>q;
for(int i=1;i<=n;i++){
if(e[i].size()==2){
q.push(i);
}
}
while(!q.empty()){
int x=q.front();
q.pop();
if(ban[x])continue;
if(e[x].size()!=2)continue;
ban[x]=1;
auto it=e[x].begin();
auto itt=it;
++itt;
int e1=(*it).second;
int e2=(*itt).second;
int cur=merge(t[e1],t[e2]);
e[t[cur].u].erase({x,e1});
e[t[cur].v].erase({x,e2});
insert(t[cur].v,t[cur].u,cur);
if(e[t[cur].v].size()==2){
q.push(t[cur].v);
}
if(e[t[cur].u].size()==2){
q.push(t[cur].u);
}
}
for(int i=1;i<=n;i++){
if(!ban[i]){
int x=(*e[i].begin()).second;
auto res=t[x].cal();
if(res.first<0)assert(0);
if(res.second<0)assert(0);
printf("%lld %lld\n",res.first,res.second);
return;
}
}
assert(0);
}
signed main(){
int T;
scanf("%lld",&T);
while(T--){
int n,m;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=indec;i++){
t[i]=edge();
}
indec=0;
for(int i=1;i<=n;i++){
e[i].clear();
}
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
t[++indec]=edge(x,y,z);
e[x].insert({y,indec});
e[y].insert({x,indec});
}
solve(n);
}
}
详细
Test #1:
score: 0
Runtime Error
input:
100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...