oj.uz

Submission #684690

# Submission time Handle Problem Language Result Execution time Memory
684690 2023-01-22T10:44:53 Z Ronin13 Election Campaign (JOI15_election_campaign) C++14
30 / 100
 427 ms 35424 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 1e5 + 1;
int in[nmax];
vector <vector <int> > g(nmax);
vector <int> sz(nmax);

vector <ll> t(4 * nmax);

void update(int v, int l, int r, int pos, ll val){
    if(l > pos || r < pos) return;
    if(l == r){
        t[v] = val;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v + 1, m + 1, r, pos, val);
    t[v] = t[2 * v] + t[2 * v + 1];
}

int get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st) return 0;
    if(l >= st && r <= fin) return t[v];
    int m = (l + r) / 2;
    return get(2 * v, l, m, st, fin) + get(2 * v + 1, m + 1, r, st, fin);
}

int lead[nmax];
int a[nmax][22];

void dfs(int v, int e = -1){
    sz[v] = 1;
    a[v][0] = e;
    for(int j = 1; j <= 20; j++){
        if(a[v][j - 1] != -1) a[v][j] = a[a[v][j - 1]][j - 1];
        else a[v][j] = -1;
    }
    for(int to : g[v]){
        if(to == e) continue;
        dfs(to, v);
        sz[v] += sz[to];
    }
    for(int j = 1; j < g[v].size(); j++){
        int x = g[v][j];
        if(sz[x] * 2 >= sz[v]) {
            swap(g[v][j], g[v][0]);
        }
    }
}
int timer = 1;
int out[nmax];
int outtimer = 1;
void DFS(int v, int l, int e = -1){
    in[v] = timer++;
    lead[v] = l;
    for(int to : g[v]){
        if(to == e) continue;
        if(sz[to] * 2 >= sz[v]) DFS(to, l, v);
        else DFS(to, to, v);
    }
    out[v] = outtimer++;
}

bool is_ancestor(int a, int b){
    return in[a] < in[b] && out[a] > out[b];
}

int lca(int u, int v){
    if(is_ancestor(u, v)) return u;
    if(is_ancestor(v, u)) return v;
    for(int j =20; j >= 0; j--){
        if(a[v][j] == -1) continue;
        if(is_ancestor(a[v][j], u)) continue;
        v = a[v][j];
    }
    return a[v][0];
}
int n;
ll sum(int A, int B){
    ll ans = 0;
    while(lead[A] != lead[B]){
        int x = lead[A];
        ans += get(1, 1, n, in[x], in[A]);
        A = a[x][0];
    }
    ans += get(1, 1, n, in[B], in[A]);
    return ans;
}

ll dp[nmax];

vector <vector <pair<ll, pii> > > vec(nmax);

void DP_DFS(int v, int e = -1){
    for(int to : g[v]){
        if(to == e) continue;
        DP_DFS(to, v);
    }
    ll s = 0;
    for(int to : g[v])
        if(to != e) s += dp[to];
    dp[v] = s;
    for(auto ro : vec[v]){
        int x = ro.s.f, y = ro.s.s;
        ll val = ro.f;
        dp[v] = max(dp[v], sum(x, v) + sum(y, v) + s + val);
    }
    update(1, 1, n, in[v], s - dp[v]);
}

int main(){
    //ios_base::sync_with_stdio(false); cin.tie(0);
    cin >>n;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1);
    DFS(1, 1);

    int m; cin >> m;
   //cout << lca(2, 6) << "\n";
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        ll c; cin >> c;
        ll x = lca(u, v);
    //    cout << x << ' ';
        vec[x].pb({c, {u, v}});
    }

    DP_DFS(1);

    cout << dp[1];
    return 0;
}

Compilation message

