제출 #602710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
602710		vanic	The Potion of Great Power (CEOI20_potion)	C++14	38 / 100	357 ms	262144 KiB

potion

#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
• Subtask 2: 17 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 30