oj.uz

Submission #297603

# Submission time Handle Problem Language Result Execution time Memory
297603 2020-09-11T16:19:00 Z limabeans Election Campaign (JOI15_election_campaign) C++17
20 / 100
 1000 ms 139356 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
const int LOG = 20;

int n, m;
vector<int> g[maxn];
int dep[maxn];
int par[maxn][LOG+1];
vector<int> leaves[maxn];
ll dp0[maxn]; // no path goes direct thru me
ll dp1[maxn]; // path goes directly thru me
vector<ll> dp[maxn]; // no path thru me, and no path thru ith leaf


void gen(int at, int p) {
    for (int j=1; j<LOG; j++) {
	par[at][j] = par[par[at][j-1]][j-1];
    }
    for (int to: g[at]) {
	if (to==p) continue;
	leaves[at].push_back(to);
	par[to][0]=at;
	dep[to]=1+dep[at];
	gen(to,at);
    }
}

int lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x,y);
    int dx=dep[x]-dep[y];
    for (int j=0; j<LOG; j++) {
	if (dx>>j&1) {
	    x=par[x][j];
	}
    }
    if (x==y) return x;

    for (int j=LOG-1; j>=0; j--) {
	if (par[x][j] != par[y][j]) {
	    x=par[x][j];
	    y=par[y][j];
	}
    }

    return par[x][0];    
}

int a[maxn], b[maxn];
ll c[maxn];
vector<int> qu[maxn];


void procQuery(int i) {
    int from = a[i];
    int to = b[i];

    int mid = lca(from, to);
    qu[mid].push_back(i);
}


void dfs(int at) {

    vector<ll> pre;
    for (int to: leaves[at]) {
	dfs(to);
	ll tmp = max(dp0[to], dp1[to]);
	pre.push_back(tmp);
	dp0[at] += tmp;
    }
    int lcount = leaves[at].size();
    for (int i=1; i<lcount; i++) {
	pre[i] += pre[i-1];
    }

    auto qry = [&](int l, int r) {
	if (l>r) return 0ll;
	return pre[r] - (l>0 ? pre[l-1] : 0ll);
    };
    
    dp[at].resize(lcount);

    // ith leaf is banned
    for (int i=0; i<lcount; i++) {
	dp[at][i] = qry(0,i-1) + qry(i+1, lcount-1);
    }


    for (int qi: qu[at]) {
	vector<vector<int>> paths;
	// get paths a->at and at<-b
	for (int nd: {a[qi],b[qi]}) {
	    if (nd==at) continue;
	    vector<int> path = {nd};
	    while (par[nd][0] != at) {
		nd=par[nd][0];
		path.push_back(nd);
	    }
	    reverse(path.begin(), path.end());
	    paths.push_back(path);
	}
	ll cur = c[qi];

	assert(int(paths.size()) <= 2);
	
	for (int to: leaves[at]) {
	    int id=-1;
	    for (int j=0; j<int(paths.size()); j++) {
		if (paths[j].front() == to) {
		    id = j;
		}
	    }

	    // at->to->...a
	    if (~id) {
		auto &p = paths[id];
		int plen = p.size();
		for (int j=0; j<plen; j++) {
		    if (j==plen-1) {
			int end = p[j];
			cur += dp0[end];
		    } else {
			int nid=0;
			while (leaves[p[j]][nid] != p[j+1]) nid++;
			cur += dp[p[j]][nid];
		    }
		}
	    } else {
		cur += max(dp0[to],dp1[to]);
	    }
	}

	dp1[at] = max(dp1[at], cur);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    for (int i=0; i<n-1; i++) {
	int u,v;
	cin>>u>>v;
	--u; --v;
	g[u].push_back(v);
	g[v].push_back(u);
    }

    gen(0,0);

    cin>>m;
    for (int i=0; i<m; i++) {
	cin>>a[i]>>b[i]>>c[i];
	--a[i];
	--b[i];
	procQuery(i);
    }


    dfs(0);
    ll res = max(dp0[0], dp1[0]);
    cout<<res<<endl;    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 94328 KB Output is correct
2 Correct 64 ms 94328 KB Output is correct
3 Correct 72 ms 94328 KB Output is correct
4 Correct 68 ms 94460 KB Output is correct
5 Correct 196 ms 110328 KB Output is correct
6 Correct 157 ms 136824 KB Output is correct
7 Correct 250 ms 127036 KB Output is correct
8 Correct 134 ms 107944 KB Output is correct
9 Correct 297 ms 123848 KB Output is correct
10 Correct 138 ms 109096 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 94328 KB Output is correct
2 Correct 66 ms 94332 KB Output is correct
3 Correct 65 ms 94712 KB Output is correct
4 Execution timed out 1054 ms 138888 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 94328 KB Output is correct
2 Correct 66 ms 94332 KB Output is correct
3 Correct 65 ms 94712 KB Output is correct
4 Execution timed out 1054 ms 138888 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 113140 KB Output is correct
2 Execution timed out 1056 ms 139356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 94328 KB Output is correct
2 Correct 64 ms 94328 KB Output is correct
3 Correct 72 ms 94328 KB Output is correct
4 Correct 68 ms 94460 KB Output is correct
5 Correct 196 ms 110328 KB Output is correct
6 Correct 157 ms 136824 KB Output is correct
7 Correct 250 ms 127036 KB Output is correct
8 Correct 134 ms 107944 KB Output is correct
9 Correct 297 ms 123848 KB Output is correct
10 Correct 138 ms 109096 KB Output is correct
11 Correct 66 ms 94456 KB Output is correct
12 Correct 70 ms 94840 KB Output is correct
13 Correct 66 ms 94712 KB Output is correct
14 Correct 67 ms 94456 KB Output is correct
15 Correct 67 ms 94456 KB Output is correct
16 Correct 69 ms 94584 KB Output is correct
17 Correct 67 ms 94456 KB Output is correct
18 Correct 71 ms 94712 KB Output is correct
19 Correct 65 ms 94456 KB Output is correct
20 Correct 74 ms 94840 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 94328 KB Output is correct
2 Correct 64 ms 94328 KB Output is correct
3 Correct 72 ms 94328 KB Output is correct
4 Correct 68 ms 94460 KB Output is correct
5 Correct 196 ms 110328 KB Output is correct
6 Correct 157 ms 136824 KB Output is correct
7 Correct 250 ms 127036 KB Output is correct
8 Correct 134 ms 107944 KB Output is correct
9 Correct 297 ms 123848 KB Output is correct
10 Correct 138 ms 109096 KB Output is correct
11 Correct 65 ms 94328 KB Output is correct
12 Correct 66 ms 94332 KB Output is correct
13 Correct 65 ms 94712 KB Output is correct
14 Execution timed out 1054 ms 138888 KB Time limit exceeded
15 Halted 0 ms 0 KB -