oj.uz

Submission #868157

# Submission time Handle Problem Language Result Execution time Memory
868157 2023-10-30T14:15:49 Z oscar1f Editor (BOI15_edi) C++17
15 / 100
 102 ms 45432 KB 
#include<bits/stdc++.h>
using namespace std;

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

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

vector<pair<int,int>> effacer(vector<pair<int,int>> v,pair<int,int> p) {
	vector<pair<int,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[pos].valAre[nbSom]=0;
			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,{arbre[pos].valAre[suiv],suiv});
					arbre[pos].valAre[suiv]=nouv;
					arbre[pos].fils.push_back({arbre[pos].valAre[suiv],suiv});
					pos=suiv;
				}
			}
			if (trouve==0) {
				suiv=arbre[pos].pere;
				arbre[suiv].fils=effacer(arbre[suiv].fils,{arbre[suiv].valAre[pos],pos});
				arbre[suiv].valAre[pos]=nouv;
				arbre[suiv].fils.push_back({arbre[suiv].valAre[pos],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.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 26204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 45432 KB Output is correct
2 Correct 102 ms 45392 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 41040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 26204 KB Output isn't correct
2 Halted 0 ms 0 KB -