Submission #102691

#	Time	Username	Problem	Language	Result	Execution time	Memory
102691		tincamatei	Election Campaign (JOI15_election_campaign)	C++14	20 / 100	235 ms	30464 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000;
const int MAX_M = 100000;
const int INF = 1000000000;

vector<int> graph[1+MAX_N];
vector<int> chainstart[1+MAX_N];
int dp[1+MAX_N], subarb[1+MAX_N], cost[MAX_N];

void calcSubarb(int nod, int papa = 0) {
	subarb[nod] = chainstart[nod].size();
	for(auto it: graph[nod])
		if(it != papa) {
			calcSubarb(it, nod);
			subarb[nod] += subarb[it];
		}
}

struct NodeCell {
	static int bestCost[1+MAX_N];
	static bool nodeExists[1+MAX_N];
	static int lazy;

	vector<pair<int, int> > chains;

	static void init() {
		for(int i = 0; i <= MAX_N; ++i)
			nodeExists[i] = false;
		lazy = 0;
	}

	void reset() {
		for(int i = 0; i < chains.size(); ++i) {
			nodeExists[chains[i].first] = false;
			chains[i].second = getVal(chains[i].first);
		}
	}

	static bool findNode(int nod) {
		return nodeExists[nod];
	}

	static void addVal(int x) {
		lazy += x;
	}

	static int getVal(int nod) {
		return bestCost[nod] + lazy;
	}

	static void insertNode(int nod, int val) {
		nodeExists[nod] = true;
		bestCost[nod] = val - lazy;
	}

	static void eraseNode(int nod) {
		nodeExists[nod] = false;
	}
} node[1+MAX_N]; 

int NodeCell::bestCost[1+MAX_N];
int NodeCell::lazy;
bool NodeCell::nodeExists[1+MAX_N];

void dfs(int nod, int papa = 0) {
	int heavySon = -1, sumdp = 0;

	for(auto it: graph[nod])
		if(it != papa && (heavySon == -1 || (heavySon != -1 && subarb[it] > subarb[heavySon])))
			heavySon = it;
	
	for(auto it: graph[nod])
		if(it != papa && it != heavySon) {
			dfs(it, nod);
			node[it].reset();
			sumdp += dp[it];
		}
	
	if(heavySon != -1) {
		dfs(heavySon, nod);
		sumdp += dp[heavySon];

		node[nod].chains.swap(node[heavySon].chains);

		for(auto it: graph[nod])
			if(it != papa && it != heavySon) {
				for(auto x: node[it].chains) {
					int nodch, costch;
					nodch = x.first;
					costch = x.second;

					if(NodeCell::findNode(nodch)) { // Trebuie sa sterg lantul
						dp[nod] = max(dp[nod], costch + NodeCell::getVal(nodch) + sumdp + cost[nodch]);
						NodeCell::eraseNode(nodch);
					} else
						NodeCell::insertNode(nodch, costch);

					node[nod].chains.push_back(x);
				}
			}
	}

	for(auto it: chainstart[nod]) {
		if(NodeCell::findNode(it)) {
			dp[nod] = max(dp[nod], NodeCell::getVal(it) + sumdp + cost[it]);
			NodeCell::eraseNode(it);
		} else {
			NodeCell::insertNode(it, 0);
			node[nod].chains.push_back(make_pair(it, 0));
		}
	}

	dp[nod] = max(dp[nod], sumdp);
	NodeCell::addVal(sumdp - dp[nod]);
}

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = stdin;
	FILE *fout = stdout;
#endif

	int N, M;

	fscanf(fin, "%d", &N);
	for(int i = 0; i < N - 1; ++i) {
		int a, b;
		fscanf(fin, "%d%d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	fscanf(fin, "%d", &M);
	for(int i = 0; i < M; ++i) {
		int a, b, c;
		fscanf(fin, "%d%d%d", &a, &b, &c);
		chainstart[a].push_back(i);
		chainstart[b].push_back(i);
		cost[i] = c;
	}
	calcSubarb(1);
	
	NodeCell::init();
	dfs(1);
	
	fprintf(fout, "%d", dp[1]);

	fclose(fin);
	fclose(fout);
	return 0;
}

Compilation message (stderr)

election_campaign.cpp: In member function 'void NodeCell::reset()':
election_campaign.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < chains.size(); ++i) {
                  ~~^~~~~~~~~~~~~~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:131:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d", &N);
  ~~~~~~^~~~~~~~~~~~~~~
election_campaign.cpp:134:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d%d", &a, &b);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:139:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d", &M);
  ~~~~~~^~~~~~~~~~~~~~~
election_campaign.cpp:142:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d%d%d", &a, &b, &c);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40