election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int j = 1; j < g[v].size(); j++){
      |                    ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 5 ms 8680 KB Output is correct
5 Correct 156 ms 23500 KB Output is correct
6 Correct 97 ms 31144 KB Output is correct
7 Correct 174 ms 28468 KB Output is correct
8 Correct 124 ms 23900 KB Output is correct
9 Correct 132 ms 26828 KB Output is correct
10 Correct 121 ms 23952 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8532 KB Output is correct
2 Correct 5 ms 8532 KB Output is correct
3 Correct 5 ms 8688 KB Output is correct
4 Correct 225 ms 35016 KB Output is correct
5 Correct 200 ms 35124 KB Output is correct
6 Correct 200 ms 35020 KB Output is correct
7 Correct 206 ms 35060 KB Output is correct
8 Correct 197 ms 35012 KB Output is correct
9 Correct 189 ms 35020 KB Output is correct
10 Correct 198 ms 34996 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8532 KB Output is correct
2 Correct 5 ms 8532 KB Output is correct
3 Correct 5 ms 8688 KB Output is correct
4 Correct 225 ms 35016 KB Output is correct
5 Correct 200 ms 35124 KB Output is correct
6 Correct 200 ms 35020 KB Output is correct
7 Correct 206 ms 35060 KB Output is correct
8 Correct 197 ms 35012 KB Output is correct
9 Correct 189 ms 35020 KB Output is correct
10 Correct 198 ms 34996 KB Output is correct
11 Correct 25 ms 9684 KB Output is correct
12 Correct 236 ms 35320 KB Output is correct
13 Correct 209 ms 35236 KB Output is correct
14 Correct 208 ms 35304 KB Output is correct
15 Correct 213 ms 35424 KB Output is correct
16 Correct 197 ms 35272 KB Output is correct
17 Correct 210 ms 35288 KB Output is correct
18 Correct 219 ms 35276 KB Output is correct
19 Correct 203 ms 35372 KB Output is correct
20 Correct 223 ms 35420 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 5 ms 8680 KB Output is correct
5 Correct 156 ms 23500 KB Output is correct
6 Correct 97 ms 31144 KB Output is correct
7 Correct 174 ms 28468 KB Output is correct
8 Correct 124 ms 23900 KB Output is correct
9 Correct 132 ms 26828 KB Output is correct
10 Correct 121 ms 23952 KB Output is correct
11 Correct 6 ms 8724 KB Output is correct
12 Correct 6 ms 8788 KB Output is correct
13 Correct 6 ms 8692 KB Output is correct
14 Correct 6 ms 8692 KB Output is correct
15 Correct 6 ms 8660 KB Output is correct
16 Correct 6 ms 8660 KB Output is correct
17 Correct 7 ms 8816 KB Output is correct
18 Correct 8 ms 8744 KB Output is correct
19 Correct 6 ms 8660 KB Output is correct
20 Correct 6 ms 8788 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 5 ms 8680 KB Output is correct
5 Correct 156 ms 23500 KB Output is correct
6 Correct 97 ms 31144 KB Output is correct
7 Correct 174 ms 28468 KB Output is correct
8 Correct 124 ms 23900 KB Output is correct
9 Correct 132 ms 26828 KB Output is correct
10 Correct 121 ms 23952 KB Output is correct
11 Correct 5 ms 8532 KB Output is correct
12 Correct 5 ms 8532 KB Output is correct
13 Correct 5 ms 8688 KB Output is correct
14 Correct 225 ms 35016 KB Output is correct
15 Correct 200 ms 35124 KB Output is correct
16 Correct 200 ms 35020 KB Output is correct
17 Correct 206 ms 35060 KB Output is correct
18 Correct 197 ms 35012 KB Output is correct
19 Correct 189 ms 35020 KB Output is correct
20 Correct 198 ms 34996 KB Output is correct
21 Correct 25 ms 9684 KB Output is correct
22 Correct 236 ms 35320 KB Output is correct
23 Correct 209 ms 35236 KB Output is correct
24 Correct 208 ms 35304 KB Output is correct
25 Correct 213 ms 35424 KB Output is correct
26 Correct 197 ms 35272 KB Output is correct
27 Correct 210 ms 35288 KB Output is correct
28 Correct 219 ms 35276 KB Output is correct
29 Correct 203 ms 35372 KB Output is correct
30 Correct 223 ms 35420 KB Output is correct
31 Incorrect 427 ms 26664 KB Output isn't correct
32 Halted 0 ms 0 KB -