QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #136929 | #239. Maximum Weighted Matching | nameless_story | 100 ✓ | 1780ms | 40860kb | C++20 | 6.7kb | 2023-08-09 14:12:05 | 2023-08-09 14:12:06 |
Judging History
answer
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define pb push_back
const int kcz=1000000007;
void add(ll& x,ll y)
{
x+=y;
if(x>=kcz)
x-=kcz;
}
mt19937 rnd(0);
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int T;
cin>>T;
// cerr<<(-3)/2<<' '<<(-3)%2<<'\n';
// exit(0);
while(T--)
{
int n,m;
cin>>n>>m;
vector rd(n,0);
map<ll,array<pair<ll,ll>,4> > dp;
vector<set<int>> V(n);
ll ans=0,out=0;
auto upd=[&](int a,int b,int x,int y,ll w,ll num)
{
if(a>b)
swap(a,b),swap(x,y);
dp[(ll)(a<<1)<<20|(b<<1)][x<<1|y]={w,num};
};
auto addedge=[&](int a,int b,int x,int y,ll z)
{
if(a>b)
swap(a,b),swap(x,y);
auto tmp=dp.find((ll)(a<<1)<<20|(b<<1));
if(tmp==dp.end())
dp[(ll)(a<<1)<<20|(b<<1)][3]={z,1ll},
dp[(ll)(a<<1)<<20|(b<<1)][0]={0,1ll};
else
{
if(z>tmp->se[3].fi)
tmp->se[3].fi=z,tmp->se[3].se=0;
if(z==tmp->se[3].fi)
tmp->se[3].se++;
tmp->se[0].se=1;
}
};
auto get=[&](int a,int b,int x,int y)
{
if(a>b)
swap(a,b),swap(x,y);
return dp[(ll)(a<<1)<<20|(b<<1)][x<<1|y].fi;
};
auto getf=[&](int a,int b,int x,int y)
{
if(a>b)
swap(a,b),swap(x,y);
auto tmp=dp.find((ll)(a<<1)<<20|(b<<1));
if(tmp==dp.end())
return (ll)(x==0&&y==0);
return tmp->se[x<<1|y].se;
};
auto getp=[&](int a,int b,int x,int y)
{
if(a>b)
swap(a,b),swap(x,y);
auto tmp=dp.find((ll)(a<<1)<<20|(b<<1));
if(tmp==dp.end())
return pair{0ll,(ll)(x==0&&y==0)};
return tmp->se[x<<1|y];
};
// vector<pair<int,int>> e;
// e.pb({1,2});
// for(int i=3;i<=n;i++)
// {
// int x,y;
// x=rnd()%(i-1)+1;
// y=rnd()%(i-1)+1;
// while(x==y)
// y=rnd()%(i-1)+1;x=1,y=2;
// e.pb({x,i});
// e.pb({i,y});
// }
// m=e.size();
// cerr<<m<<'\n';
for(int i=0,x,y,z;i<m;i++)
{
cin>>x>>y>>z;
// x=e[i].fi,y=e[i].se,z=1;
x--,y--;
// x=i,y=(i+1)%n,z=1;
if(x>y)
swap(x,y);
// if(z>get(x,y,1,1))
// upd(x,y,1,1,z,0);
// if(z==get(x,y,1,1))
// dp[(ll)(x<<1|1)<<20|(y<<1|1)].se+=1;
addedge(x,y,1,1,z);
V[x].insert(y);
V[y].insert(x);
if(z>ans)
ans=z,out=0;
if(z==ans)
out=(out+1)%kcz;
}
priority_queue<ll> bob;
for(int i=0;i<n;i++)
rd[i]=V[i].size(),bob.push(-rd[i]*(ll)m-i);
// exit(0);
// cerr<<"&\n";
int M=m*2,PM=m*2+1;
ans=out=0;
// cerr<<getf(0,1,0,0)<<'\n';
while(!bob.empty())
{
int RD=(-bob.top())/m,u=(-bob.top())%m;
bob.pop();
// cerr<<RD<<' '<<u<<'\n';
if(RD!=rd[u])
continue;
if(rd[u]<2)
{
assert(rd[u]==1);
auto it=V[u].begin();
int x=*it;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
{
if(get(x,u,i,j)>ans)
ans=get(x,u,i,j),out=0;
if(get(x,u,i,j)==ans)
out+=getf(x,u,i,j);
// cerr<<x<<' '<<u<<' '<<i<<' '<<j<<' '<<getf(x,u,i,j)<<'\n';
}
break;
}
assert(rd[u]==2);
assert(V[u].size()==2);
assert(PM>M);
auto it=V[u].begin();
int x=*it;it++;int y=*it;
// cerr<<u<<' '<<x<<' '<<y<<'\n';
vector<pair<ll,ll>> tp(12);//tf(3*4);
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
{
tp[(i<<1|j)]=getp(x,y,i,j);
tp[4|(i<<1|j)]=getp(x,u,i,j);
tp[8|(i<<1|j)]=getp(u,y,i,j);
// tf[(i<<1|j)]=getf(x,y,i,j);
// tf[4+(i<<1|j)]=getf(x,u,i,j);
// tf[8+(i<<1|j)]=getf(u,y,i,j);
}
auto _get=[&](int a,int b,int i,int j)
{
if(a==x&&b==y)
return tp[(i<<1|j)].fi;
if(a==x&&b==u)
return tp[4|(i<<1|j)].fi;
if(a==u&&b==y)
return tp[8|(i<<1|j)].fi;
return 0ll;
};
auto _getf=[&](int a,int b,int i,int j)
{
if(a==x&&b==y)
return tp[(i<<1|j)].se;
if(a==x&&b==u)
return tp[4|(i<<1|j)].se;
if(a==u&&b==y)
return tp[8|(i<<1|j)].se;
return 1ll;
};
for(int ii=1;~ii;ii--)
for(int jj=1;~jj;jj--)
{
ll tmp=0,num=0,t2;
for(int i=0;i<=ii;i++)
for(int j=0;j<=jj;j++)
for(int k=0;k<2;k++)
for(int l=0;k+l<2;l++)
{
t2=_get(x,u,i,k)+_get(u,y,l,j)+_get(x,y,ii-i,jj-j);
if(t2>tmp)
tmp=t2,num=0;
if(t2==tmp)
add(num,_getf(x,u,i,k)*_getf(u,y,l,j)%kcz*_getf(x,y,ii-i,jj-j)%kcz);
}
upd(x,y,ii,jj,tmp,num);
// if(tmp>ans)
// ans=tmp,out=0;
// if(tmp==ans)
// add(out,num);
// cerr<<x<<' '<<y<<' '<<ii<<' '<<jj<<' '<<getf(x,y,ii,jj)<<'\n';
}
PM=M;
M-=rd[x]+rd[y];
V[x].erase(u);
V[y].erase(u);
V[x].insert(y);
V[y].insert(x);
if(V[x].size()<rd[x])
rd[x]=V[x].size(),bob.push(-rd[x]*(ll)m-x);
if(V[y].size()<rd[y])
rd[y]=V[y].size(),bob.push(-rd[y]*(ll)m-y);
rd[u]=0;
M+=rd[x]+rd[y]-2;
}
add(out,kcz);
cout<<ans<<' '<<out<<'\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1780ms
memory: 40860kb
input:
6676 6 10 6 1 1 6 4 1 4 1 1 6 5 1 5 1 1 6 3 1 3 2 1 2 4 1 6 4 1 4 1 1 7 10 4 2 1 4 1 1 1 2 1 1 6 1 6 2 1 1 3 1 3 2 1 1 5 1 5 7 1 7 2 1 7 10 5 3 1 5 7 1 7 2 1 2 3 1 2 1 1 1 4 1 4 3 1 5 6 1 6 7 1 2 3 1 7 10 3 5 1 3 4 1 4 2 1 2 5 1 2 6 1 6 5 1 2 7 1 7 5 1 2 1 1 1 6 1 7 10 5 1 1 5 3 1 3 2 1 2 1 1 2 7 1 ...
output:
3 5 3 6 3 14 3 10 3 11 2 13 2 16 3 6 3 3 3 9 2 9 2 14 4 5 3 10 3 13 3 4 3 5 3 14 3 5 2 15 3 10 3 3 3 3 3 14 2 3 3 6 3 3 3 6 3 11 3 17 3 7 3 2 3 6 3 13 3 9 3 11 3 14 3 6 3 2 2 2 2 11 4 4 3 6 3 6 3 5 3 11 2 10 3 5 4 5 2 18 3 13 3 5 3 3 3 12 3 9 2 11 3 2 3 3 3 4 2 7 3 3 3 3 3 2 3 8 3 10 2 15 3 3 3 12 3...
result:
ok 6676 lines