P3261 JLOI2015 城池攻佔 可並堆

2022-09-22 21:31:42 字數 946 閱讀 2459

戳這裡

又是一道巨佬秒切了的題

我們以每個城市作為一個小根堆,把騎士作為元素,每次彈出不符合的元素之後

向自己的 \(fa\) 進行合併,同時更新堆內的每一個元素

注意特判堆是否為空

#include#define lc t[rt].ls

#define rc t[rt].rs

#define pb push_back

using namespace std;

namespace zzc

while(isdigit(ch))

return x*f;

}const int maxn = 3e5+5;

long long n,m,cnt;

long long ans1[maxn],ans2[maxn],dep[maxn];

vectorg[maxn],h[maxn];

struct city

c[maxn];

struct node

t[maxn];

void pushdown(int rt)

int merge(int x,int y)

int pop(int rt,int id)

void work()

else

}dep[1]=1;

for(int i=1;i<=n;i++) for(auto j:h[i]) dep[j]=dep[i]+1;

for(int i=1;i<=m;i++) ans2[ans1[i]]++;

for(int i=1;i<=n;i++) printf("%lld\n",ans2[i]);

for(int i=1;i<=m;i++) printf("%lld\n",dep[t[i].frm]-dep[ans1[i]]);

}}int main()

P3261 JLOI2015 城池攻佔 題解

小銘銘最近獲得了一副新的桌遊,遊戲中需要用 m 個騎士攻佔 n 個城池。這 n 個城池用 1 到 n 的整數表示。除 1 號城池外,城池 i...

JLOI2015 城池攻佔 可並堆

傳送門 如果直接暴力列舉的話肯定會超時 我們可以從下往上遍歷,維護一個小根堆 每次到達一個節點把戰敗的騎士扔出去 剩下的再繼續向上合併,注意...

luoguP3261 JLOI2015 城池攻佔

有一棵樹 n 個節點,每個節點有一個防禦值,以及兩個屬性,表示一個騎士佔領該節點後攻擊值是加還是乘,有 m 個騎士,有初始位置和初始攻擊值,...