結果

問題 No.386 貪欲な領主
コンテスト
ユーザー horiesiniti
提出日時 2016-06-16 12:47:00
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 575 ms / 2,000 ms
コード長 3,622 bytes
コンパイル時間 1,147 ms
コンパイル使用メモリ 97,500 KB
実行使用メモリ 57,616 KB
最終ジャッジ日時 2024-10-12 02:30:34
合計ジャッジ時間 4,763 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:160:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  160 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
main.cpp:162:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  162 |                 scanf("%d %d",&a,&b);
      |                 ~~~~~^~~~~~~~~~~~~~~
main.cpp:168:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  168 |                 scanf("%d",&a);
      |                 ~~~~~^~~~~~~~~
main.cpp:173:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  173 |         scanf("%d",&m);
      |         ~~~~~^~~~~~~~~
main.cpp:175:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  175 |                 scanf("%d %d %d",&a,&b,&c);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <map>
#include <set>
#include <stdio.h>
#include <vector>
#include <stack>
#include <string.h>
#include <algorithm>


const int LIMIT=150000;
std::vector<int> tree[LIMIT];
std::vector<long long int> cost;
std::vector<long long int> sumCost;
std::map<int,long long int> sToG[LIMIT];

std::map<long long int,int> countToP;
std::map<int,long long int> pToCount;
long long int count=0;
int humanCount=0;


long long int ans=0;
void g(int goal){
	std::map<int,long long int>::iterator it;
	//printf("?%d\n",goal);
	for(it=sToG[goal].begin();it!=sToG[goal].end();it++){
		int start=(*it).first;
		long long int t=(*it).second;
		if(pToCount.find(start)!=pToCount.end()){
			long long int count1=pToCount[start];
			long long int count2=pToCount[goal];
			long long int count3=std::min(count1,count2);
			std::map<long long int,int>::iterator it2=countToP.lower_bound(count3);
			int center=(*it2).second;
			//std::cout<<"x="<<start<<" "<<goal<<" "<<sumCost[start]<<" "<<sumCost[goal]<<" "<<center<<"\n";
			long long int temp=(sumCost[goal]-sumCost[center])+(sumCost[start]-sumCost[center])+cost[center];
			ans+=(temp*t);
		}
	}
}
void h(){
	count=0;
	std::stack<int> noStc,iStc;
	std::stack<long long int> oldCountStc;
	noStc.push(-1);
	iStc.push(-1);
	oldCountStc.push(-1);
	
	noStc.push(0);
	iStc.push(0);
	oldCountStc.push(count);
	pToCount[0]=count;
	countToP[count]=0;
	while(noStc.size()>1){
		int no=noStc.top();
		int i=iStc.top();
		long long int oldCount=oldCountStc.top();
		if(i==0){
			g(no);
		}
		std::map<int,long long int>::iterator it;
		//std::cout<<"\n no="<<no<<"\n";
		//for(it=pToCount.begin();it!=pToCount.end();it++){
		//	std::cout<<"("<<(*it).first<<" "<<(*it).second<<" "<<")";
		//}
		//std::cout<<"=r\n";
		if (i<tree[no].size()){
			noStc.pop();
			
			
			
			if (noStc.top()==tree[no][i]){
				noStc.push(no);
				iStc.pop();
				iStc.push(i+1);
				continue;
			}
			noStc.push(no);
			count++;
			countToP.erase(oldCount);
			countToP[count]=no;
			
			oldCountStc.pop();
			oldCountStc.push(count);
			count++;
			
			pToCount[tree[no][i]]=count;
			countToP[count]=tree[no][i];
			
			oldCountStc.push(count);
			noStc.push(tree[no][i]);
			iStc.push(0);
			count++;
		}else{
			count++;
			pToCount[no]=count;
			countToP.erase(oldCount);
			count++;
			oldCountStc.pop();
			iStc.pop();
			noStc.pop();
			
			int i=iStc.top();
			iStc.pop();
			iStc.push(i+1);
		}
	}
}
void f(){
	std::stack<int> noStc,iStc;
	std::stack<long long int> costStc;
	noStc.push(-1);
	iStc.push(-1);
	costStc.push(0);
	
	noStc.push(0);
	iStc.push(0);
	costStc.push(cost[0]);
	sumCost[0]=cost[0];
	
	while(noStc.size()>1){
		int no=noStc.top();
		int i=iStc.top();
		long long int sumc=costStc.top();
		
		if (i<tree[no].size()){
			noStc.pop();
			if (noStc.top()==tree[no][i]){
				noStc.push(no);
				iStc.pop();
				iStc.push(i+1);
				continue;
			}

			noStc.push(no);
			
			long long int sumc2=sumc+cost[tree[no][i]];
			
			sumCost[tree[no][i]]=sumc2;
			noStc.push(tree[no][i]);
			iStc.push(0);
			costStc.push(sumc2);
		}else{
			costStc.pop();
			iStc.pop();
			noStc.pop();
			
			int i=iStc.top();
			iStc.pop();
			iStc.push(i+1);
		}
	}
}


int main() {
	// your code goes here
	int n,a,b,c;
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		scanf("%d %d",&a,&b);
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	
	for(int i=0;i<n;i++){
		scanf("%d",&a);
		cost.push_back(a);
		sumCost.push_back(0);
	}
	int m;
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&a,&b,&c);
		sToG[a][b]+=c;
		sToG[b][a]+=c;
	}
	f();
	h();
	std::cout<<ans<<"\n";
	return 0;
}
0