oj.uz

Submission #198652

# Submission time Handle Problem Language Result Execution time Memory
198652 2020-01-27T08:20:00 Z osaaateiasavtnl Election Campaign (JOI15_election_campaign) C++14
20 / 100
 1000 ms 41976 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 1e5 + 7, LG = 20;
vector <int> g[N];
vector <int> mem[N];
int to[N][LG];
int tin[N], tout[N], timer = 0;

int in = 0, out = 0, in_pos[N], out_pos[N], r[N];

void dfs(int u, int p) {
    to[u][0] = p;
    for (int i = 1; i < LG; ++i)
        to[u][i] = to[to[u][i - 1]][i - 1];
    r[u] = out - 1;
    tin[u] = timer++;        
    in_pos[u] = in++;
    for (int v : g[u]) 
        if (v != p)
            dfs(v, u);
    tout[u] = timer++;
    out_pos[u] = out++;
}   
bool anc(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}   
int lca(int u, int v) {
    if (anc(u, v))
        return u;
    for (int i = LG - 1; i >= 0; --i) 
        if (!anc(to[u][i], v))
            u = to[u][i];
    return to[u][0];
}
int dp[N];  
struct Quer {
    int u, v, c;
} d[N];  

void add(int i, int x, int *f) {
    for (; i < N; i |= i + 1)
        f[i] += x;
}   
int get(int i, int *f) {
    int ans = 0;
    for (; i >= 0; i &= i + 1, --i)
        ans += f[i];    
    return ans;
}   
int get(int l, int r, int *f) {
    return get(r, f) - get(l - 1, f);
}   

int in_f[N], out_f[N];

int get(int u) {
    return get(in_pos[u], in_f) - get(r[u], out_f);
}   
int get(int u, int p) {
    int ans = get(u) - get(p);
    while (u != p) {
        ans -= dp[u];
        u = to[u][0];
    }   
    return ans;
}   
void solve(int u, int p) {
    int sum = 0;
    for (int v : g[u])
        if (v != p) {
            solve(v, u);
            dp[u] += dp[v];
            sum += dp[v];
        }
    for (int i : mem[u]) 
        dp[u] = max(dp[u], get(d[i].u, u) + get(d[i].v, u) + sum + d[i].c);
    add(in_pos[u], sum, in_f);
    add(out_pos[u], sum, out_f);
}
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n;
    cin >> n;    
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].app(v); g[v].app(u);
    }   
    dfs(1, 1);
    int m;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        cin >> d[i].u >> d[i].v >> d[i].c;
        mem[lca(d[i].u, d[i].v)].app(i);                        
    }
    solve(1, 1);
    #ifdef HOME
    for (int i = 1; i <= n; ++i)
        cout << dp[i] << ' ';
    cout << '\n';
    #endif
    cout << dp[1] << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 8 ms 4984 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct
4 Correct 8 ms 5368 KB Output is correct
5 Correct 135 ms 30968 KB Output is correct
6 Correct 79 ms 37880 KB Output is correct
7 Correct 169 ms 35568 KB Output is correct
8 Correct 100 ms 30200 KB Output is correct
9 Correct 197 ms 34040 KB Output is correct
10 Correct 95 ms 30200 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Correct 11 ms 5496 KB Output is correct
4 Execution timed out 1094 ms 41800 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Correct 11 ms 5496 KB Output is correct
4 Execution timed out 1094 ms 41800 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 34288 KB Output is correct
2 Execution timed out 1098 ms 41976 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 8 ms 4984 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct
4 Correct 8 ms 5368 KB Output is correct
5 Correct 135 ms 30968 KB Output is correct
6 Correct 79 ms 37880 KB Output is correct
7 Correct 169 ms 35568 KB Output is correct
8 Correct 100 ms 30200 KB Output is correct
9 Correct 197 ms 34040 KB Output is correct
10 Correct 95 ms 30200 KB Output is correct
11 Correct 9 ms 5368 KB Output is correct
12 Correct 13 ms 5496 KB Output is correct
13 Correct 9 ms 5496 KB Output is correct
14 Correct 10 ms 5392 KB Output is correct
15 Correct 9 ms 5368 KB Output is correct
16 Correct 10 ms 5496 KB Output is correct
17 Correct 9 ms 5368 KB Output is correct
18 Correct 10 ms 5496 KB Output is correct
19 Correct 9 ms 5552 KB Output is correct
20 Correct 13 ms 5496 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 8 ms 4984 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct
4 Correct 8 ms 5368 KB Output is correct
5 Correct 135 ms 30968 KB Output is correct
6 Correct 79 ms 37880 KB Output is correct
7 Correct 169 ms 35568 KB Output is correct
8 Correct 100 ms 30200 KB Output is correct
9 Correct 197 ms 34040 KB Output is correct
10 Correct 95 ms 30200 KB Output is correct
11 Correct 8 ms 5112 KB Output is correct
12 Correct 8 ms 5112 KB Output is correct
13 Correct 11 ms 5496 KB Output is correct
14 Execution timed out 1094 ms 41800 KB Time limit exceeded
15 Halted 0 ms 0 KB -