oj.uz

Submission #363754

# Submission time Handle Problem Language Result Execution time Memory
363754 2021-02-07T08:14:29 Z Bill_00 Election Campaign (JOI15_election_campaign) C++14
10 / 100
 714 ms 30444 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define N 100001
typedef long long ll;
const long long MOD=1000000007;
using namespace std;
struct plan{
	int x,y,votes;
};

int timer,m,n,l,k,sz[N],h[N],seg[N];
int tin[N],tout[N],up[N][20];
int in[N],out[N],tree[4*N+4];

vector<plan>path[N];
vector<int>adj[N];

void dfs(int node,int par=1){
	tin[node]=++timer;
	up[node][0]=par;
	for(int i=1;i<=l;i++){
		up[node][i]=up[up[node][i-1]][i-1];
	}
	sz[node]=1;
	for(int x:adj[node]){
		if(x!=par){
			dfs(x,node);
			sz[node]+=sz[x];
		} 
	}
	tout[node]=++timer;
}

void dfs1(int node,int par,int head){
	seg[node]=++k;
	h[node]=head;
	pair<int,int>bigchild={0,-1};
	for(int x:adj[node]){
		if(x!=par) bigchild=max(bigchild,{sz[x],x});
	}
	if(bigchild.ss!=-1) dfs1(bigchild.ss,node,head);
	for(int x:adj[node]){
		if(x!=par && x!=bigchild.ss) dfs1(x,node,x);
	}
}

bool is(int a,int b){
	return (tin[a]<=tin[b] && tout[b]<=tout[a]);
}

int lca(int a,int b){
	if(is(a,b)) return a;
	if(is(b,a)) return b;
	for(int i=l;i>=0;i--){
		if(!is(up[a][i],b)) a=up[a][i];
	}
	return up[a][0];
}

int query(int id,int l,int r,int L,int R){
	if(r<L || R<l) return 0;
	if(L<=l && r<=R) return tree[id];
	int m=(l+r)>>1;
	return query(id*2,l,m,L,R)+query(id*2+1,m+1,r,L,R);
}

void update(int id,int l,int r,int x,int val){
	if(l==r){
		tree[id]+=val;
		return;
	}
	int m=(l+r)>>1;
	if(m>=x) update(id*2,l,m,x,val);
	else update(id*2+1,m+1,r,x,val);
	tree[id]=tree[id*2]+tree[id*2+1];
}

int p(int a,int b){
	if(is(h[a],b)) return query(1,1,k,seg[b],seg[a]);
	return query(1,1,k,seg[h[a]],seg[a])+p(up[a][0],b);
}

void solve(int node,int par=1){
	for(int x:adj[node]){
		if(x!=par){
			solve(x,node);
			out[node]+=in[x];
			in[node]=max(in[node],in[x]);
		} 
	}
	for(plan xx:path[node]){
		int a=xx.x;
		int b=xx.y;
		int c=xx.votes;
		in[node]=max(in[node],p(a,node)+p(b,node)+c+out[node]);
	}
	update(1,1,k,seg[node],out[node]-in[node]);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	l=ceil(log2(n));
	for(int i=1;i<n;i++){
		int a,b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}	
	dfs(1);
	dfs1(1,1,1);
	cin >> m;
	while(m--){
		int a,b,c;
		cin >> a >> b >> c;
		int x=lca(a,b);
		path[x].pb({a,b,c});
	}
	solve(1);
	cout << in[1];
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Incorrect 5 ms 5376 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 4 ms 5100 KB Output is correct
2 Correct 4 ms 5248 KB Output is correct
3 Correct 6 ms 5356 KB Output is correct
4 Correct 169 ms 30244 KB Output is correct
5 Correct 158 ms 30444 KB Output is correct
6 Correct 146 ms 30336 KB Output is correct
7 Correct 155 ms 30188 KB Output is correct
8 Correct 163 ms 30188 KB Output is correct
9 Correct 169 ms 30188 KB Output is correct
10 Correct 163 ms 30284 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5248 KB Output is correct
3 Correct 6 ms 5356 KB Output is correct
4 Correct 169 ms 30244 KB Output is correct
5 Correct 158 ms 30444 KB Output is correct
6 Correct 146 ms 30336 KB Output is correct
7 Correct 155 ms 30188 KB Output is correct
8 Correct 163 ms 30188 KB Output is correct
9 Correct 169 ms 30188 KB Output is correct
10 Correct 163 ms 30284 KB Output is correct
11 Correct 17 ms 6124 KB Output is correct
12 Correct 175 ms 30188 KB Output is correct
13 Correct 163 ms 30316 KB Output is correct
14 Correct 173 ms 30316 KB Output is correct
15 Correct 163 ms 30188 KB Output is correct
16 Correct 151 ms 30316 KB Output is correct
17 Correct 160 ms 30188 KB Output is correct
18 Correct 158 ms 30188 KB Output is correct
19 Correct 153 ms 30316 KB Output is correct
20 Correct 172 ms 30188 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 40.0

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