QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#397504 | #5308. RPG Pro League | marher | WA | 240ms | 30936kb | C++14 | 5.1kb | 2024-04-24 11:02:37 | 2024-04-24 11:02:39 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+50,M=10000,inf=1e9+7;
int n,num[8],c[N],k,b[N],p[N],mpp[8],m,dfn[N];
ll ans;
map<string,int>mp;
string s[N];
struct edge
{
int v,w,nxt;
};
struct flows
{
int head[M],cnt=1,st,ed,ans,dep[M],cur[M];
edge e[M];vector<int>eg;
void add(int u,int v,int w)
{
e[++cnt]=(edge){v,w,head[u]};head[u]=cnt;
e[++cnt]=(edge){u,0,head[v]};head[v]=cnt;
}
int bfs()
{
queue<int>q;
for(int i=1;i<=ed;i++)dep[i]=0;
dep[st]=1,q.push(st);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(!dep[v]&&e[i].w>0)
q.push(v),dep[v]=dep[u]+1;
}
}
return dep[ed];
}
int dfs(int now,int flow)
{
if(now==ed||!flow)return flow;
int res=0;
for(int &i=cur[now];i;i=e[i].nxt)
{
int v=e[i].v;
if(dep[v]==dep[now]+1&&e[i].w>0)
{
int x=dfs(v,min(flow-res,e[i].w));
if(x>0)
{
e[i].w-=x;e[i^1].w+=x;res+=x;
if(flow==res)return res;
}
}
}
return res;
}
void dinic()
{
while(bfs()>0)
{
for(int i=1;i<=ed;i++)cur[i]=head[i];
ans+=dfs(st,inf);
}
}
int sol()
{
st=12;ed=13;
for(int i=1;i<=7;i++)add(st,i,num[i]);
for(int i=8;i<=11;i++)eg.push_back(cnt+1),add(i,ed,0);
for(int i=2;i<=7;i++)add(i,8,inf);
add(1,11,inf);add(2,10,inf);add(3,9,inf);
add(4,11,inf);add(4,10,inf);
add(5,11,inf);add(5,9,inf);
add(6,10,inf);add(6,9,inf);
add(7,11,inf);add(7,10,inf);add(7,9,inf);
for(int i=1;i<=n;i++)
{
for(auto x:eg)++e[x].w;dinic();
if(ans!=4*i)return i-1;
}
return 114514;
}
}FLOWS;
struct poi
{
int w,x,tim;
friend bool operator<(poi a,poi b)
{
return a.w>b.w;
}
};
struct node
{
queue<int>to[7];int w,ty;
priority_queue<poi>q,rub;
void pop()
{
while(!q.empty()&&(b[q.top().x]||q.top().tim!=dfn[q.top().x]))q.pop();
}
poi cost()
{
pop();return q.empty()?(poi){inf}:q.top();
}
void popto()
{
for(int i=1;i<=4;i++)while(!to[i].empty()&&b[to[i].front()]!=ty)to[i].pop();
}
void rubpop()
{
while(!rub.empty()&&(b[rub.top().x]!=ty||rub.top().tim!=dfn[rub.top().x]))rub.pop();
}
void push(poi x)
{
ans+=x.w;b[x.x]=ty;w++;
for(int i=0;i<3;i++)if(p[x.x]&(1<<i))to[4-i].push(x.x);
if(p[x.x]!=1)to[1].push(x.x);
}
}q[6];
void insert(int f=0)
{
int ty=0;poi c1=(poi){inf,0};
for(int i=1;i<=4;i++)if(q[i].w<k)
{
poi w=q[i].cost();
if(w.w<c1.w)c1=w,ty=i;
}
int st=0,ed=0;poi c2=(poi){inf,0};
for(int i=1;i<=4;i++)if(q[i].w==k)
{
poi w=q[i].cost();q[i].popto();
if(w.w>=c2.w)continue;
for(int j=1;j<=4;j++)if(i!=j&&q[j].w!=k&&!q[i].to[j].empty())
{
st=i,ed=j;c2=w;
break;
}
}
if(c1.w<=c2.w)
{
q[ty].push(c1);
if(f)q[ty].rub.push((poi){-c1.w,c1.x,dfn[c1.x]});
return;
}
int x=q[st].to[ed].front();
q[st].push(c2);q[ed].push((poi){0,x});--q[st].w;
if(f)q[st].rub.push((poi){-c2.w,c2.x,dfn[c2.x]});
if(f)q[ed].rub.push((poi){-c[x],x,dfn[x]});
}
void add(int i)
{
for(int j=0;j<3;j++)if(p[i]&(1<<j))q[4-j].q.push((poi){c[i],i,dfn[i]});
if(p[i]!=1)q[1].q.push((poi){c[i],i,dfn[i]});
}
void init()
{
k=FLOWS.sol();
for(int i=1;i<=n;i++)add(i);
for(int i=1;i<=4;i++)q[i].ty=i;
for(int fl=1;fl<=4*k;fl++)insert();
}
void del(int x,int w)
{
ans-=c[x];c[x]=w;
--q[b[x]].w;b[x]=0;
add(x);
}
void mk()
{
for(int i=1;i<=4;i++)
{
q[i].rubpop();
del(q[i].rub.top().x,-q[i].rub.top().w);
}
for(int i=1;i<=4;i++)insert(1);
}
main()
{
// freopen("in.txt","r",stdin);
mp["B"]=1;mp["D"]=2;mp["S"]=3;mp["BD"]=4;mp["BS"]=5;mp["DS"]=6;mp["BDS"]=7;
mpp[1]=1;mpp[2]=2;mpp[3]=4;mpp[4]=3;mpp[5]=5;mpp[6]=6;mpp[7]=7;
cin>>n;
for(int i=1;i<=n;i++)cin>>s[i]>>c[i],sort(s[i].begin(),s[i].end()),++num[mp[s[i]]],p[i]=mpp[mp[s[i]]];
cin>>m;m--;
int x,val;cin>>x>>val;c[x]=val;
init();
for(int i=1;i<=n;i++)if(b[i])q[b[i]].rub.push((poi){-c[i],i,0});
int T=n;while(T--)mk();
cout<<ans<<'\n';
// cout<<k<<'\n';
while(m--)
{
int x,val;
cin>>x>>val;dfn[x]++;
// cout<<b[x]<<'\n';
if(b[x])
{
del(x,val);insert(1);
cout<<ans<<'\n';
continue;
}
c[x]=val;add(x);mk();
cout<<ans<<'\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 12772kb
input:
5 BS 3 D 3 B 2 D 4 D 5 2 5 2 1 5
output:
10 12
result:
ok 2 number(s): "10 12"
Test #2:
score: 0
Accepted
time: 206ms
memory: 28508kb
input:
100000 B 727564174 S 231637747 D 246625257 S 975124756 D 844292741 S 809641006 B 396062588 B 883224128 B 311130283 S 434433581 S 509817048 S 993501344 S 508399542 B 279564062 D 950946642 D 819528264 D 412285620 B 968540732 S 953428318 D 902181790 S 172330493 D 725075 B 135580649 D 714478555 B 466916...
output:
40721766963064 40720937650054 40721120372880 40720722768213 40721029809776 40720546822562 40719680807733 40720084910620 40720153432078 40720873952927 40721146683113 40721696875436 40722235723316 40722133896063 40723047443192 40723419347010 40722633976087 40722282806304 40722071958869 40721278798949 ...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 212ms
memory: 29196kb
input:
100000 S 139759881 S 606246897 D 295439937 S 30506154 B 815842927 D 195502949 S 172358189 B 763560428 S 862087943 B 413481091 B 775973599 B 336841814 S 116523655 D 670479401 S 405979654 D 246440323 B 764165518 S 20267667 S 327264314 B 44539411 B 353491632 D 5202858 S 842200033 S 337952200 D 6150168 ...
output:
40524529913817 40524860528295 40524824503871 40524293726866 40524353142964 40524176391157 40524132308308 40524134826811 40524107274580 40524341365401 40524194084164 40524572093940 40524910630137 40525296284478 40525633925207 40525793456210 40526041232042 40526041232042 40526144290799 40526737278038 ...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 221ms
memory: 27576kb
input:
100000 B 567185557 S 731841946 S 365565517 D 767568967 B 450159068 D 658059427 S 790559143 B 356623472 S 541664149 D 447906802 B 407933323 S 403512209 D 187294244 D 351683584 S 504286757 D 212023807 B 51119045 S 84059041 S 819097063 D 115224344 B 104478594 B 446088838 D 153595287 S 749172175 S 57160...
output:
40639770818547 40639473223932 40639909468709 40639327970968 40639021798510 40639377404325 40638848317225 40638755074708 40638463360482 40638463360482 40638225443217 40638907566106 40638907566106 40638707391259 40638642781389 40638809562003 40637986313647 40637481713492 40636989271046 40636464147095 ...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 207ms
memory: 30236kb
input:
100000 BS 609181774 BS 498815665 BS 729225393 S 366911976 D 192782776 DB 109052372 D 927091614 SD 120687185 D 619604491 DB 405398892 BS 947957264 DB 134896320 S 909342292 DS 374808683 SD 810910022 D 636083341 D 719767505 D 576713707 DB 327091245 SD 128393617 B 464665485 DB 186653465 S 50744850 BS 31...
output:
49922035989330 49921636770968 49921944461352 49922449756073 49922666981649 49922155391929 49922220626762 49922165472452 49922033364853 49922182879778 49922118499498 49921629498341 49921194947559 49921237943096 49920830551816 49920785993225 49921523763744 49920936362665 49920399195989 49920353383077 ...
result:
ok 100000 numbers
Test #6:
score: 0
Accepted
time: 240ms
memory: 29808kb
input:
100000 S 46980313 DS 746577279 S 119614887 D 32418943 B 952739459 S 532231646 SD 559263381 DS 631559122 SB 335561329 SD 935559531 DB 548708848 BD 8298741 DS 403723074 DS 559038896 SB 43327419 SD 430897629 B 483781810 B 31916773 B 39977980 S 405078517 D 323989135 SD 584417860 SB 776661769 D 467791168...
output:
42348275359402 42348652439619 42348713198459 42348631107452 42349074844557 42349760441910 42349962186466 42350429498431 42350447771721 42350361082730 42349972717124 42350266522340 42350463555914 42351167696055 42350739802238 42350725554192 42351107085086 42350772822134 42349881535618 42350109052615 ...
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 206ms
memory: 30936kb
input:
100000 BS 213295369 B 455710761 SB 373454236 DB 673322458 S 651168441 BS 359903245 BD 751934633 SD 632609134 S 358152611 S 160649972 D 146822438 B 754830402 B 385092410 B 851559764 DS 481485147 B 224375164 D 961859623 DB 985459185 B 582943091 B 316407251 DS 305843239 DS 723438991 S 53429344 B 523111...
output:
45600208273121 45600317533935 45600175773836 45600173792927 45599452402298 45599812001804 45599878168987 45600637494399 45600782960729 45601107349004 45601024544203 45600077092341 45600360724694 45600356341282 45600663553626 45600478170427 45601258145258 45601572720352 45601860925268 45602282587440 ...
result:
ok 100000 numbers
Test #8:
score: -100
Wrong Answer
time: 228ms
memory: 27380kb
input:
100000 S 716049090 D 833450560 SD 670462747 SB 446815258 B 384907056 D 984726104 SB 462243694 D 922590298 BD 759638240 DS 19626890 SB 248370274 SD 668142001 D 335754916 B 726719900 BD 453285618 D 322601083 D 748915428 DB 977946001 BD 918781134 SB 548154938 S 732129575 B 165403934 DB 307460261 B 5705...
output:
49045290862113 49045178552014 49045718593914 49046497270112 49046433001876 49045928887776 49045419893936 49045345342505 49044998229647 49044353205614 49044963840919 49045148100224 49045371511229 49045472880182 49045419821185 49045011639474 49044314690017 49043828356487 49044412298956 49044755193563 ...
result:
wrong answer 1st numbers differ - expected: '49045162855443', found: '49045290862113'