QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#397504#5308. RPG Pro LeaguemarherWA 240ms30936kbC++145.1kb2024-04-24 11:02:372024-04-24 11:02:39

Judging History

你现在查看的是最新测评结果

  • [2024-04-24 11:02:39]
  • 评测
  • 测评结果:WA
  • 用时:240ms
  • 内存:30936kb
  • [2024-04-24 11:02:37]
  • 提交

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'