oj.uz

Submission #363782

# Submission time Handle Problem Language Result Execution time Memory
363782 2021-02-07T09:14:36 Z Bill_00 Election Campaign (JOI15_election_campaign) C++14
20 / 100
 1000 ms 28780 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]=out[node];
	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]);
		while(a!=node){
			c+=out[a];
			c-=in[a];
			a=up[a][0];
		}
		while(b!=node){
			c+=out[b];
			c-=in[b];
			b=up[b][0];
		}
		c+=out[node];
		in[node]=max(in[node],c);
	}
	// 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
10.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 5 ms 5100 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 133 ms 18924 KB Output is correct
6 Correct 60 ms 26604 KB Output is correct
7 Correct 124 ms 23916 KB Output is correct
8 Correct 75 ms 18924 KB Output is correct
9 Correct 140 ms 22252 KB Output is correct
10 Correct 108 ms 20076 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5356 KB Output is correct
4 Execution timed out 1094 ms 28780 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5356 KB Output is correct
4 Execution timed out 1094 ms 28780 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 20388 KB Output is correct
2 Execution timed out 1082 ms 28652 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.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 5 ms 5100 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 133 ms 18924 KB Output is correct
6 Correct 60 ms 26604 KB Output is correct
7 Correct 124 ms 23916 KB Output is correct
8 Correct 75 ms 18924 KB Output is correct
9 Correct 140 ms 22252 KB Output is correct
10 Correct 108 ms 20076 KB Output is correct
11 Correct 6 ms 5228 KB Output is correct
12 Correct 6 ms 5356 KB Output is correct
13 Correct 6 ms 5356 KB Output is correct
14 Correct 5 ms 5228 KB Output is correct
15 Correct 5 ms 5228 KB Output is correct
16 Correct 5 ms 5228 KB Output is correct
17 Correct 5 ms 5228 KB Output is correct
18 Correct 6 ms 5356 KB Output is correct
19 Correct 5 ms 5228 KB Output is correct
20 Correct 7 ms 5356 KB Output is correct

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 5 ms 5100 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 133 ms 18924 KB Output is correct
6 Correct 60 ms 26604 KB Output is correct
7 Correct 124 ms 23916 KB Output is correct
8 Correct 75 ms 18924 KB Output is correct
9 Correct 140 ms 22252 KB Output is correct
10 Correct 108 ms 20076 KB Output is correct
11 Correct 5 ms 5100 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 4 ms 5356 KB Output is correct
14 Execution timed out 1094 ms 28780 KB Time limit exceeded
15 Halted 0 ms 0 KB -