oj.uz

Submission #485215

# Submission time Handle Problem Language Result Execution time Memory
485215 2021-11-06T15:12:16 Z MilosMilutinovic Election Campaign (JOI15_election_campaign) C++14
10 / 100
 134 ms 34400 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n,m;

vector<int> graf[100005];

int par[100005][20];
int dep[100005];
int disc[100005];
int out[100005];
int t=1;

void dfs(int u, int p){
    disc[u] = t;
    dep[u] = dep[p] + 1;
    par[u][0] = p;
    ff(i,1,19)par[u][i] = par[par[u][i-1]][i-1];
    for(auto c:graf[u]){
        if(c == p)continue;
        t++;
        dfs(c, u);
    }
    t++;
    out[u] = t;
}

struct sta{
    int a,b,c;
};
vector<sta> st[100005];

ll bit[100005];

void upd(int x, int y){
    while(x < 100005){
        bit[x] += y;
        x += (x&(-x));
    }
}

ll get(int x){
    ll ans = 0;
    while(x > 0){
        ans += bit[x];
        x -= (x&(-x));
    }
    return ans;
}

ll get(int l, int r){
    return get(r) - get(l - 1);
}

bool anc(int u, int v){
    return disc[u] <= disc[v] && out[u] >= out[v];
}

int lca(int u, int v){
    if(anc(u, v))return u;
    if(anc(v, u))return v;
    fb(i,19,0)if(par[u][i] != 0 && !anc(par[u][i], v))u = par[u][i];
    return par[u][0];
}

int dist(int u, int v){
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

int lift(int u, int k){
    ff(i,0,19)if(k & (1 << i))u = par[u][i];
    return u;
}

ll dp[100005];

void solve(int u, int p){
    dp[u] = get(disc[u], disc[u]);
    for(auto c:graf[u]){
        if(c == p)continue;
        solve(c, u);
        dp[u] += dp[c];
    }
    for(auto x:st[u]){
        int a = x.a;
        int b = x.b;
        int c = x.c;
        if(anc(b, a))swap(a, b);
        if(a == u){
            dp[u] = max(dp[u], get(disc[u], disc[b]) + c);
        }
        else{
            dp[u] = max(dp[u], get(disc[u], disc[a]) + get(disc[lift(b, dist(b, u) - 1)], disc[b]) + c);
        }
    }
    if(u != 1){
        upd(disc[par[u][0]], dp[u]);
        upd(disc[u], -dp[u]);
        upd(out[u], dp[u]);
        upd(out[par[u][0]], -dp[u]);
    }
}

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

    cin >> n;
    ff(i,1,n-1){
        int x,y;
        cin >> x >> y;
        graf[x].pb(y);
        graf[y].pb(x);
    }
    dfs(1, 0);
    cin >> m;
    ff(i,1,m){
        int a,b,c;
        cin >> a >> b >> c;
        st[lca(a,b)].pb({a,b,c});
    }
    solve(1, 0);
    cout << dp[1];
    return 0;
}

Compilation message

election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
election_campaign.cpp:37:5: note: in expansion of macro 'ff'
   37 |     ff(i,1,19)par[u][i] = par[par[u][i-1]][i-1];
      |     ^~
election_campaign.cpp: In function 'int lca(int, int)':
election_campaign.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
election_campaign.cpp:81:5: note: in expansion of macro 'fb'
   81 |     fb(i,19,0)if(par[u][i] != 0 && !anc(par[u][i], v))u = par[u][i];
      |     ^~
election_campaign.cpp: In function 'int lift(int, int)':
election_campaign.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
election_campaign.cpp:90:5: note: in expansion of macro 'ff'
   90 |     ff(i,0,19)if(k & (1 << i))u = par[u][i];
      |     ^~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
election_campaign.cpp:128:5: note: in expansion of macro 'ff'
  128 |     ff(i,1,n-1){
      |     ^~
election_campaign.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
election_campaign.cpp:136:5: note: in expansion of macro 'ff'
  136 |     ff(i,1,m){
      |     ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 2 ms 5068 KB Output is correct
3 Correct 2 ms 5068 KB Output is correct
4 Correct 3 ms 5196 KB Output is correct
5 Incorrect 91 ms 19908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5020 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 82 ms 34068 KB Output is correct
5 Correct 81 ms 34072 KB Output is correct
6 Correct 79 ms 34084 KB Output is correct
7 Correct 80 ms 34116 KB Output is correct
8 Correct 113 ms 34080 KB Output is correct
9 Correct 76 ms 34080 KB Output is correct
10 Correct 77 ms 34012 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5020 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 82 ms 34068 KB Output is correct
5 Correct 81 ms 34072 KB Output is correct
6 Correct 79 ms 34084 KB Output is correct
7 Correct 80 ms 34116 KB Output is correct
8 Correct 113 ms 34080 KB Output is correct
9 Correct 76 ms 34080 KB Output is correct
10 Correct 77 ms 34012 KB Output is correct
11 Correct 9 ms 6092 KB Output is correct
12 Correct 83 ms 34316 KB Output is correct
13 Correct 84 ms 34348 KB Output is correct
14 Correct 80 ms 34304 KB Output is correct
15 Correct 85 ms 34400 KB Output is correct
16 Correct 85 ms 34364 KB Output is correct
17 Correct 88 ms 34308 KB Output is correct
18 Correct 86 ms 34328 KB Output is correct
19 Correct 86 ms 34340 KB Output is correct
20 Correct 92 ms 34368 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 22744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 2 ms 5068 KB Output is correct
3 Correct 2 ms 5068 KB Output is correct
4 Correct 3 ms 5196 KB Output is correct
5 Incorrect 91 ms 19908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 2 ms 5068 KB Output is correct
3 Correct 2 ms 5068 KB Output is correct
4 Correct 3 ms 5196 KB Output is correct
5 Incorrect 91 ms 19908 KB Output isn't correct
6 Halted 0 ms 0 KB -