Submission #660811

#	Time	Username	Problem	Language	Result	Execution time	Memory
660811		Danilo21	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	289 ms	51128 KiB

election_campaign

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))

using namespace std;

class Tree{

private:
    int n, root;
    vector<int> depth, in, out;
    vector<vector<int> > g, par;
    int _edges_ = 0;
    bool _initialized_ = 0;

    bool Valid(int s) const { return s >= 0 && s < n; }

    int InitDfs(int s, int p = -1, int d = 0, int t = 0){
        par[s][0] = p;
        depth[s] = d;
        in[s] = t;
        for (int u : g[s])
            if (u^p)
                t = InitDfs(u, s, d+1, t+1);
        return out[s] = ++t;
    }

    void Dfs(int s, int p, void bf(int, int), void af(int, int)) const {
        bf(s, p);
        for (int u : g[s])
            if (u^p)
                Dfs(u, s, bf, af);
        af(s, p);
    }

public:
    Tree(int n = 0){ Assign(n); }

    void Assign(int n = 0){
        this->n = n;
        depth.assign(n, 0);
        in.assign(n, 0);
        out.assign(n, 0);
        g.assign(n, vector<int>());
        par.assign(n, vector<int>(lg(n)+1, -1));
    }

    void Edge(int u, int v){
        if (!Valid(u) || !Valid(v)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        g[u].pb(v);
        g[v].pb(u);
        _edges_++;
    }

    void Read(int d = 1){
        for (int i = 0; i < n-1; i++){
            ri(u); ri(v);
            u -= d; v -= d;
            Edge(u, v);
        }
    }

    void Initialize(int s = 0){
        if (!Valid(s)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        if (_edges_ < n-1){
            cerr << "Tree is not connected" << endl;
            exit(1);
        }
        if (_edges_ > n-1){
            cerr << "Tree has cycle(s)" << endl;
            exit(1);
        }
        root = s;
        InitDfs(s, -1);
        for (int d = 1; d <= lg(n); d++)
            for (int i = 0; i < n; i++)
                if (depth[i] >= (1<<d))
                    par[i][d] = par[par[i][d-1]][d-1];
        _initialized_ = 1;
    }

    int Size() const { return n; }

    int Depth(int s) const {
        if (!Valid(s)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        return depth[s];
    }

    int InTime(int s) const {
        if (!Valid(s)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        return in[s];
    }

    int OutTime(int s) const {
        if (!Valid(s)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        return out[s];
    }

    vector<int> GetAdjecent(int s) const {
        if (!Valid(s)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        return g[s];
    }

    vector<int> GetChilds(int s) const {
        if (!Valid(s)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        vector<int> ch;
        for (int u : g[s])
            if (u^par[s][0])
                ch.pb(u);
        return ch;
    }

    int Par(int s, int d = 1) const {
        if (!_initialized_){
            cerr << "Tree has not been initialized yet" << endl;
            exit(1);
        }
        if (d < 0 || d > depth[s]) return -1;
        if (!d) return s;
        return Par(par[s][lg(d)], d - highpow(d));
    }

    bool Ancestor(int s, int p) const {
        if (!_initialized_){
            cerr << "Tree has not been initialized yet" << endl;
            exit(1);
        }
        return in[s] > in[p] && out[s] < out[p];
    }

    int Lca(int u, int v) const {
        if (!Valid(u) || !Valid(v)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        if (!_initialized_){
            cerr << "Tree has not been initialized yet" << endl;
            exit(1);
        }
        if (depth[u] > depth[v]) swap(u, v);
        if (Ancestor(v, u)) return u;
        v = Par(v, depth[v] - depth[u]);
        for (int d = lg(n); ~d; d--){
            if (par[u][d] != par[v][d]){
                u = par[u][d];
                v = par[v][d];
            }
        }
        return par[u][0];
    }

    int Dist(int u, int v) const {
        if (!Valid(u) || !Valid(v)){
            cerr << "Node index out of range" << endl;
            exit(1);
        }
        if (!_initialized_){
            cerr << "Tree has not been initialized yet" << endl;
            exit(1);
        }
        int lca = Lca(u, v);
        return 2*depth[lca] - depth[u] - depth[v];
    }

    void Dfs(void bf(int, int), void af(int, int)) const { Dfs(root, -1, bf, af); }
};
#define Empty [](int, int){}

class BIT{

    int n;
    vector<ll> tree;
    ll query(int pos) const {
        smin(pos, n);
        ll sum = 0;
        for (; pos; pos -= (pos & (-pos)))
            sum += tree[pos];
        return sum;
    }
public:
    void Assign(int s){ n = s; tree.assign(s+1, 0); }
    ll query(int l, int r) const {
        l++; r++;
        if (l>r) return 0;
        return query(r) - query(l-1);
    }
    void update(int pos, ll x){
        pos++;
        if (pos < 1) return;
        for (; pos <= n; pos += (pos & (-pos)))
            tree[pos] += x;
    }
};

const ll LINF = 4e18;
const int mxN = 1e6+10, INF = 2e9;
ll n, m, a[mxN], dp[mxN];
vector<array<int, 3> > path[mxN];
Tree tree;
BIT fen;

ll sumPath(int p, int s){ return fen.query(tree.InTime(p), tree.InTime(s)); }

void dfsF(int s, int p){

    for (int u : tree.GetChilds(s))
        dp[s] += dp[u];
    for (auto [u, v, w] : path[s]){
        ll cur = sumPath(s, u);
        cur += sumPath(tree.Par(v, tree.Depth(v) - tree.Depth(s) - 1), v);
        smax(dp[s], cur + w);
    }
    fen.update(tree.InTime(s), -dp[s]);
    fen.update(tree.OutTime(s), dp[s]);
    if (~p){
        fen.update(tree.InTime(p), dp[s]);
        fen.update(tree.OutTime(p), -dp[s]);
    }
}

void Solve(){

    cin >> n;
    tree.Assign(n);
    tree.Read();
    tree.Initialize();
    cin >> m;
    for (int i = 0; i < m; i++){
        ri(u); ri(v); rl(w);
        u--; v--;
        int lca = tree.Lca(u, v);
        if (tree.Depth(u) > tree.Depth(v)) swap(u, v);
        path[lca].pb({u, v, w});
    }
    fen.Assign(2*n);
    tree.Dfs(Empty, &dfsF);
    cout << dp[0] << en;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void dfsF(int, int)':
election_campaign.cpp:254:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  254 |     for (auto [u, v, w] : path[s]){
      |               ^
election_campaign.cpp: In function 'void Solve()':
election_campaign.cpp:279:29: warning: narrowing conversion of 'w' from 'long long int' to 'int' [-Wnarrowing]
  279 |         path[lca].pb({u, v, w});
      |                             ^

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40