Submission #240646

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
240646	2020-06-20T11:08:19 Z	aggu_01000101	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	180 ms	42468 KB

election_campaign

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define INF 100000000000000000
#define int long long
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define x(p) p.first
#define y(p) p.second
#define MOD 998244353
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
struct plan{
    int A, B, C, lca;
};
const int N = 1e5 + 5;
int n, m;
vector<int> adj[N];
int seg[10*N];
int dep[N];
int ind[N];
int dp[N][2]; //0 -> without including i, 1 -> including i
plan plans[N];
vector<int> ett;
vector<pair<int, int>> children[N];
vector<plan> PlansHere[N];
int merge(int l, int u){
    return (dep[l]<=dep[u]) ? l : u;
}
int build(int l, int u, int i){
    if(l==u) return seg[i] = ett[l];
    else return seg[i] = merge(build(l, mid(l, u), lchild(i)), build(mid(l, u)+1, u, rchild(i)));
}
int query(int l, int u, int i, int ll, int uu){
    //cout<<l<<" "<<u<<" "<<ll<<" "<<uu<<endl;
    if(l>=ll && u<=uu) return seg[i];
    if(uu<=mid(l, u)) return query(l, mid(l, u), lchild(i), ll, uu);
    if(ll>mid(l, u)) return query(mid(l, u)+1, u, rchild(i), ll, uu);
    return merge(query(l, mid(l, u), lchild(i), ll, uu), query(mid(l, u)+1, u, rchild(i), ll, uu));
}
int LCA(int x, int y){
    return query(0, ett.size() - 1, 0, min(ind[x], ind[y]), max(ind[x], ind[y]));
}
void buildLCA(){
    build(0, ett.size()-1, 0);
}
void euler_tour(int i, int p, int d){
    dep[i] = d;
    ind[i] = ett.size();
    ett.push_back(i);
    for(int j: adj[i]){
        if(j==p) continue;
        children[i].push_back({ett.size(), j});
        euler_tour(j, i, d+1);
        ett.push_back(i);
    }
}
int findChild(int i, int j){
    //find the child of i that contains j
    int ans = -1;
    int lo = 0;
    int hi = children[i].size() - 1;
    while(lo<=hi){
        int mid = mid(lo, hi);
        //cout<<lo<<" "<<hi<<"\n";
        //cout<<i<<" "<<j<<" "<<children[i][mid].first<<" "<<ind[j]<<"\n";
        if(children[i][mid].first <= ind[j]){
            //cout<<children[i][mid].second<<"\n";
            ans = max(ans, mid);
            lo = mid + 1;
        }
        else hi = mid - 1;
    }
    //cout<<i<<" is connected to "<<j<<" through "<<(children[i][ans].second)<<endl;
    return children[i][ans].second;
}
int dfs(int i){
    dp[i][0] = 0;
    for(pair<int, int> j: children[i]){
        dp[i][0] += dfs(j.second);
    }
    int maxi = dp[i][0];
    for(plan k: PlansHere[i]){
        int acontr = 0;
        int bcontr = 0;
        int plancontr = k.C;

        if(k.A != i){
            acontr += dp[k.A][0];
            acontr -= dp[findChild(i, k.A)][1];
        }
        if(k.B != i){
            bcontr += dp[k.B][0];
            bcontr -= dp[findChild(i, k.B)][1];
        }
        maxi = max(maxi, dp[i][0] + acontr + bcontr + plancontr);
    }
    dp[i][1] = maxi;
    return dp[i][1];
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i = 1;i<n;i++){
        int x, y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    euler_tour(1, 0, 0);
    buildLCA();
    cin>>m;
    for(int i = 0;i<m;i++){
        cin>>plans[i].A>>plans[i].B>>plans[i].C;
        //cout<<"Done taking input"<<endl;
        plans[i].lca = LCA(plans[i].A, plans[i].B);
        //cout<<"Done calculating LCA"<<endl;
        PlansHere[plans[i].lca].push_back(plans[i]);
        //cout<<"Done pushing back"<<endl;
    }
    cout<<dfs(1)<<"\n";
}
/*
7
3 4
6 5
2 7
1 5
7 5
4 5
5
4 3 10
5 6 5
2 6 9
7 2 2
1 3 8

8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
5
7 5 4
5 8 9
4 3 9
1 3 3
2 8 11

20
17 10
11 4
8 3
3 16
1 14
15 18
5 4
6 18
10 18
19 4
16 7
2 13
4 12
12 20
9 20
18 13
20 14
14 7
13 7
15
19 9 2341
13 8 6974
8 3 3339
15 17 6515
10 13 4370
1 7 8376
18 2 9272
6 7 4595
1 20 505
10 9 308
6 19 8937
2 15 5072
5 4 4217
2 4 4170
19 12 8204
*/

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	7424 KB	Output is correct
2	Correct	8 ms	7424 KB	Output is correct
3	Incorrect	9 ms	7424 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	7424 KB	Output is correct
2	Correct	10 ms	7424 KB	Output is correct
3	Correct	10 ms	7680 KB	Output is correct
4	Correct	147 ms	42084 KB	Output is correct
5	Correct	161 ms	42084 KB	Output is correct
6	Correct	137 ms	42084 KB	Output is correct
7	Correct	148 ms	42084 KB	Output is correct
8	Correct	148 ms	42064 KB	Output is correct
9	Correct	134 ms	42116 KB	Output is correct
10	Correct	164 ms	42084 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	7424 KB	Output is correct
2	Correct	10 ms	7424 KB	Output is correct
3	Correct	10 ms	7680 KB	Output is correct
4	Correct	147 ms	42084 KB	Output is correct
5	Correct	161 ms	42084 KB	Output is correct
6	Correct	137 ms	42084 KB	Output is correct
7	Correct	148 ms	42084 KB	Output is correct
8	Correct	148 ms	42064 KB	Output is correct
9	Correct	134 ms	42116 KB	Output is correct
10	Correct	164 ms	42084 KB	Output is correct
11	Correct	21 ms	9856 KB	Output is correct
12	Correct	146 ms	42340 KB	Output is correct
13	Correct	167 ms	42468 KB	Output is correct
14	Correct	141 ms	42340 KB	Output is correct
15	Correct	148 ms	42448 KB	Output is correct
16	Correct	133 ms	42340 KB	Output is correct
17	Correct	156 ms	42340 KB	Output is correct
18	Correct	151 ms	42340 KB	Output is correct
19	Correct	138 ms	42340 KB	Output is correct
20	Correct	148 ms	42440 KB	Output is correct