oj.uz

Submission #25468

# Submission time Handle Problem Language Result Execution time Memory
25468 2017-06-22T09:43:57 Z dotorya Election Campaign (JOI15_election_campaign) C++14
20 / 100
 486 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 - 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] + off[pos[n2]];
		for (auto it : Mx[pos[n2]]) {
			if (it.first == -1) continue;
			Mx[np][it.first] = v + it.second - off[np];
		}
	}
}
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[pos[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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24796 KB Output is correct
2 Correct 0 ms 24796 KB Output is correct
3 Correct 6 ms 24796 KB Output is correct
4 Correct 6 ms 25060 KB Output is correct
5 Correct 299 ms 64376 KB Output is correct
6 Correct 149 ms 53864 KB Output is correct
7 Correct 229 ms 51372 KB Output is correct
8 Correct 243 ms 51500 KB Output is correct
9 Correct 196 ms 50256 KB Output is correct
10 Correct 219 ms 52132 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24796 KB Output is correct
2 Correct 6 ms 24796 KB Output is correct
3 Correct 3 ms 24956 KB Output is correct
4 Correct 419 ms 54920 KB Output is correct
5 Correct 433 ms 54920 KB Output is correct
6 Correct 313 ms 54936 KB Output is correct
7 Correct 309 ms 54920 KB Output is correct
8 Correct 386 ms 54916 KB Output is correct
9 Correct 339 ms 54936 KB Output is correct
10 Correct 439 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 6 ms 24796 KB Output is correct
3 Correct 3 ms 24956 KB Output is correct
4 Correct 419 ms 54920 KB Output is correct
5 Correct 433 ms 54920 KB Output is correct
6 Correct 313 ms 54936 KB Output is correct
7 Correct 309 ms 54920 KB Output is correct
8 Correct 386 ms 54916 KB Output is correct
9 Correct 339 ms 54936 KB Output is correct
10 Correct 439 ms 54920 KB Output is correct
11 Correct 29 ms 25088 KB Output is correct
12 Correct 453 ms 54916 KB Output is correct
13 Correct 433 ms 54924 KB Output is correct
14 Correct 356 ms 54940 KB Output is correct
15 Correct 376 ms 54920 KB Output is correct
16 Correct 309 ms 54940 KB Output is correct
17 Correct 386 ms 54920 KB Output is correct
18 Correct 419 ms 54916 KB Output is correct
19 Correct 343 ms 54944 KB Output is correct
20 Correct 416 ms 54924 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 486 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 0 ms 24796 KB Output is correct
3 Correct 6 ms 24796 KB Output is correct
4 Correct 6 ms 25060 KB Output is correct
5 Correct 299 ms 64376 KB Output is correct
6 Correct 149 ms 53864 KB Output is correct
7 Correct 229 ms 51372 KB Output is correct
8 Correct 243 ms 51500 KB Output is correct
9 Correct 196 ms 50256 KB Output is correct
10 Correct 219 ms 52132 KB Output is correct
11 Incorrect 6 ms 25060 KB Output isn't correct
12 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 0 ms 24796 KB Output is correct
3 Correct 6 ms 24796 KB Output is correct
4 Correct 6 ms 25060 KB Output is correct
5 Correct 299 ms 64376 KB Output is correct
6 Correct 149 ms 53864 KB Output is correct
7 Correct 229 ms 51372 KB Output is correct
8 Correct 243 ms 51500 KB Output is correct
9 Correct 196 ms 50256 KB Output is correct
10 Correct 219 ms 52132 KB Output is correct
11 Correct 3 ms 24796 KB Output is correct
12 Correct 6 ms 24796 KB Output is correct
13 Correct 3 ms 24956 KB Output is correct
14 Correct 419 ms 54920 KB Output is correct
15 Correct 433 ms 54920 KB Output is correct
16 Correct 313 ms 54936 KB Output is correct
17 Correct 309 ms 54920 KB Output is correct
18 Correct 386 ms 54916 KB Output is correct
19 Correct 339 ms 54936 KB Output is correct
20 Correct 439 ms 54920 KB Output is correct
21 Correct 29 ms 25088 KB Output is correct
22 Correct 453 ms 54916 KB Output is correct
23 Correct 433 ms 54924 KB Output is correct
24 Correct 356 ms 54940 KB Output is correct
25 Correct 376 ms 54920 KB Output is correct
26 Correct 309 ms 54940 KB Output is correct
27 Correct 386 ms 54920 KB Output is correct
28 Correct 419 ms 54916 KB Output is correct
29 Correct 343 ms 54944 KB Output is correct
30 Correct 416 ms 54924 KB Output is correct
31 Incorrect 486 ms 66056 KB Output isn't correct
32 Halted 0 ms 0 KB -