oj.uz

Submission #297596

# Submission time Handle Problem Language Result Execution time Memory
297596 2020-09-11T16:13:31 Z limabeans Election Campaign (JOI15_election_campaign) C++17
0 / 100
 1000 ms 138580 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) {
    for (int to: leaves[at]) {
	dfs(to);
	dp0[at] += max(dp0[to], dp1[to]);
    }
    int lcount = leaves[at].size();
    dp[at].resize(lcount);

    // ith leaf is banned
    for (int i=0; i<lcount; i++) {
	for (int j=0; j<lcount; j++) {
	    if (i == j) continue;
	    int to = leaves[at][j];
	    dp[at][i] += max(dp0[to], dp1[to]);
	}
    }


    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];
	
	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 94296 KB Output is correct
2 Correct 63 ms 94304 KB Output is correct
3 Correct 67 ms 94328 KB Output is correct
4 Correct 73 ms 94584 KB Output is correct
5 Correct 206 ms 111480 KB Output is correct
6 Correct 151 ms 135072 KB Output is correct
7 Correct 255 ms 126024 KB Output is correct
8 Execution timed out 1100 ms 108408 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 94328 KB Output is correct
2 Correct 64 ms 94328 KB Output is correct
3 Correct 66 ms 94712 KB Output is correct
4 Execution timed out 1088 ms 138028 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 94328 KB Output is correct
2 Correct 64 ms 94328 KB Output is correct
3 Correct 66 ms 94712 KB Output is correct
4 Execution timed out 1088 ms 138028 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 112996 KB Output is correct
2 Execution timed out 1062 ms 138580 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 94296 KB Output is correct
2 Correct 63 ms 94304 KB Output is correct
3 Correct 67 ms 94328 KB Output is correct
4 Correct 73 ms 94584 KB Output is correct
5 Correct 206 ms 111480 KB Output is correct
6 Correct 151 ms 135072 KB Output is correct
7 Correct 255 ms 126024 KB Output is correct
8 Execution timed out 1100 ms 108408 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 94296 KB Output is correct
2 Correct 63 ms 94304 KB Output is correct
3 Correct 67 ms 94328 KB Output is correct
4 Correct 73 ms 94584 KB Output is correct
5 Correct 206 ms 111480 KB Output is correct
6 Correct 151 ms 135072 KB Output is correct
7 Correct 255 ms 126024 KB Output is correct
8 Execution timed out 1100 ms 108408 KB Time limit exceeded
9 Halted 0 ms 0 KB -