QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#713802#4898. 基础图论练习题DaiRuiChen0070 0ms0kbC++173.2kb2024-11-05 20:35:072024-11-05 20:35:08

Judging History

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

  • [2024-11-05 20:35:08]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-11-05 20:35:07]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef array<ll,2> pii;
const int MAXN=5e4+5,MOD=998244353;
ll CntScc(ll n,vector<ll>&D) {
	ll cnt=0,tg=0; 
	vector <ll> op;
	priority_queue <pii,vector<pii>,greater<pii>> q;
	for(ll d:D) q.push({d,d});
	while(q.size()) {
		ll d=q.top()[0]-tg,ov=q.top()[1]; q.pop();
		if(!d) continue;
		op.push_back(ov);
		if(n<d) break;
		ll k=q.size()?min(n,q.top()[0]-tg)/d:n/d;
		n-=k*d,tg+=k*d,q.push({d+tg,ov});
		if(n<d) cnt=(cnt+d-n)%MOD;
	}
	sort(op.begin(),op.end());
	op.erase(unique(op.begin(),op.end()),op.end());
	D.swap(op);
	return (cnt+n)%MOD;
}
vector<pii> GenScc(ll n,const vector<ll>&D,const vector<ll>&V) {
	vector <pii> scc;
	for(ll v:V) scc.push_back({v,v});
	priority_queue <ll,vector<ll>,greater<ll>> q;
	for(ll d:D) q.push(d);
	ll tg=0;
	while(q.size()) {
		ll d=q.top()-tg; q.pop();
		if(!d) continue;
		if(n<d) break;
		ll k=q.size()?min(n,q.top()-tg)/d:n/d;
		n-=k*d,tg+=k*d,q.push(d+tg);
		for(auto &v:scc) {
			if(v[0]>=n+k*d) continue;
			v[0]-=d*max(0ll,k-(n+k*d-v[0]-1)/d-1);
			if(v[0]>=n&&v[0]>=d) v[0]-=d;
		}
	}
	sort(scc.begin(),scc.end());
	return scc;
}
ll n,ans=0; int m,q;
vector <array<ll,2>> F;
vector <array<ll,3>> G;
vector <ll> D[MAXN];
void solve(int l,int r,const vector<vector<ll>> &grp) {
	if(grp.empty()) return ;
	if(l==r) {
		ll w=F[l][0];
		for(auto o:grp) if(o.size()) {
			for(int i=1;i<(int)o.size();++i) {
				G.push_back({w,o[0],o[i]}),ans=(ans-w)%MOD;
			}
		}
		if(ans<0) ans+=MOD;
		return ;
	}
	int mid=(l+r)>>1;
	vector <vector<ll>> gl,gr;
	for(auto o:grp) if(o.size()>=2) {
		auto scc=GenScc(n,D[mid],o);
		sort(scc.begin(),scc.end());
		gr.push_back({});
		for(int i=0,j;i<(int)scc.size();i=j) {
			gl.push_back({});
			gr.back().push_back(scc[i][1]);
			for(j=i;j<(int)scc.size()&&scc[i][0]==scc[j][0];++j) {
				gl.back().push_back(scc[j][1]);
			}
		}
	}
	solve(l,mid,gl),solve(mid+1,r,gr);
}
int dsu[MAXN<<1];
int find(int x) { return dsu[x]^x?dsu[x]=find(dsu[x]):x; }
signed main() {
	freopen("mst.in","r",stdin);
	freopen("mst.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n>>m>>q;
	F.resize(m);
	for(auto &e:F) cin>>e[1]>>e[0];
	sort(F.begin(),F.end());
	for(int i=0,lst=n%MOD;i<m;++i) {
		ll d=F[i][1],w=F[i][0];
		if(i>0) D[i]=D[i-1];
		D[i].push_back(d);
		ll cur=CntScc(n,D[i]);
		ans=(ans+w*(lst+MOD-cur))%MOD;
		lst=cur;
	}
	G.resize(q);
	vector <ll> idx;
	for(auto &e:G) {
		cin>>e[1]>>e[2]>>e[0];
		idx.push_back(e[1]);
		idx.push_back(e[2]);
	}
	sort(idx.begin(),idx.end());
	idx.erase(unique(idx.begin(),idx.end()),idx.end());
	if(m) {
		auto scc=GenScc(n,D[m-1],idx);
		vector <vector<ll>> grp;
		for(int i=0,j;i<(int)scc.size();i=j) {
			grp.push_back({});
			for(j=i;j<(int)scc.size()&&scc[i][0]==scc[j][0];++j) {
				grp.back().push_back(scc[j][1]);
			}
		}
		solve(0,m-1,grp);
	}
	int tot=idx.size();
	iota(dsu+1,dsu+tot+1,1);
	sort(G.begin(),G.end());
	for(auto e:G) {
		int u=lower_bound(idx.begin(),idx.end(),e[1])-idx.begin()+1;
		int v=lower_bound(idx.begin(),idx.end(),e[2])-idx.begin()+1;
		if(find(u)!=find(v)) ans=(ans+e[0])%MOD,dsu[find(u)]=find(v);
	}
	cout<<ans<<"\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

161199 9 46510
147335 540442844
159493 801351455
149342 821625305
128476 843250712
95524 275754315
139315 106523502
93575 680460786
155498 328812257
146020 410466645
79992 141967 50596784
152210 68644 268349216
72549 96959 42994091
93869 27394 945120577
2909 81886 270684270
12735 35026 871917997
974...

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Dangerous Syscalls

Test #11:

score: 0
Dangerous Syscalls

input:

569435269457904707 2 0
490445920091092693 772271583
144842828305643603 609043885

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Dangerous Syscalls

Test #31:

score: 0
Dangerous Syscalls

input:

755526150476311190 942 0
492334667739348527 1
755523898623296976 1
532486636690994793 1
755526150476030559 1
755526150476249097 1
502164090270592200 1
657422656495814703 1
487200614853438190 1
311037325561173142 1
755526150475651155 1
125287404340238660 1
755524914808674090 1
755526150476177007 1
75...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #3:

0%

Subtask #7:

score: 0
Skipped

Dependency #3:

0%

Subtask #8:

score: 0
Skipped

Dependency #5:

0%

Subtask #9:

score: 0
Skipped

Dependency #1:

0%