QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#401746#5308. RPG Pro LeagueNaganohara_YoimiyaWA 308ms11640kbC++145.1kb2024-04-29 11:46:552024-04-29 11:46:55

Judging History

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

  • [2024-04-29 11:46:55]
  • 评测
  • 测评结果:WA
  • 用时:308ms
  • 内存:11640kb
  • [2024-04-29 11:46:55]
  • 提交

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'