Submission #388733

#	Time	Username	Problem	Language	Result	Execution time	Memory
388733		Iwanttobreakfree	Fountain (eJOI20_fountain)	C++17	0 / 100	1598 ms	257048 KiB

fountain

#include <iostream>
#include <vector>
#include <set>
using namespace std;
void dfs(int a,int i,vector<vector<int> >& cone,vector<vector<int> >& acumulacion,vector<vector<int> >& listas,vector<pair<int,int> >& fuen){
	listas[a].push_back(i);
	if(acumulacion[a].empty())acumulacion[a].push_back(fuen[i].second);
	else{
		int b=acumulacion[a].size();
		acumulacion[a].push_back(acumulacion[a][b-1]+fuen[i].second);
	}
        for(int x:cone[a]){
            dfs(x,i,cone,acumulacion,listas,fuen);
        }
}
int main(){
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
    int n,q,li,num;
    cin>>n>>q;
    int men=1e9;
    vector<pair<int,int> >fuen(n);
    vector<vector<int> >cone(n,vector<int>());
    vector<vector<int> >acumulacion(n,vector<int>());
    vector<vector<int> >listas(n,vector<int>());
    set<int> s;
    set<int>borrar;
    for(int i=0;i<n;i++){
        cin>>fuen[i].second>>fuen[i].first;
        if(fuen[i].second<=men){
            men=fuen[i].second;
            s.insert(i);
        }
        else{
        s.insert(i);
            for(auto it=s.begin();it!=s.end();it++){
            //cout<<*it<<' ';
                if(fuen[*it].second<fuen[i].second){
                    cone[i].push_back(*it);
                    int a=*it;
                    dfs(a,i,cone,acumulacion,listas,fuen);
                    borrar.insert(*it);
                }
            }
            for(int x:borrar)s.erase(x);
            //cout<<'\n';
        }
    }
    while(q--){
        cin>>num>>li;
        num--;
        int b=acumulacion[num].size();
        if(li>acumulacion[num][b-1])cout<<0<<'\n';
        for(int i=b-1;i>=0;i--){
        	if(acumulacion[num][i]<=li){
        		cout<<listas[num][i]<<'\n';
        		break;
			}
		}
    }
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40