основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Олимпиады >> Задачи

Страницы: 1
juver
здесь был не раз


Рег.: 06/21/06
Сообщений: 29
Из: Челябинск
Задача с PKU
      #11951 - 08/28/06 12:48 AM

Как решать эту задачу http://acm.pku.edu.cn/JudgeOnline/problem?id=2985. Подскажите пожалуйста.
Мое решение на основе системы непересек. множеств + дерево Фенвика дает TL/


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Michael_Rybak
здесь был не раз
*****

Рег.: 07/09/06
Сообщений: 47
Из: Kyiv, Ukraine
Re: Задача с PKU [Re: juver]
      #11969 - 08/29/06 02:11 AM Вложение (18 загрузки)

У меня сдалась. Таким же методом. В аттаче - весь код, вот ключевые места:

Code:

...

//////////////////////////////////////////////////////////////////////////
//CLogArray
//////////////////////////////////////////////////////////////////////////

template <int MAX_N> struct CLogArray
{
int a[MAX_N];
int sum[MAX_N];
int n;

void SetN(int i_n)
...

inline void Inc(int i, int d)
{
static int x;
static int y;
static int z;
x = 0;
y = n;
while (x + 1 != y)
{
z = (x + y) >> 1;
sum[z] += d;
if (i < z)
y = z;
else
x = z;
}
a[i] += d;
}

...

inline int FindIWithRightSum(int sum, int& actual_sum)
//returns the rightmost x such that
//a[x] + .. +a[n - 1] >= sum
{
static int x;
static int y;
static int z;
static int sum_zy;
x = 0;
y = n;
actual_sum = sum;
while (x + 1 != y)
{
z = (x + y) >> 1;
sum_zy = _GetSum(z, y);
if (sum_zy >= sum)
x = z;
else
{
sum -= sum_zy;
y = z;
}
}
actual_sum += _GetSum(x, y) - sum;
return x;
}

inline int FindIWithRightSum(int sum)
{
int unused;
return FindIWithRightSum(sum, unused);
}

private:

int _GetSum(int i, int j)
{
if (i + 1 == j)
return a[i];
else
return sum[(i + j) >> 1];
}
};

//////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////
//CChainery
//////////////////////////////////////////////////////////////////////////
template <int MAX_N> struct CChainery
{
int color[MAX_N];

int first[MAX_N];
int next[MAX_N];

int count[MAX_N];
int all_count;
int n_groups;

CChainery ()
{
}

void Init0123(int max_n);
bool Merge(int id0, int id1);
//false if already same colors
};

...

//////////////////////////////////////////////////////////////////////////
template <int MAX_N>
bool CChainery<MAX_N>::Merge(int id0, int id1)
//false if already same colors
{
ASSERT(BTW(id0, -1, MAX_N) && BTW(id1, -1, MAX_N));
ASSERT(color[id0] != -1 && color[id1] != -1);
if (color[id0] == color[id1])
return false;

int from = color[id0], to = color[id1];
if (count[from] > count[to])
SWP(from, to);

ASSERT(count[from] > 0);

count[to] += count[from];
count[from] = 0;

int last = -1;
for (int i = first[from]; i != -1; last = i, i = next[i])
color[i] = to;

ASSERT(last != -1);
//last is not -1 because we checked that count[from] > 0

next[last] = first[to];
first[to] = first[from];
first[from] = -1;

//merged 2 groups:
--n_groups;

return true;
}

//////////////////////////////////////////////////////////////////////////
///////CODE THAT WAS ACTUALLY TYPED FOR THIS PROBLEM STARTS HERE//////////
//////////////////////////////////////////////////////////////////////////

const int MAX_N = 1 << 18;
int ncats, nops;
CChainery<MAX_N> gg;
CLogArray<MAX_N> ss;

int main()
{
scanf("%d %d", &ncats, &nops);

gg.Init0123(ncats);
ss.SetN(ncats + 1);
ss.Inc(1, ncats);

REP(cop, nops)
{
int type;
scanf("%d", &type);
if (type == 0)
{
int i, j;
scanf("%d %d", &i, &j);
--i, --j;
if (gg.color[i] != gg.color[j])
{
ss.Inc(gg.count[gg.color[i]], -1);
ss.Inc(gg.count[gg.color[j]], -1);
gg.Merge(i, j);
ss.Inc(gg.count[gg.color[i]], +1);
}
}
else
{
int k;
scanf("%d", &k);
int i = ss.FindIWithRightSum(k);
printf("%d\n", i);
}
}
return 0;
}



Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 418 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, Sergeyev, M_Gustokashin 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 8623

Rate this topic

Переход в