Submission #25472

#	Time	Username	Problem	Language	Result	Execution time	Memory
25472		dotorya	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	676 ms	66452 KiB

election_campaign

#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 15;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

vector <int> conn[100050];
vector <int> son[100050];
int par[100050][20];
int sz[100050];
int dep[100050];
bool dchk[100050];
void DFS1(int n) {
	dchk[n] = true;
	sz[n] = 1;
	for (auto it : conn[n]) {
		if (dchk[it]) continue;
		dep[it] = dep[n] + 1;
		par[it][0] = n;
		for (int i = 1; i < 20; i++) par[it][i] = par[par[it][i - 1]][i - 1];
		DFS1(it);
		son[n].push_back(it);
		sz[n] += sz[it];
	}
}
int upnode(int n, int c) {
	for (int i = 18; i >= 0; i--) if (c & (1 << i)) n = par[n][i];
	return n;
}
int lca(int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);
	b = upnode(b, dep[b] - dep[a]);
	if (a == b) return a;
	for (int i = 19; i >= 0; i--) {
		if (par[a][i] != par[b][i]) {
			a = par[a][i];
			b = par[b][i];
		}
	}
	return par[a][0];
}

vector <int> Vq[100050];
int Qu[100050][3];
map <int, ll> Mx[100050];
ll off[100050];
int pos[100050];
int pc = 0;

vector <ll> Vu;

set <pll> Sx;
void DFS2(int n) {
	if (son[n].empty()) {
		pos[n] = ++pc;
		Mx[pc][n] = Mx[pc][-1] = 0;
		return;
	}
	for (auto it : son[n]) DFS2(it);

	sort(all(son[n]), [](int a, int b) {
		return sz[a] > sz[b];
	});
	
	ll sum = 0;
	for (auto it : son[n]) {
		Vu.push_back(Mx[pos[it]][-1] + off[pos[it]]);
		sum += Vu.back();
	}

	ll toff = sum - (Mx[pos[son[n][0]]][-1] + off[pos[son[n][0]]]);

	ll u = sum;
	for (auto it : Vq[n]) {
		int n1 = Qu[it][0], n2 = Qu[it][1];
		if (n2 == n) swap(n1, n2);

		ll v = sum;
		if (n1 != n) {
			int p1 = upnode(n1, dep[n1] - dep[n] - 1);
			v += Mx[pos[p1]][n1] - Mx[pos[p1]][-1];
		}
		int p2 = upnode(n2, dep[n2] - dep[n] - 1);
		v += Mx[pos[p2]][n2] - Mx[pos[p2]][-1];
		v += Qu[it][2];
		u = max(u, v);
	}
	pos[n] = pos[son[n][0]];
	int np = pos[n];
	off[np] += toff;
	Mx[np][n] = sum - off[np], Mx[np][-1] = u - off[np];
	for (int i = 1; i < son[n].size(); i++) {
		int n2 = son[n][i];
		ll v = sum - Mx[pos[n2]][-1];
		for (auto it : Mx[pos[n2]]) {
			if (it.first == -1) continue;
			Mx[np][it.first] = v + it.second - off[np];
		}
	}
}
int main() {
	srand(time(0));
	int N, Q, i, t1, t2;
	scanf("%d", &N);
	for (i = 1; i < N; i++) {
		scanf("%d %d", &t1, &t2);
		conn[t1].push_back(t2);
		conn[t2].push_back(t1);
	}

	int x = rand() % N + 1;
	for (i = 0; i < 20; i++) par[x][i] = x;
	DFS1(x);

	scanf("%d", &Q);
	for (i = 1; i <= Q; i++) {
		scanf("%d %d %d", &Qu[i][0], &Qu[i][1], &Qu[i][2]);
		Vq[lca(Qu[i][0], Qu[i][1])].push_back(i);
	}
	DFS2(x);
	return !printf("%lld\n", Mx[pos[x]][-1] + off[pos[x]]);
}

Compilation message (stderr)

election_campaign.cpp:23:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)  
 ^
election_campaign.cpp:24:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:336777216")  
 ^
election_campaign.cpp: In function 'void DFS2(int)':
election_campaign.cpp:138:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < son[n].size(); i++) {
                    ^
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:150:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
election_campaign.cpp:152:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &t1, &t2);
                           ^
election_campaign.cpp:161:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
election_campaign.cpp:163:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &Qu[i][0], &Qu[i][1], &Qu[i][2]);
                                                     ^

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