QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#381981#6692. Building Companyryh7WA 3ms15980kbC++201.9kb2024-04-07 22:55:562024-04-07 22:55:56

Judging History

This is the latest submission verdict.

  • [2024-04-07 22:55:56]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 15980kb
  • [2024-04-07 22:55:56]
  • Submitted

answer

// Problem: B. Building Company
// Contest: Codeforces - The 13th Shandong ICPC Provincial Collegiate Programming Contest
// URL: https://codeforces.com/gym/104417/problem/B
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using PII = pair<ll,ll>;
using VVI = vector<vector<int>>;
const ll mod = 998244353;
const ll INF = 1e18;
const int N = 2e5 + 10;
using pq = priority_queue<PII , vector<PII> , greater<>>;
map<ll,ll>have;
ll need[N];
ll k[N];
ll g,n;
map<ll,ll> off[N];
map<ll , pq> p;
queue<ll> q;
void add(int pj){
	for(auto [t , v] : off[pj]){
		have[t] += v;
		while(p[t].size() && p[t].top().first <= have[t]){
			need[p[t].top().second]--;
			if(need[p[t].top().second] == 0) q.push(p[t].top().second);
			p[t].pop();
		}	
	}
	
	
	
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>g;
    for(int i = 1 ; i <= g ; i++){
    	ll t,v;
    	cin>>t>>v;
    	//cout<<t<<v<<" ";
    	off[0][t] += v;
    }
    cin>>n;
    //cout<<n;
    for(int i = 1 ; i <= n ; i++){
    	cin>>need[i];
    	//cout<<need[i]<<"\n";
    	for(int j = 1 ; j <= need[i] ; j++){
			ll a,b;
			cin>>a>>b;
			p[a].push({b , i});
    	}
    	cin>>k[i];
    	for(int j = 1 ; j <= k[i] ; j++){
    		ll c,d;
    		cin>>c>>d;
    		off[i][c] += d;
    	}
    }
    
    
    int res = 0;
    /*for(auto [x,v] : have){
    	cout<<x<<" "<<v<<"\n";
    }
    */
    for(int i = 1 ; i <= n ; i++){
    	if(need[i] == 0) {
    		add(i);
    		res++;
    		//cout<<i<<" ";
    	}
    	
    }
    add(0);
    //cout<<endl;
    while(q.size()){
    	auto u = q.front();
    	//cout<<u<<" ";
    	res++;
    	q.pop();
    	add(u);
    }    
    
    
    
    
    
    cout<<res;
    
    
    
}


//5 4 3 2 1
//5 4 3 2 1

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 15964kb

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:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 14532kb

input:

3 610031727 590328742 816793299 18485566 654221125 47823436
10
3 610031727 224714165 816793299 491951703 654221125 593479446
1 610031727 538596643
1 610031727 551036304
3 816793299 262985484 610031727 52580932 654221125 424397787
1 654221125 889197190
3 654221125 126924193 610031727 963399336 816793...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: -100
Wrong Answer
time: 3ms
memory: 15980kb

input:

10 720543365 814021419 777649737 273919247 339754140 472967790 545693058 298289557 949226024 176807538 267294560 819212220 337794335 504610276 137418995 614590802 632556957 783062334 587607535 115519693
100
5 949226024 327424834 777649737 117746775 137418995 152960310 720543365 423301366 267294560 4...

output:

157

result:

wrong answer 1st numbers differ - expected: '100', found: '157'