[NOIP 2016]毎日走るのが好き(lca+むやみにやる)
5554 ワード
2557.[NOIP 2016]毎日ジョギングが好き
時間制限:2 sメモリ制限:512 MB
【タイトル説明】
Cさんはランニングがとても面白いと思って、「毎日走るのが好き」というゲームを作ることにしました.「毎日走るのが好き」は育成ゲームで、プレイヤーが毎日時間通りにオンラインになり、カードを打つ任務を完成する必要がある.
このゲームの地図は、n個のノードとn−1個のエッジを含むツリーと見なすことができ、各エッジは2個のノードを接続し、任意の2つのノードは互いに経路が互いに達することができる.ツリー上のノード番号は、1からnまでの連続正の整数です.
現在mプレイヤーがおり,i番目のプレイヤーの起点はSi,終点はTiである.毎日カードを打つ任務が始まる時、すべてのプレーヤーは0秒目に同時に自分の起点から出発して、毎秒1本の辺の速度を走って、間断なく最短の経路に沿って自分の終点に向かって走って、終点に着いた後にそのプレーヤーはカードを打つ任務を完成しました.(地図は木なので、一人一人の経路は唯一です)
Cちゃんはゲームの活躍度が知りたくて、ノードごとにオブザーバーが置かれていました.ノードのオブザーバーは、Wj秒目にプレイヤーを観察することを選択し、1人のプレイヤーがこのオブザーバーに観察され、そのプレイヤーがWj秒目にもノードJに到着することができる.Cさんはオブザーバー一人一人が何人観察するか知りたいです.
注意:あるプレイヤーが自分のゴールに着いたら、そのプレイヤーはゲームを終了すると思います.彼はしばらく待ってからオブザーバーに観察されることはできません.すなわち、ノードJを終点とするプレイヤーに対して、Wj秒目に再び終点に到達すると、ノードJのオブザーバーはそのプレイヤーを観察できない.もし彼がちょうどWj秒でゴールに着いたら、ノードのオブザーバーはこのプレイヤーを観察することができます.
【入力形式】
最初の行には2つの整数nとmがあります.このうちnはツリーのノード数を表し,またオブザーバーの数を表し,mはプレイヤーの数を表す.
次に、n−1行の各行の2つの整数uおよびvは、ノードuからノードvまでのエッジを表す.
次の行n個の整数であり、j番目の整数はWjであり、ノードjがオブザーバーが現れる時間を表す.
次にm行,1行あたり2つの整数SiとTiが,1プレイヤーの始点と終点を表す.
全てのデータに対して,1≦Si,Ti≦n,0≦Wj≦nを保証した.
【出力形式】
1行n個の整数を出力し,j番目の整数はノードjのオブザーバーがどれだけの人を観察できるかを示す.
【サンプル1入力】
【サンプル1出力】
【サンプル2入力】
5 3
1 2
2 3
2 4
1 5
0 1 0 3 0
3 1
1 4
5 5
【サンプル2出力】
【ヒント】
1番ポイントについては、W 1=0なので、起点が1番ポイントのプレイヤーのみが観察されるので、プレイヤー1とプレイヤー2が観察され、合計2人が観察される.
2番ポイントについては,2秒目にこの時点でプレイヤーがいないため,計0人が観察された.
3番ポイントについては,5秒目にこの時点で0人が観察されなかった.
4番ポイントについては,プレイヤー1が観察され,合計1人が観察された.
5番ポイントについては,プレイヤー2が観察され,合計1人が観察された.
6番ポイントについては、プレイヤー3が観察され、合計1人が観察された.
问题を见たばかりの时、ぼんやりした颜をしていた...
(定義:dp[]配列は深さ配列,tim[]と題して与えられたw[]である)
まず経路を2つの部分に分けて考えると,第1の部分はS(起点)からlca,第2の部分はlcaからT(終点)である.1人がiで検出された場合、2つのケースがあります.
1.第1の部分で検出された場合、dp[i]+tim[i]=dp[S];
2.第2の部分において、len-(dp[T]-dp[i])=tim[i]、すなわちdp[i]-tim[i]=dp[T]-lenのみが検出される.(lenはSからTまでの距離)
木の断面が詰まっている可能性があるので、バケツの方法を使います.
まず,そのlcaの上に1つの点が影響しないことを考慮する(lcaよりも深さが小さい点は歩かない)
2つのバケツをメンテナンスする:1つの起点のバケツupと1つの終点のバケツdn(メンテナンスの値);
現在のノードをiとする
では、iを起点とする起点のバケツに「1」を加え(具体的には、1つのA配列が各点から出発する人の個数を記録している)、大人に変えるとup[dp[i]+=A[i];
同様に、iを終点とするバケツに1を加え、(注意:バケツの中でメンテナンスされているのは値なので、大人に変えるとdn[dp[i]-len]++となり、上式に合わせて見る)
lcaに遡ると、それをlcaとする点の影響は自然に解消されるので、dfsが戻ってくると、iをlcaの起点とするupが1減、(人話:up[x]-、xをiをlcaの起点とする)、iをlcaの終点とするdnが1減(人話:dn[x]-、xをiをlcaの終点とする)する
ではansは?ans[i]=up[dp[i]+w[i]]+dn[dp[i]-w[i]];(すなわち、対応する寄与可能なバケツ)
チェーンなら重いかもしれないので、差で計算すればいいです.
2パスdfs,複雑度O(n+m)
注意:dp[i]-lenは負の数を出し、300000を統一的に加算して処理することができます.
コード:
時間制限:2 sメモリ制限:512 MB
【タイトル説明】
Cさんはランニングがとても面白いと思って、「毎日走るのが好き」というゲームを作ることにしました.「毎日走るのが好き」は育成ゲームで、プレイヤーが毎日時間通りにオンラインになり、カードを打つ任務を完成する必要がある.
このゲームの地図は、n個のノードとn−1個のエッジを含むツリーと見なすことができ、各エッジは2個のノードを接続し、任意の2つのノードは互いに経路が互いに達することができる.ツリー上のノード番号は、1からnまでの連続正の整数です.
現在mプレイヤーがおり,i番目のプレイヤーの起点はSi,終点はTiである.毎日カードを打つ任務が始まる時、すべてのプレーヤーは0秒目に同時に自分の起点から出発して、毎秒1本の辺の速度を走って、間断なく最短の経路に沿って自分の終点に向かって走って、終点に着いた後にそのプレーヤーはカードを打つ任務を完成しました.(地図は木なので、一人一人の経路は唯一です)
Cちゃんはゲームの活躍度が知りたくて、ノードごとにオブザーバーが置かれていました.ノードのオブザーバーは、Wj秒目にプレイヤーを観察することを選択し、1人のプレイヤーがこのオブザーバーに観察され、そのプレイヤーがWj秒目にもノードJに到着することができる.Cさんはオブザーバー一人一人が何人観察するか知りたいです.
注意:あるプレイヤーが自分のゴールに着いたら、そのプレイヤーはゲームを終了すると思います.彼はしばらく待ってからオブザーバーに観察されることはできません.すなわち、ノードJを終点とするプレイヤーに対して、Wj秒目に再び終点に到達すると、ノードJのオブザーバーはそのプレイヤーを観察できない.もし彼がちょうどWj秒でゴールに着いたら、ノードのオブザーバーはこのプレイヤーを観察することができます.
【入力形式】
最初の行には2つの整数nとmがあります.このうちnはツリーのノード数を表し,またオブザーバーの数を表し,mはプレイヤーの数を表す.
次に、n−1行の各行の2つの整数uおよびvは、ノードuからノードvまでのエッジを表す.
次の行n個の整数であり、j番目の整数はWjであり、ノードjがオブザーバーが現れる時間を表す.
次にm行,1行あたり2つの整数SiとTiが,1プレイヤーの始点と終点を表す.
全てのデータに対して,1≦Si,Ti≦n,0≦Wj≦nを保証した.
【出力形式】
1行n個の整数を出力し,j番目の整数はノードjのオブザーバーがどれだけの人を観察できるかを示す.
【サンプル1入力】
6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6
【サンプル1出力】
2 0 0 1 1 1【サンプル2入力】
5 3
1 2
2 3
2 4
1 5
0 1 0 3 0
3 1
1 4
5 5
【サンプル2出力】
1 2 1 0 1【ヒント】
1番ポイントについては、W 1=0なので、起点が1番ポイントのプレイヤーのみが観察されるので、プレイヤー1とプレイヤー2が観察され、合計2人が観察される.
2番ポイントについては,2秒目にこの時点でプレイヤーがいないため,計0人が観察された.
3番ポイントについては,5秒目にこの時点で0人が観察されなかった.
4番ポイントについては,プレイヤー1が観察され,合計1人が観察された.
5番ポイントについては,プレイヤー2が観察され,合計1人が観察された.
6番ポイントについては、プレイヤー3が観察され、合計1人が観察された.
问题を见たばかりの时、ぼんやりした颜をしていた...
(定義:dp[]配列は深さ配列,tim[]と題して与えられたw[]である)
まず経路を2つの部分に分けて考えると,第1の部分はS(起点)からlca,第2の部分はlcaからT(終点)である.1人がiで検出された場合、2つのケースがあります.
1.第1の部分で検出された場合、dp[i]+tim[i]=dp[S];
2.第2の部分において、len-(dp[T]-dp[i])=tim[i]、すなわちdp[i]-tim[i]=dp[T]-lenのみが検出される.(lenはSからTまでの距離)
木の断面が詰まっている可能性があるので、バケツの方法を使います.
まず,そのlcaの上に1つの点が影響しないことを考慮する(lcaよりも深さが小さい点は歩かない)
2つのバケツをメンテナンスする:1つの起点のバケツupと1つの終点のバケツdn(メンテナンスの値);
現在のノードをiとする
では、iを起点とする起点のバケツに「1」を加え(具体的には、1つのA配列が各点から出発する人の個数を記録している)、大人に変えるとup[dp[i]+=A[i];
同様に、iを終点とするバケツに1を加え、(注意:バケツの中でメンテナンスされているのは値なので、大人に変えるとdn[dp[i]-len]++となり、上式に合わせて見る)
lcaに遡ると、それをlcaとする点の影響は自然に解消されるので、dfsが戻ってくると、iをlcaの起点とするupが1減、(人話:up[x]-、xをiをlcaの起点とする)、iをlcaの終点とするdnが1減(人話:dn[x]-、xをiをlcaの終点とする)する
ではansは?ans[i]=up[dp[i]+w[i]]+dn[dp[i]-w[i]];(すなわち、対応する寄与可能なバケツ)
チェーンなら重いかもしれないので、差で計算すればいいです.
2パスdfs,複雑度O(n+m)
注意:dp[i]-lenは負の数を出し、300000を統一的に加算して処理することができます.
コード:
#include
#include
#include
#define maxn 300005
#define maxx 600010
#define MA 300000
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline int read()
{ char c=getchar();int x=0,y=1;
while(c'9'){if(c=='-') y=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*y;
}
int n,m,ans[maxn],fans[maxn],dp[maxn],ance[maxn],f[maxn],hea[maxn],nhea[maxn],num,nnum,num1,num2,num3,A[maxn];
int hea1[maxx],hea2[maxx],hea3[maxx],tim[maxn],dn[maxx],upp[maxx];
bool ok[maxn];
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
inline void unionn(int x,int y){int a=find(x),b=find(y);if(a!=b) f[a]=b;}
struct road{int en,nex;}ro[maxx],ro1[maxx],ro2[maxx],ro3[maxx];
struct query{int en,nex,id;}qu[maxx];
inline void addq(int x,int y,int z)
{ qu[nnum].en=y;qu[nnum].id=z;qu[nnum].nex=nhea[x];nhea[x]=nnum++;
qu[nnum].en=x;qu[nnum].id=z;qu[nnum].nex=nhea[y];nhea[y]=nnum++;
}
inline void add(int x,int y){ro[num].en=y;ro[num].nex=hea[x];hea[x]=num++;}
inline void add1(int x,int y){ro1[num1].en=y;ro1[num1].nex=hea1[x];hea1[x]=num1++;}
inline void add2(int x,int y){ro2[num2].en=y;ro2[num2].nex=hea2[x];hea2[x]=num2++;}
inline void add3(int x,int y){ro3[num3].en=y;ro3[num3].nex=hea3[x];hea3[x]=num3++;}
void lca(int x,int y)
{ ance[x]=x;ok[x]=1;dp[x]=dp[y]+1;
for(int i=hea[x];i!=-1;i=ro[i].nex)
{ int v=ro[i].en;if(ok[v]) continue;
lca(v,x);unionn(x,v);ance[find(x)]=x;
}
for(int i=nhea[x];i!=-1;i=qu[i].nex)
{ int v=qu[i].en;
if(ok[v]) ans[qu[i].id]=ance[find(v)];
}
}
void dfs(int x,int y)
{ int t1=upp[dp[x]+tim[x]],t2=dn[dp[x]-tim[x]+MA];upp[dp[x]]+=A[x];
for(int i=hea1[x];i!=-1;i=ro1[i].nex) ++dn[ro1[i].en+MA];
for(int i=hea[x];i!=-1;i=ro[i].nex) if(ro[i].en!=y) dfs(ro[i].en,x);
fans[x]=upp[dp[x]+tim[x]]+dn[dp[x]-tim[x]+MA]-t1-t2;
for(int i=hea2[x];i!=-1;i=ro2[i].nex){int v=ro2[i].en;--upp[v];if(v==dp[x]+tim[x]) --fans[x];}
for(int i=hea3[x];i!=-1;i=ro3[i].nex) --dn[ro3[i].en+MA];
}
void init()
{ mem(hea,-1);mem(nhea,-1);mem(hea1,-1);mem(hea2,-1);mem(hea3,-1);
for(int i=1;i<=n;++i) f[i]=i;
}
int main()
{ //freopen("runninga.in","r",stdin);
//freopen("runninga.out","w",stdout);
int __size__=64<<20;//
char *__p__=(char*)malloc(__size__)+__size__;
__asm__("movl %0, %%esp
"::"r"(__p__));
n=read();m=read();
init();int x,y;
for(int i=1;i