oj.uz

Submission #25471

# Submission time Handle Problem Language Result Execution time Memory
25471 2017-06-22T09:51:51 Z dotorya Election Campaign (JOI15_election_campaign) C++14
20 / 100
 569 ms 64144 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;

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] + 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() {
	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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24796 KB Output is correct
2 Correct 3 ms 24796 KB Output is correct
3 Correct 0 ms 24796 KB Output is correct
4 Correct 3 ms 25060 KB Output is correct
5 Correct 303 ms 63972 KB Output is correct
6 Correct 139 ms 49484 KB Output is correct
7 Correct 296 ms 50184 KB Output is correct
8 Correct 213 ms 52140 KB Output is correct
9 Correct 283 ms 50248 KB Output is correct
10 Correct 246 ms 52672 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24796 KB Output is correct
2 Correct 3 ms 24796 KB Output is correct
3 Correct 3 ms 24956 KB Output is correct
4 Correct 399 ms 52952 KB Output is correct
5 Correct 339 ms 53896 KB Output is correct
6 Correct 273 ms 53924 KB Output is correct
7 Correct 309 ms 53896 KB Output is correct
8 Correct 366 ms 50956 KB Output is correct
9 Correct 316 ms 50980 KB Output is correct
10 Correct 309 ms 53092 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 24796 KB Output is correct
2 Correct 3 ms 24796 KB Output is correct
3 Correct 3 ms 24956 KB Output is correct
4 Correct 399 ms 52952 KB Output is correct
5 Correct 339 ms 53896 KB Output is correct
6 Correct 273 ms 53924 KB Output is correct
7 Correct 309 ms 53896 KB Output is correct
8 Correct 366 ms 50956 KB Output is correct
9 Correct 316 ms 50980 KB Output is correct
10 Correct 309 ms 53092 KB Output is correct
11 Correct 36 ms 25096 KB Output is correct
12 Correct 233 ms 53096 KB Output is correct
13 Correct 383 ms 51816 KB Output is correct
14 Correct 309 ms 51968 KB Output is correct
15 Correct 326 ms 52924 KB Output is correct
16 Correct 256 ms 52948 KB Output is correct
17 Correct 313 ms 52796 KB Output is correct
18 Correct 393 ms 52480 KB Output is correct
19 Correct 339 ms 52628 KB Output is correct
20 Correct 366 ms 52664 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24796 KB Output is correct
2 Correct 3 ms 24796 KB Output is correct
3 Correct 0 ms 24796 KB Output is correct
4 Correct 3 ms 25060 KB Output is correct
5 Correct 303 ms 63972 KB Output is correct
6 Correct 139 ms 49484 KB Output is correct
7 Correct 296 ms 50184 KB Output is correct
8 Correct 213 ms 52140 KB Output is correct
9 Correct 283 ms 50248 KB Output is correct
10 Correct 246 ms 52672 KB Output is correct
11 Incorrect 3 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 6 ms 24796 KB Output is correct
2 Correct 3 ms 24796 KB Output is correct
3 Correct 0 ms 24796 KB Output is correct
4 Correct 3 ms 25060 KB Output is correct
5 Correct 303 ms 63972 KB Output is correct
6 Correct 139 ms 49484 KB Output is correct
7 Correct 296 ms 50184 KB Output is correct
8 Correct 213 ms 52140 KB Output is correct
9 Correct 283 ms 50248 KB Output is correct
10 Correct 246 ms 52672 KB Output is correct
11 Correct 0 ms 24796 KB Output is correct
12 Correct 3 ms 24796 KB Output is correct
13 Correct 3 ms 24956 KB Output is correct
14 Correct 399 ms 52952 KB Output is correct
15 Correct 339 ms 53896 KB Output is correct
16 Correct 273 ms 53924 KB Output is correct
17 Correct 309 ms 53896 KB Output is correct
18 Correct 366 ms 50956 KB Output is correct
19 Correct 316 ms 50980 KB Output is correct
20 Correct 309 ms 53092 KB Output is correct
21 Correct 36 ms 25096 KB Output is correct
22 Correct 233 ms 53096 KB Output is correct
23 Correct 383 ms 51816 KB Output is correct
24 Correct 309 ms 51968 KB Output is correct
25 Correct 326 ms 52924 KB Output is correct
26 Correct 256 ms 52948 KB Output is correct
27 Correct 313 ms 52796 KB Output is correct
28 Correct 393 ms 52480 KB Output is correct
29 Correct 339 ms 52628 KB Output is correct
30 Correct 366 ms 52664 KB Output is correct
31 Incorrect 569 ms 64144 KB Output isn't correct
32 Halted 0 ms 0 KB -