ブルーブリッジ災害後の再建
Pear市にはN(<=50000)の住民点があり、住民点の間にはM(<=20000)の双方向道路がつながっている.これらの住民は2つの間に双方向の道路を通って到着することができる.このような状況は最近まで続いており、深刻な地震でM本の道路がすべて破壊された.
地震後、Pearは一部の道路を修復しようとしたが、i番目の道路を修理するにはPiの時間が必要だった.しかし、Pearはすべての点を連通させるつもりはなく、いくつかの記号の特殊な点を選んで連通させる.
PearはQ(<=50000)回の質問があり、質問するたびに[l,r]の間にすべての番号を選択し、modK=Cの点を番号し、いくつかの道を修理して連通させる.すべての道路の修理は同時に着工できるため、修理を完了する時間は、最も長い時間を費やした道路、すなわち関連する道路のPiの最大値に依存する.
Pearが質問するたびに最小限の時間を計算するのを助けることができますか?ここでの問い合わせは独立しています.つまり、前の問い合わせの修理計画は実行されていません.
【入力形式】
第1行の3つの正の整数N、M、Qは、問題面で述べたように意味する.
次にM行、各行の3つの正の整数Xi、Yi、Piは、XiとYiを結ぶ双方向の道路を表し、修復にはPiの時間が必要である.セルフループがあるかもしれませんが、重いエッジがあるかもしれません.1<=Pi<=1000000.
続いてQ行は、行ごとに4つの正の整数Li、Ri、Ki、Ciがあり、今回問い合わせた点が[Li,Ri]区間の全ての番号Mod Ki=Ciであることを示す点である.質問に参加することを保証するポイントは少なくとも2つあります.
【出力形式】
Q行が出力され、行ごとに正の整数が質問に対する答えを表す.
【サンプル入力】
7 10 4
1 3 10
2 6 9
4 1 5
3 7 4
3 6 9
1 5 8
2 7 4
3 2 10
1 7 6
7 6 9
1 7 1 0
1 7 3 1
2 5 1 0
3 7 2 1
【サンプル出力】
9
6
8
8
【データ範囲】
20%のデータに対して、N,M,Q<=30
40%のデータに対して、N、M、Q<=2000
100%のデータに対して、N<=50000、M<=2*10^5、Q<=50000である.Pi<=10^6. Li,Ri,Kiはいずれも［1,N］の範囲であり,Ciは［0,対応する問い合わせのKi)の範囲である.
生産資源約定:
ピークメモリ消費量<256 M
CPU消費量<5000 ms
要求通りに出力してください.ヘビを描いて印刷しないでください.「入力してください.」と入力します.
すべてのコードを同じソースファイルに配置し、デバッグに合格した後、コピーしてソースコードをコミットします.
注意:main関数は0を返す必要があります
注:ANSI C/ANSI C++標準のみを使用し、コンパイル環境やオペレーティングシステムに依存する特別な関数を呼び出さないでください.
注意:すべての依存する関数は、ソースファイル内のincludeで明確にする必要があります.通常のヘッダファイルは、エンジニアリング設定で省略することはできません.
コミットするときは、目的のコンパイラタイプを選択することに注意してください.
私が使っている最小生成ツリーkruskalの時間が限界を超えているので、まずコードを貼り付けましょう.
地震後、Pearは一部の道路を修復しようとしたが、i番目の道路を修理するにはPiの時間が必要だった.しかし、Pearはすべての点を連通させるつもりはなく、いくつかの記号の特殊な点を選んで連通させる.
PearはQ(<=50000)回の質問があり、質問するたびに[l,r]の間にすべての番号を選択し、modK=Cの点を番号し、いくつかの道を修理して連通させる.すべての道路の修理は同時に着工できるため、修理を完了する時間は、最も長い時間を費やした道路、すなわち関連する道路のPiの最大値に依存する.
Pearが質問するたびに最小限の時間を計算するのを助けることができますか?ここでの問い合わせは独立しています.つまり、前の問い合わせの修理計画は実行されていません.
【入力形式】
第1行の3つの正の整数N、M、Qは、問題面で述べたように意味する.
次にM行、各行の3つの正の整数Xi、Yi、Piは、XiとYiを結ぶ双方向の道路を表し、修復にはPiの時間が必要である.セルフループがあるかもしれませんが、重いエッジがあるかもしれません.1<=Pi<=1000000.
続いてQ行は、行ごとに4つの正の整数Li、Ri、Ki、Ciがあり、今回問い合わせた点が[Li,Ri]区間の全ての番号Mod Ki=Ciであることを示す点である.質問に参加することを保証するポイントは少なくとも2つあります.
【出力形式】
Q行が出力され、行ごとに正の整数が質問に対する答えを表す.
【サンプル入力】
7 10 4
1 3 10
2 6 9
4 1 5
3 7 4
3 6 9
1 5 8
2 7 4
3 2 10
1 7 6
7 6 9
1 7 1 0
1 7 3 1
2 5 1 0
3 7 2 1
【サンプル出力】
9
6
8
8
【データ範囲】
20%のデータに対して、N,M,Q<=30
40%のデータに対して、N、M、Q<=2000
100%のデータに対して、N<=50000、M<=2*10^5、Q<=50000である.Pi<=10^6. Li,Ri,Kiはいずれも［1,N］の範囲であり,Ciは［0,対応する問い合わせのKi)の範囲である.
生産資源約定:
ピークメモリ消費量<256 M
CPU消費量<5000 ms
要求通りに出力してください.ヘビを描いて印刷しないでください.「入力してください.」と入力します.
すべてのコードを同じソースファイルに配置し、デバッグに合格した後、コピーしてソースコードをコミットします.
注意:main関数は0を返す必要があります
注:ANSI C/ANSI C++標準のみを使用し、コンパイル環境やオペレーティングシステムに依存する特別な関数を呼び出さないでください.
注意:すべての依存する関数は、ソースファイル内のincludeで明確にする必要があります.通常のヘッダファイルは、エンジニアリング設定で省略することはできません.
コミットするときは、目的のコンパイラタイプを選択することに注意してください.
私が使っている最小生成ツリーkruskalの時間が限界を超えているので、まずコードを貼り付けましょう.
#include
#include
#include
using namespace std;
int n,m,q,x,y,p,l,r,k,c,maxn,h;
struct edge {
int from,to,cost;
} e[200010];
bool cmp(const edge& e1,const edge& e2) {
return e1.costfy) swap(fx,fy);
pre[fy]=fx;
}
bool judge() {
for (int i=0;i