제출 #868159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
868159		oscar1f	Editor (BOI15_edi)	C++17	15 / 100	81 ms	14676 KiB

edi

#include<bits/stdc++.h>
using namespace std;

struct sommet {
	int val,pere;
	vector<pair<int,int>> fils;
};

const int MAX_SOM=300*1000+5;
sommet arbre[MAX_SOM];
int nbOp,nbSom,nouv,pos,suiv,trouve;

vector<pair<int,int>> effacer(vector<pair<int,int>> v,int p) {
	vector<pair<int,int>> r;
	for (auto i:v) {
		if (i.second!=p) {
			r.push_back(i);
		}
	}
	return r;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>nbOp;
	for (int iop=0;iop<nbOp;iop++) {
		cin>>nouv;
		if (nouv>0) {
			nbSom++;
			arbre[nbSom].val=nouv;
			arbre[nbSom].pere=pos;
			arbre[pos].fils.push_back({0,nbSom});
			pos=nbSom;
		}
		else {
			nouv*=-1;
			trouve=0;
			for (int i=(int)arbre[pos].fils.size()-1;i>=0;i--) {
				if (trouve==0 and arbre[pos].fils[i].first<nouv) {
					trouve=1;
					suiv=arbre[pos].fils[i].second;
					arbre[pos].fils=effacer(arbre[pos].fils,suiv);
					arbre[pos].fils.push_back({nouv,suiv});
					pos=suiv;
				}
			}
			if (trouve==0) {
				suiv=arbre[pos].pere;
				arbre[suiv].fils=effacer(arbre[suiv].fils,pos);
				arbre[suiv].fils.push_back({nouv,pos});
				pos=suiv;
			}
		}
		cout<<arbre[pos].val<<"\n";
	}
	/*for (int i=0;i<=nbSom;i++) {
		cout<<i<<" "<<arbre[i].val<<" "<<arbre[i].pere<<endl;
	}*/
	return 0; 
}

• Subtask 1: 0 / 20
• Subtask 2: 15 / 15
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37