oj.uz

Submission #868160

# Submission time Handle Problem Language Result Execution time Memory
868160 2023-10-30T15:01:28 Z oscar1f Editor (BOI15_edi) C++17
15 / 100
 132 ms 59220 KB 
#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.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 132 ms 59220 KB Output is correct
2 Correct 130 ms 58740 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 42324 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 -