oj.uz

Submission #602710

# Submission time Handle Problem Language Result Execution time Memory
602710 2022-07-23T10:30:55 Z vanic The Potion of Great Power (CEOI20_potion) C++14
38 / 100
 357 ms 262144 KB 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=1e5+5, maxu=2e5+5;

struct edge{
	edge *c;
	int val;
	edge(int _val){
		val=_val;
		c=nullptr;
	}
	edge(edge *x){
		if(x==nullptr){
			c=nullptr;
			val=0;
		}
		else{
			c=x->c;
			val=x->val;
		}
	}
};



vector < edge* > root[maxn];
vector < int > kad[maxn];
int n, d;
int h[maxn];


edge* update(edge *x, int val){
	if(x==nullptr){
		return new edge(val);
	}
	if(x->val==val){
		return x->c;
	}
	else if(h[x->val]>h[val]){
		edge *y=new edge(val);
		y->c=x;
		return y;
	}
	x=new edge(x);
	x->c=update(x->c, val);
	return x;
}


void init(int N, int D, int H[]){
	n=N;
	d=D;
	for(int i=0; i<n; i++){
		h[i]=H[i];
	}
	for(int i=0; i<n; i++){
		root[i].push_back(nullptr);
		kad[i].push_back(0);
	}
}

void ispis(edge *x){
	cout << "ispisujem ";
	while(x!=nullptr){
		cout << x->val << ' ';
		x=x->c;
	}
	cout << endl;
}

void curseChanges(int u, int a[], int b[]){
	for(int i=0; i<u; i++){
//		ispis(root[a[i]].back());
//		ispis(root[b[i]].back());
		root[a[i]].push_back(update(root[a[i]].back(), b[i]));
		kad[a[i]].push_back(i+1);
		root[b[i]].push_back(update(root[b[i]].back(), a[i]));
		kad[b[i]].push_back(i+1);
//		ispis(root[a[i]].back());
//		ispis(root[b[i]].back());
	}
}

int binary(int pos, int val){
	int lo=0, hi=kad[pos].size()-1, mid;
	while(lo<hi){
		mid=(lo+hi)/2+1;
		if(kad[pos][mid]>val){
			hi=mid-1;
		}
		else{
			lo=mid;
		}
	}
	return lo;
}

int question(int x, int y, int v){
	int pos1=binary(x, v);
	int pos2=binary(y, v);
//	cout << "posovi " << pos1 << ' ' << pos2 << endl;
	int sol=1e9;
	edge *e1=root[x][pos1];
//	cout << "od " << x << endl;
//	ispis(e1);
	edge *e2=root[y][pos2];
//	cout << "od " << y << endl;
//	ispis(e2);
	e1=root[x][pos1];
	e2=root[y][pos2];
	while(e1!=nullptr && e2!=nullptr){
//		cout << "cmp " << e1->val << ' ' << e2->val << endl;
		sol=min(sol, abs(h[e1->val]-h[e2->val]));
		if(h[e1->val]<h[e2->val]){
			e1=e1->c;
		}
		else{
			e2=e2->c;
		}
	}
	return sol;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5200 KB Output is correct
2 Correct 4 ms 5200 KB Output is correct
3 Correct 3 ms 5200 KB Output is correct
4 Correct 23 ms 12024 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 43096 KB Output is correct
2 Correct 357 ms 43232 KB Output is correct
3 Correct 181 ms 81204 KB Output is correct
4 Runtime error 320 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 49520 KB Output is correct
2 Runtime error 355 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 6848 KB Output is correct
2 Correct 57 ms 8892 KB Output is correct
3 Correct 54 ms 9212 KB Output is correct
4 Correct 169 ms 27280 KB Output is correct
5 Correct 154 ms 21832 KB Output is correct
6 Correct 54 ms 9136 KB Output is correct
7 Correct 158 ms 23964 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 5 ms 5200 KB Output is correct
3 Correct 4 ms 5200 KB Output is correct
4 Correct 3 ms 5200 KB Output is correct
5 Correct 23 ms 12024 KB Output is correct
6 Correct 326 ms 43096 KB Output is correct
7 Correct 357 ms 43232 KB Output is correct
8 Correct 181 ms 81204 KB Output is correct
9 Runtime error 320 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -