oj.uz

Submission #25464

# Submission time Handle Problem Language Result Execution time Memory
25464 2017-06-22T09:29:33 Z dotorya Election Campaign (JOI15_election_campaign) C++14
10 / 100
 449 ms 66056 KB 
#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;
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 - toff, Mx[np][-1] = u - toff;
	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 - toff;
		}
	}
}
int main() {
	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);
	}
	for (i = 0; i < 20; i++) par[1][i] = 1;
	DFS1(1);

	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(1);
	return !printf("%lld\n", Mx[pos[1]][-1] + off[1]);
}

Compilation message

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:136: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:147:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
election_campaign.cpp:149: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:156:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
election_campaign.cpp:158: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24796 KB Output is correct
2 Correct 9 ms 24796 KB Output is correct
3 Correct 3 ms 24796 KB Output is correct
4 Incorrect 0 ms 25060 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24796 KB Output is correct
2 Correct 0 ms 24796 KB Output is correct
3 Correct 0 ms 24960 KB Output is correct
4 Correct 446 ms 54924 KB Output is correct
5 Correct 423 ms 54916 KB Output is correct
6 Correct 369 ms 54932 KB Output is correct
7 Correct 386 ms 54924 KB Output is correct
8 Correct 343 ms 54924 KB Output is correct
9 Correct 343 ms 54940 KB Output is correct
10 Correct 359 ms 54920 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24796 KB Output is correct
2 Correct 0 ms 24796 KB Output is correct
3 Correct 0 ms 24960 KB Output is correct
4 Correct 446 ms 54924 KB Output is correct
5 Correct 423 ms 54916 KB Output is correct
6 Correct 369 ms 54932 KB Output is correct
7 Correct 386 ms 54924 KB Output is correct
8 Correct 343 ms 54924 KB Output is correct
9 Correct 343 ms 54940 KB Output is correct
10 Correct 359 ms 54920 KB Output is correct
11 Correct 23 ms 25096 KB Output is correct
12 Correct 389 ms 54920 KB Output is correct
13 Correct 406 ms 54920 KB Output is correct
14 Correct 366 ms 54940 KB Output is correct
15 Correct 403 ms 54920 KB Output is correct
16 Correct 299 ms 54944 KB Output is correct
17 Correct 426 ms 54924 KB Output is correct
18 Correct 403 ms 54924 KB Output is correct
19 Correct 363 ms 54940 KB Output is correct
20 Correct 449 ms 54920 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 389 ms 66056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24796 KB Output is correct
2 Correct 9 ms 24796 KB Output is correct
3 Correct 3 ms 24796 KB Output is correct
4 Incorrect 0 ms 25060 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24796 KB Output is correct
2 Correct 9 ms 24796 KB Output is correct
3 Correct 3 ms 24796 KB Output is correct
4 Incorrect 0 ms 25060 KB Output isn't correct
5 Halted 0 ms 0 KB -