#387017 (C++11) No.900 aδδitivee

提出ソース

結果

問題	No.900 aδδitivee
ユーザー	latte0119
提出日時	2019-10-05 01:11:10
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	167 ms / 2,000 ms
コード長	3,111 bytes
コンパイル時間	1,766 ms
コンパイル使用メモリ	174,120 KB
実行使用メモリ	36,040 KB
最終ジャッジ日時	2024-04-14 22:42:22
合計ジャッジ時間	8,586 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 6,812 KB
testcase_01	AC	3 ms 6,816 KB
testcase_02	AC	3 ms 6,816 KB
testcase_03	AC	3 ms 6,940 KB
testcase_04	AC	3 ms 6,940 KB
testcase_05	AC	3 ms 6,940 KB
testcase_06	AC	3 ms 6,940 KB
testcase_07	AC	163 ms 33,072 KB
testcase_08	AC	163 ms 32,772 KB
testcase_09	AC	166 ms 32,948 KB
testcase_10	AC	161 ms 32,948 KB
testcase_11	AC	163 ms 33,076 KB
testcase_12	AC	160 ms 32,984 KB
testcase_13	AC	160 ms 33,076 KB
testcase_14	AC	166 ms 32,952 KB
testcase_15	AC	164 ms 32,948 KB
testcase_16	AC	161 ms 32,820 KB
testcase_17	AC	165 ms 32,948 KB
testcase_18	AC	160 ms 33,076 KB
testcase_19	AC	162 ms 32,944 KB
testcase_20	AC	167 ms 32,820 KB
testcase_21	AC	162 ms 33,076 KB
testcase_22	AC	149 ms 36,028 KB
testcase_23	AC	146 ms 36,020 KB
testcase_24	AC	148 ms 36,020 KB
testcase_25	AC	147 ms 35,964 KB
testcase_26	AC	147 ms 36,024 KB
testcase_27	AC	143 ms 35,896 KB
testcase_28	AC	147 ms 36,040 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:136:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  136 |         int N;scanf("%lld",&N);
      |               ~~~~~^~~~~~~~~~~
main.cpp:140:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  140 |                 scanf("%lld%lld%lld",&a,&b,&c);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:148:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  148 |         int Q;scanf("%lld",&Q);
      |               ~~~~~^~~~~~~~~~~
main.cpp:150:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  150 |                 int t;scanf("%lld",&t);
      |                       ~~~~~^~~~~~~~~~~
main.cpp:153:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  153 |                         scanf("%lld%lld",&a,&x);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:158:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  158 |                         int b;scanf("%lld",&b);
      |                               ~~~~~^~~~~~~~~~~

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}


template<class W,int lg=1>
struct WeightedTree{
	struct Edge{
		int to;
		W cost;
		Edge(int to,W cost):to(to),cost(cost){}
	};

	int V;
	vector<vector<Edge>>G;

	vector<vector<int>>par;
	vector<int>dep,sz,head;
	vector<int>tin,tout;
	vector<W>dist;
	WeightedTree(int V):V(V),G(V),par(lg,vector<int>(V)),sz(V),dep(V),head(V),dist(V),tin(V),tout(V){}

	void addEdge(int a,int b,W c=W(1)){
		G[a].push_back(Edge(b,c));
		G[b].push_back(Edge(a,c));
	}

	void dfs(int v,int p,int d,W c){
		par[0][v]=p;
		dep[v]=d;
		sz[v]=1;
		dist[v]=c;

		for(auto &e:G[v]){
			if(e.to==p)continue;
			dfs(e.to,v,d+1,c+e.cost);
			sz[v]+=sz[e.to];
			if(G[v][0].to==p||sz[e.to]>sz[G[v][0].to])swap(G[v][0],e);
		}
	}

	void dfs_hld(int v,int &tt){
		tin[v]=tt++;
		for(auto &e:G[v]){
			if(e.to==par[0][v])continue;
			head[e.to]=(e.to==G[v][0].to)?head[v]:e.to;
			dfs_hld(e.to,tt);
		}
		tout[v]=tt;
	}
	void init(){
		dfs(0,-1,0,W(0));
		int tt=0;
		dfs_hld(0,tt);

		for(int i=0;i+1<lg;i++){
			for(int j=0;j<V;j++){
				if(par[i][j]==-1)par[i+1][j]=-1;
				else par[i+1][j]=par[i][par[i][j]];
			}
		}
	}

	// 1<<lg >=N-1!!!!!
	int getLCA(int u,int v){
		
		if(dep[u]<dep[v])swap(u,v);
		rep(i,lg)if((dep[u]-dep[v])>>i&1)u=par[i][u];
		if(u==v)return u;

		for(int i=lg-1;i>=0;i--)if(par[i][u]!=par[i][v])u=par[i][u],v=par[i][v];
		return par[0][v];
	}

	int getLength(int a,int b=0){
		int l=getLCA(a,b);
		return dep[a]+dep[b]-2*dep[l];
	}
	W getDistance(int a,int b=0){
		int l=getLCA(a,b);
		return dist[a]+dist[b]-2*dist[l];
	}

	int getPar(int v,int k=0){
		return par[k][v];
	}
	int getDepth(int v){
		return dep[v];
	}
	int getIn(int v){
		return tin[v];
	}
	int getOut(int v){
		return tout[v];
	}
};


/*
0-indexed
add(k,x): a[k]+=x
sum(k): sum(a[0,k])
space:O(N)
time:O(logN) per query
*/
struct BinaryIndexedTree{
	int n;
	vector<int>dat;
	BinaryIndexedTree(int n=0):n(n){
		dat.resize(n+1);
	}
	void add(int k,int x){
		for(k++;k<=n;k+=k&-k)dat[k]+=x;
	}
	int sum(int k){
		int ret=0;
		for(k++;k;k-=k&-k)ret+=dat[k];
		return ret;
	}
};

signed main(){
	int N;scanf("%lld",&N);
	WeightedTree<int,20>T(N);
	rep(i,N-1){
		int a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		T.addEdge(a,b,c);
	}

	T.init();

	BinaryIndexedTree bit0(111111),bit1(111111);

	int Q;scanf("%lld",&Q);
	while(Q--){
		int t;scanf("%lld",&t);
		if(t==1){
			int a,x;
			scanf("%lld%lld",&a,&x);
			bit1.add(T.getIn(a),x);bit1.add(T.getOut(a),-x);
			bit0.add(T.getIn(a),-T.getDepth(a)*x);bit0.add(T.getOut(a),T.getDepth(a)*x);
		}
		else{
			int b;scanf("%lld",&b);
			int ans=T.getDistance(b);
			ans+=bit0.sum(T.getIn(b));
			ans+=bit1.sum(T.getIn(b))*T.getDepth(b);
			printf("%lld\n",ans);
		}
	}
	return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード