oj.uz

Submission #297617

# Submission time Handle Problem Language Result Execution time Memory
297617 2020-09-11T16:33:05 Z limabeans Election Campaign (JOI15_election_campaign) C++17
30 / 100
 1000 ms 155128 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;
const ll inf = 1e18;

struct MaxLazySegmentTree {
    vector<ll> t, o;
    void init(int n) {
	n += 10;
	t.resize(4*n);
	o.resize(4*n);
    }
    
    void push(int v) {
	t[2*v]+=o[v];
	t[2*v+1]+=o[v];
	o[2*v]+=o[v];
	o[2*v+1]+=o[v];
	o[v]=0;
    }
 
    ll queryMax(int v, int tl, int tr, int l, int r) {
	if (l>tr||r<tl) return -inf;
	if (l<=tl&&tr<=r) {
	    return t[v];
	} else {
	    push(v);
	    int tm=(tl+tr)/2;
	    return max(queryMax(2*v,tl,tm,l,r),queryMax(2*v+1,tm+1,tr,l,r));
	}
    }
 
    void rangeAdd(int v, int tl, int tr, int l, int r, ll dx) {
	if (l>r) return;
	if (l>tr||r<tl) return;
	if (l<=tl&&tr<=r) {
	    t[v]+=dx;
	    o[v]+=dx;
	} else {
	    push(v);
	    int tm=(tl+tr)/2;
	    rangeAdd(2*v,tl,tm,l,r,dx);
	    rangeAdd(2*v+1,tm+1,tr,l,r,dx);
	    t[v]=max(t[2*v],t[2*v+1]);
	}
    }
};

vector<int> ev[maxn];

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);
    }
}


ll solveTask23() {
    //cerr<<"solveTask23"<<endl;
    MaxLazySegmentTree dp;
    dp.init(n+10);
 
    auto qry = [&](int i) {
	if (i==0) return 0ll;
	return dp.queryMax(1,1,n,1,i);
    };
 
    auto upd = [&](int i, ll val) {
	ll cur = dp.queryMax(1,1,n,i,i);
	if (val <= cur) return;
	ll dx = val-cur;
	dp.rangeAdd(1,1,n,i,i,dx);
    };
 
 
    for (int i=1; i<=n; i++) {
	for (int idx: ev[i]) {
	    int l = a[idx];
	    int r = b[idx];
	    int val = c[idx];
	    upd(r, val+qry(l-1));
	}
    }
    return qry(n);
}

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

    cin>>n;
    bool line = true;
    for (int i=1; i<=n-1; i++) {
	int u,v;
	cin>>u>>v;
	line &= (u==i && v==i+1);
	--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];
	if (line) {
	    ev[b[i]].push_back(i);
	    if (a[i]>b[i]) swap(a[i],b[i]);
	} else {
	    --a[i];
	    --b[i];
	}
	
	procQuery(i);
    }

    if (line) {
	out(solveTask23());
    }


    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 80 ms 117880 KB Output is correct
2 Correct 83 ms 117752 KB Output is correct
3 Correct 79 ms 117752 KB Output is correct
4 Correct 80 ms 118008 KB Output is correct
5 Correct 215 ms 133752 KB Output is correct
6 Correct 148 ms 148472 KB Output is correct
7 Correct 274 ms 150456 KB Output is correct
8 Correct 152 ms 131496 KB Output is correct
9 Correct 308 ms 146404 KB Output is correct
10 Correct 157 ms 131496 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 117752 KB Output is correct
2 Correct 80 ms 117752 KB Output is correct
3 Correct 81 ms 118136 KB Output is correct
4 Correct 313 ms 152184 KB Output is correct
5 Correct 325 ms 154616 KB Output is correct
6 Correct 287 ms 154744 KB Output is correct
7 Correct 339 ms 154744 KB Output is correct
8 Correct 330 ms 154616 KB Output is correct
9 Correct 315 ms 154616 KB Output is correct
10 Correct 312 ms 154616 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 117752 KB Output is correct
2 Correct 80 ms 117752 KB Output is correct
3 Correct 81 ms 118136 KB Output is correct
4 Correct 313 ms 152184 KB Output is correct
5 Correct 325 ms 154616 KB Output is correct
6 Correct 287 ms 154744 KB Output is correct
7 Correct 339 ms 154744 KB Output is correct
8 Correct 330 ms 154616 KB Output is correct
9 Correct 315 ms 154616 KB Output is correct
10 Correct 312 ms 154616 KB Output is correct
11 Correct 102 ms 119032 KB Output is correct
12 Correct 319 ms 154872 KB Output is correct
13 Correct 328 ms 154872 KB Output is correct
14 Correct 301 ms 154896 KB Output is correct
15 Correct 327 ms 154872 KB Output is correct
16 Correct 305 ms 154872 KB Output is correct
17 Correct 350 ms 154872 KB Output is correct
18 Correct 313 ms 154872 KB Output is correct
19 Correct 304 ms 154908 KB Output is correct
20 Correct 343 ms 155128 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 136436 KB Output is correct
2 Correct 308 ms 152312 KB Output is correct
3 Execution timed out 1057 ms 154276 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 117880 KB Output is correct
2 Correct 83 ms 117752 KB Output is correct
3 Correct 79 ms 117752 KB Output is correct
4 Correct 80 ms 118008 KB Output is correct
5 Correct 215 ms 133752 KB Output is correct
6 Correct 148 ms 148472 KB Output is correct
7 Correct 274 ms 150456 KB Output is correct
8 Correct 152 ms 131496 KB Output is correct
9 Correct 308 ms 146404 KB Output is correct
10 Correct 157 ms 131496 KB Output is correct
11 Correct 82 ms 118008 KB Output is correct
12 Correct 80 ms 118136 KB Output is correct
13 Correct 83 ms 118136 KB Output is correct
14 Correct 83 ms 118008 KB Output is correct
15 Correct 82 ms 118136 KB Output is correct
16 Correct 84 ms 118136 KB Output is correct
17 Correct 82 ms 118008 KB Output is correct
18 Correct 85 ms 118136 KB Output is correct
19 Correct 81 ms 118008 KB Output is correct
20 Correct 80 ms 118264 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 117880 KB Output is correct
2 Correct 83 ms 117752 KB Output is correct
3 Correct 79 ms 117752 KB Output is correct
4 Correct 80 ms 118008 KB Output is correct
5 Correct 215 ms 133752 KB Output is correct
6 Correct 148 ms 148472 KB Output is correct
7 Correct 274 ms 150456 KB Output is correct
8 Correct 152 ms 131496 KB Output is correct
9 Correct 308 ms 146404 KB Output is correct
10 Correct 157 ms 131496 KB Output is correct
11 Correct 87 ms 117752 KB Output is correct
12 Correct 80 ms 117752 KB Output is correct
13 Correct 81 ms 118136 KB Output is correct
14 Correct 313 ms 152184 KB Output is correct
15 Correct 325 ms 154616 KB Output is correct
16 Correct 287 ms 154744 KB Output is correct
17 Correct 339 ms 154744 KB Output is correct
18 Correct 330 ms 154616 KB Output is correct
19 Correct 315 ms 154616 KB Output is correct
20 Correct 312 ms 154616 KB Output is correct
21 Correct 102 ms 119032 KB Output is correct
22 Correct 319 ms 154872 KB Output is correct
23 Correct 328 ms 154872 KB Output is correct
24 Correct 301 ms 154896 KB Output is correct
25 Correct 327 ms 154872 KB Output is correct
26 Correct 305 ms 154872 KB Output is correct
27 Correct 350 ms 154872 KB Output is correct
28 Correct 313 ms 154872 KB Output is correct
29 Correct 304 ms 154908 KB Output is correct
30 Correct 343 ms 155128 KB Output is correct
31 Correct 546 ms 136436 KB Output is correct
32 Correct 308 ms 152312 KB Output is correct
33 Execution timed out 1057 ms 154276 KB Time limit exceeded
34 Halted 0 ms 0 KB -