Submission #868160

#	Time	Username	Problem	Language	Result	Execution time	Memory
868160		oscar1f	Editor (BOI15_edi)	C++17	15 / 100	132 ms	59220 KiB

edi

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

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

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

vector<int> effacer(vector<int> v,int p) {
	vector<int> r;
	for (auto i:v) {
		if (i!=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[nbSom].corres[pos]=0;
			arbre[pos].corres[nbSom]=0;
			arbre[nbSom].fils.push_back(pos);
			arbre[pos].fils.push_back(nbSom);
			pos=nbSom;
		}
		else {
			nouv*=-1;
			trouve=0;
			for (int i=(int)arbre[pos].fils.size()-1;i>=0 and trouve==0;i--) {
				if (arbre[pos].corres[arbre[pos].fils[i]]<nouv) {
					trouve=1;
					suiv=arbre[pos].fils[i];
				}
			}
			if (trouve==0) {
				suiv=arbre[pos].pere;
			}
			arbre[pos].corres[suiv]=nouv;
			arbre[suiv].corres[pos]=nouv;
			arbre[pos].fils=effacer(arbre[pos].fils,suiv);
			arbre[pos].fils.push_back(suiv);
			pos=suiv;
			//cout<<trouve<<" "<<suiv<<" ";
		}
		cout<<arbre[pos].val<<"\n";
	}
	/*for (int i=0;i<=nbSom;i++) {
		cout<<i<<" "<<arbre[i].val<<endl;
	}*/
	return 0; 
}

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