QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#401746 | #5308. RPG Pro League | Naganohara_Yoimiya | WA | 308ms | 11640kb | C++14 | 5.1kb | 2024-04-29 11:46:55 | 2024-04-29 11:46:55 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define mk make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
return x*f;
}
template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}
const int N=1e5+5;
int n,q,now[N],val[N];
bool G[N][4];
struct Set{
priority_queue<pair<int,int> >A,B;
void clear(){
priority_queue<pair<int,int> >().swap(A);
priority_queue<pair<int,int> >().swap(B);
}
void insert(pair<int,int>x){A.push(mk(-x.fi,x.se));}
void erase(pair<int,int>x){B.push(mk(-x.fi,x.se));}
pair<int,int> top(){
while(B.size()&&A.top()==B.top())A.pop(),B.pop();
auto res=A.top();return mk(-res.fi,res.se);
}
int size(){return A.size()-B.size();}
}R[4],P[4],Q[4][4];
void ins(int x){
if(now[x]==-1){
for(int i=0;i<4;i++)if(G[x][i])P[i].insert(mk(val[x],x));
}
else R[now[x]].insert(mk(-val[x],x));
if(now[x]!=-1){
for(int i=0;i<4;i++)if(i!=now[x]&&G[x][i])Q[now[x]][i].insert(mk(0,x));
}
}
void del(int x){
if(now[x]==-1){
for(int i=0;i<4;i++)if(G[x][i])P[i].erase(mk(val[x],x));
}
else R[now[x]].erase(mk(-val[x],x));
if(now[x]!=-1){
for(int i=0;i<4;i++)if(i!=now[x]&&G[x][i])Q[now[x]][i].erase(mk(0,x));
}
}
void argu1(int i){ // s -> L[x] -> R[i]
int x=P[i].top().se;
del(x),now[x]=i,ins(x);
// cout<<" argu1 s -> L"<<x<<" -> R"<<i<<endl;
// cout<<" now = ";for(int i=1;i<=n;i++)cout<<now[i]<<" ";puts("");
}
void argu2(int i,int j){ // R[i] -> L[x] -> R[j]
int x=Q[i][j].top().se;
del(x),now[x]=j,ins(x);
// cout<<" argu2 R"<<i<<" -> L"<<x<<" -> R"<<j<<endl;
// cout<<" now = ";for(int i=1;i<=n;i++)cout<<now[i]<<" ";puts("");
}
void argu3(int i){ // R[i] -> L[x] -> s
int x=R[i].top().se;
del(x),now[x]=-1,ins(x);
// cout<<" argu3 R"<<i<<" -> L"<<x<<" -> s"<<endl;
// cout<<" now = ";for(int i=1;i<=n;i++)cout<<now[i]<<" ";puts("");
}
signed main(void){
#ifndef ONLINE_JUDGE
// freopen("in.in","r",stdin);
freopen("q.in","r",stdin);
#endif
n=read();
for(int i=1;i<=n;i++){
vector<int>vis(3);auto gv=[&](char c){if(c=='D')return 0;if(c=='S')return 1;return 2;};
char c=getchar();while(c=='D'||c=='B'||c=='S')vis[gv(c)]=1,c=getchar();
G[i][0]=vis[0],G[i][1]=vis[1],G[i][2]=vis[2],G[i][3]=(vis[0]|vis[1]),val[i]=read();
}
const ll INF=1e18;
vector<vector<ll> >v(6,vector<ll>(6,INF));
auto SP=[&](int s,int t){
vector<vector<int> >pre(6,vector<int>(6,0));auto f=v;
for(int i=0;i<6;i++)f[i][i]=0;
for(int k=0;k<6;k++)for(int i=0;i<6;i++)for(int j=0;j<6;j++){
if(f[i][k]+f[k][j]<f[i][j])f[i][j]=f[i][k]+f[k][j],pre[i][j]=k;
}
vector<int>path;
function<void(int,int)>get_path=[&](int x,int y){
if(v[x][y]==f[x][y])return path.emplace_back(x),void();
int p=pre[x][y];get_path(x,p),get_path(p,y);
};
get_path(s,t);path.emplace_back(t);
return mk(f[s][t],path);
};
auto clr=[&](){for(int i=0;i<6;i++)for(int j=0;j<6;j++)v[i][j]=INF;};
for(int i=1;i<=n;i++)now[i]=-1,ins(i);
ll ans=0;
while(true){
int chk=-2;ll cur=0;
// puts("new team");
for(int x=0;x<4;x++){
for(int i=0;i<4;i++)for(int j=0;j<4;j++)if(Q[i][j].size())v[i][j]=0;
for(int i=0;i<4;i++)if(P[i].size())v[4][i]=P[i].top().fi;
v[x][5]=0;auto [cost,path]=SP(4,5);clr();
// cout<<" argument path = ";for(int x:path)cout<<x<<" ";cout<<"cost = "<<cost<<endl;
if(cost>=INF){chk=x-1;break;}
argu1(path[1]);int k=path.size();assert(k>=3);
for(int i=1;i<=k-3;i++)argu2(path[i],path[i+1]);
cur+=cost;
}
// cout<<"now = ";for(int i=1;i<=n;i++)cout<<now[i]<<" ";puts("");
if(chk==-2){ans+=cur;continue;}
for(int x=chk;x>=0;x--){
for(int i=0;i<4;i++)for(int j=0;j<4;j++)if(Q[i][j].size())v[i][j]=0;
for(int i=0;i<4;i++)if(R[i].size())v[i][4]=R[i].top().fi;
v[5][x]=0;auto [cost,path]=SP(5,4);clr();
// cout<<" argument path = ";for(int x:path)cout<<x<<" ";cout<<"cost = "<<cost<<endl;
int k=path.size();assert(k>=3);
for(int i=1;i<=k-3;i++)argu2(path[i],path[i+1]);
argu3(path[k-2]);
}
break;
}
// cout<<"now ans = "<<ans<<endl;
// cout<<"now = ";for(int i=1;i<=n;i++)cout<<now[i]<<" ";puts("");
q=read();
for(int _=1;_<=q;_++){
int x=read(),w=read();
if(now[x]!=-1)ans+=w-val[x];
del(x),val[x]=w,ins(x);
// cout<<"now ans = "<<ans<<endl;
for(int y=0;y<4;y++)if(P[y].size()){
// cout<<" y = "<<y<<" len = "<<P[y].top().fi<<endl;
for(int i=0;i<4;i++)for(int j=0;j<4;j++)if(Q[i][j].size())v[i][j]=0;
for(int i=0;i<4;i++)if(R[i].size())v[i][4]=R[i].top().fi;
auto [cost,path]=SP(y,4);clr();
// cout<<" argument path = ";for(int x:path)cout<<x<<" ";cout<<"cost = "<<cost<<endl;
if(cost+P[y].top().fi>=0)continue;
ans+=cost+P[y].top().fi;
argu1(y);int k=path.size();assert(k>=2);
for(int i=0;i<=k-3;i++)argu2(path[i],path[i+1]);
argu3(path[k-2]);
break;
}
// cout<<"now = ";for(int i=1;i<=n;i++)cout<<now[i]<<" ";puts("");
cout<<ans<<'\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3788kb
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: 289ms
memory: 11564kb
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: 167ms
memory: 11640kb
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: -100
Wrong Answer
time: 308ms
memory: 11544kb
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:
wrong answer 40358th numbers differ - expected: '40575903472331', found: '40575903477454'