QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#592379#6692. Building CompanyyinyuqinTL 0ms0kbC++141.9kb2024-09-26 22:10:202024-09-26 22:10:21

Judging History

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

  • [2024-09-26 22:10:21]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-09-26 22:10:20]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!(c>='0'&&c<='9')) {if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int maxn=1e5+5;
int cnt,t[maxn],u[maxn],num[maxn],m[maxn],ans;
map<int,int> ma;
priority_queue<pii> q[maxn];
struct node{
	int k;
	vector<int> c,d;
}a[maxn];
void check(int i){
	while(!q[i].empty()&&-q[i].top().fi<=num[i]){
		int id=q[i].top().se;
		q[i].pop();
		m[id]--;
		if(!m[id]){
//			cout<<ans<<" : "<<id<<endl;
//			for(int kkk=1;kkk<=3;kkk++) cout<<kkk<<' '<<num[ma[kkk]]<<endl;
			ans++;
			for(int j=0;j<a[id].k;j++){
				if(ma.find(a[id].c[j])==ma.end()) ma[a[id].c[j]]=++cnt;
				int tp=ma[a[id].c[j]];
				num[tp]+=a[id].d[j];
				check(tp);
			}
//			for(int kkk=1;kkk<=3;kkk++) cout<<kkk<<' '<<num[ma[kkk]]<<endl;
		}
	}
}
signed main()
{
    //ios::sync_with_stdio(false);
    freopen("1.in","r",stdin);
	int g=read();
	for(int i=1;i<=g;i++){
		t[i]=read(),u[i]=read();
		if(ma.find(t[i])==ma.end()) ma[t[i]]=++cnt;
		num[ma[t[i]]]=u[i];
	}
	int n=read();
	for(int i=1;i<=n;i++){
		m[i]=read();
		for(int j=1;j<=m[i];j++){
			int a=read(),b=read();
			if(ma.find(a)==ma.end()) ma[a]=++cnt;
			q[ma[a]].push(mp(-b,i));
		}
		a[i].k=read();
		for(int j=1;j<=a[i].k;j++){
			a[i].c.push_back(read());
			a[i].d.push_back(read());
		}
		if(m[i]==0){
			ans++;
			for(int j=0;j<a[i].k;j++){
				int tp=ma[a[i].c[j]];
				num[tp]+=a[i].d[j];
			}
		}
	}
//	for(int i=1;i<=n;i++){
//		cout<<a[i].k<<endl;
//	}
//	cout<<ans<<endl;
	for(int i=1;i<=cnt;i++){
		check(i);
	}
	cout<<ans<<endl;
//	cout<<cnt<<' '<<ans<<endl;
//	cout<<endl<<q[ma[2]].top().se<<" "<<m[4]<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

2 2 1 1 2
5
1 3 1
0
2 1 1 2 1
2 3 2 2 1
3 1 5 2 3 3 4
1 2 5
3 2 1 1 1 3 4
1 1 3
0
1 3 2

output:


result: