Submission #105564

#	Time	Username	Problem	Language	Result	Execution time	Memory
105564		Pro_ktmr	Lamps (JOI19_lamps)	C++14	0 / 100	7 ms	5120 KiB

lamp

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair
#define PB push_back

struct UnionFind{
private:
	int N;
	vector<int> par;
public:
	void init(int n){
		N = n;
		par.clear();
		for(int i=0; i<N; i++) par.PB(i);
	}
	int root(int a){
		if(par[a] == a) return a;
		return par[a] = root(par[a]);
	}
	void unite(int a, int b){
		a = root(a);
		b = root(b);
		if(a != b) par[b] = a;
	}
	bool same(int a, int b){
		return (root(a) == root(b));
	}
};

//RmaxQ RAD
struct SegmentTree{
private:
	int N;
	vector<LL> node,lazy;
public:
	void init(int n){
		N = 1;
		while(N < n) N *= 2;
		node.clear();
		for(int i=0; i<2*N-1; i++) node.PB(0LL);
		lazy.clear();
		for(int i=0; i<2*N-1; i++) lazy.PB(0LL);
	}
	void eval(int k, int l, int r){
		if(lazy[k] == 0LL) return;
		node[k] += lazy[k];
		if(r-l != 1){
			lazy[2*k+1] += lazy[k];
			lazy[2*k+2] += lazy[k];
		}
		lazy[k] = 0;
	}
	void add(int a, int b, LL x, int k=0, int l=0, int r=-1){
		if(r == -1) r = N;
		eval(k, l, r);
		if(r <= a || b <= l) return;
		if(a <= l && r <= b){
			lazy[k] += x;
			eval(k, l, r);
		}
		else{
			add(a, b, x, 2*k+1, l, (l+r)/2);
			add(a, b, x, 2*k+2, (l+r)/2, r);
			node[k] = max(node[2*k+1], node[2*k+2]);
		}
	}
	pair<LL,int> maximum(int a, int b, int k=0, int l=0, int r=-1){
		if(r == -1) r = N;
		eval(k, l, r);
		if(r <= a || b <= l) return MP(-1,-1);
		if(r-l == 1) return MP(node[k], k-(N-1));
		if(a <= l && r <= b){
			eval(2*k+1, l, (l+r)/2);
			eval(2*k+2, (l+r)/2, r);
			if(node[2*k+1] > node[2*k+2]) return maximum(a, b, 2*k+1, l, (l+r)/2);
			else return maximum(a, b, 2*k+2, (l+r)/2, r);
		}
		else return max(maximum(a, b, 2*k+1, l, (l+r)/2), maximum(a, b, 2*k+2, (l+r)/2, r));
	}
	void print(){
		for(int i=0; i<2*N-1; i++) cout << node[i] << " ";
		cout << endl;
		for(int i=0; i<2*N-1; i++) cout << lazy[i] << " ";
		cout << endl;
	}
};

int N,Q;
vector<pair<int,LL>> edge[200000];
LL all = 0;
LL ans[200001];

bool visit[200000] = {};
int par[200000] = {};
int parCost[200000] = {};
int pos[200000] = {};
int c;
LL sum;
void dfs(int now, LL cost, int bef){
	visit[now] = true;
	par[c] = bef;
	int dfs_order = c;
	c++;
	for(int i=0; i<edge[now].size(); i++){
		if(visit[edge[now][i].first]) continue;
		sum += edge[now][i].second;
		parCost[c] = edge[now][i].second;
		dfs(edge[now][i].first, cost + edge[now][i].second, dfs_order);
	}
}

LL minimum = LLONG_MAX;
int p = -1;
void dfs2(int now, LL cost){
	for(int i=0; i<edge[now].size(); i++){
		if(visit[edge[now][i].first]) cost += edge[now][i].second;
	}
	if(minimum > cost){
		minimum = cost;
		p = now;
	}
	visit[now] = true;
	c++;
	for(int i=0; i<edge[now].size(); i++){
		if(visit[edge[now][i].first]) continue;
		cost -= edge[now][i].second;
		dfs2(edge[now][i].first, cost);
		cost += edge[now][i].second;
	}
}

int main(){
	scanf("%d", &N);
	for(int i=0; i<N-1; i++){
		int A,B,C,D;
		scanf("%d%d%d%d", &A, &B, &C, &D);
		A--; B--;
		edge[A].PB(MP(B,C));
		edge[B].PB(MP(A,D));
		all += C+D;
	}
	for(int i=0; i<=N; i++) ans[i] = LLONG_MAX;
	
	//root doko
	for(int j=0; j<N; j++) visit[j] = false;
	c = 0;
	sum = 0;
	dfs(0,0, -1);
	for(int j=0; j<N; j++) visit[j] = false;
	c = 0;
	dfs2(0,sum);
	cout << minimum << endl;
	
	return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'void dfs(int, long long int, int)':
lamp.cpp:109:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge[now].size(); i++){
               ~^~~~~~~~~~~~~~~~~
lamp.cpp: In function 'void dfs2(int, long long int)':
lamp.cpp:120:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge[now].size(); i++){
               ~^~~~~~~~~~~~~~~~~
lamp.cpp:129:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge[now].size(); i++){
               ~^~~~~~~~~~~~~~~~~
lamp.cpp: In function 'int main()':
lamp.cpp:138:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
lamp.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &A, &B, &C, &D);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49