oj.uz

Submission #363746

# Submission time Handle Problem Language Result Execution time Memory
363746 2021-02-07T07:39:51 Z Bill_00 Election Campaign (JOI15_election_campaign) C++14
10 / 100
 660 ms 32512 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 x:path[node]){
		int a=x.x;
		int b=x.y;
		int c=x.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 4 ms 5228 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 5100 KB Output is correct
3 Correct 5 ms 5376 KB Output is correct
4 Correct 158 ms 32108 KB Output is correct
5 Correct 155 ms 32236 KB Output is correct
6 Correct 153 ms 32108 KB Output is correct
7 Correct 163 ms 32128 KB Output is correct
8 Correct 157 ms 32236 KB Output is correct
9 Correct 158 ms 32108 KB Output is correct
10 Correct 153 ms 31980 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 5100 KB Output is correct
3 Correct 5 ms 5376 KB Output is correct
4 Correct 158 ms 32108 KB Output is correct
5 Correct 155 ms 32236 KB Output is correct
6 Correct 153 ms 32108 KB Output is correct
7 Correct 163 ms 32128 KB Output is correct
8 Correct 157 ms 32236 KB Output is correct
9 Correct 158 ms 32108 KB Output is correct
10 Correct 153 ms 31980 KB Output is correct
11 Correct 17 ms 6124 KB Output is correct
12 Correct 168 ms 32492 KB Output is correct
13 Correct 200 ms 32364 KB Output is correct
14 Correct 151 ms 32364 KB Output is correct
15 Correct 157 ms 32364 KB Output is correct
16 Correct 153 ms 32364 KB Output is correct
17 Correct 174 ms 32364 KB Output is correct
18 Correct 162 ms 32492 KB Output is correct
19 Correct 148 ms 32512 KB Output is correct
20 Correct 157 ms 32364 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 660 ms 23976 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 4 ms 5228 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 4 ms 5228 KB Output isn't correct
5 Halted 0 ms 0 KB -