oj.uz

Submission #648547

# Submission time Handle Problem Language Result Execution time Memory
648547 2022-10-07T01:10:49 Z BackNoob Election Campaign (JOI15_election_campaign) C++14
20 / 100
 1000 ms 57400 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

struct Query{
    int u, v, c;
};

int n;
int m;
int dp[mxN];
int sum[mxN];
int sta[mxN];
int fin[mxN];
int dep[mxN];
int par[mxN][LOG + 1];
vector<int> adj[mxN];
vector<Query> query[mxN];
int timer = 0;

void dfs_pre(int u, int p)
{
    sta[u] = ++timer;
    for(int v : adj[u]) {
        if(v == p) continue;
        dep[v] = dep[u] + 1;
        par[v][0] = u;
        dfs_pre(v, u);
    }
    fin[u] = timer;
}

int getlca(int u, int v)
{
    if(dep[u] < dep[v]) swap(u, v);

    for(int j = LOG; j >= 0; j--) if(dep[par[u][j]] >= dep[v]) u = par[u][j];

    if(u == v) return u;

    for(int j = LOG; j >= 0; j--) {
        if(par[u][j] != par[v][j]) {
            u = par[u][j];
            v = par[v][j];
        }
    }
    return par[u][0];
}

void dfs(int u, int p)
{
    vector<pair<int, int>> val;
    int ans = 0;
    for(int v : adj[u]) {
        if(v == p) continue;
        dfs(v, u);
        ans += dp[v];
        val.pb({sta[v], dp[v]});
    }

    sum[u] = ans;
    dp[u] = ans;

    sort(all(val));

    for(auto it : query[u]) {
        int newval = ans + it.c;
        int x = it.u;
        int y = it.v;

        while(x != u) {
            newval += sum[x] - dp[x];
            x = par[x][0];
        }
        while(y != u) {
            newval += sum[y] - dp[y];
            y = par[y][0];
        }

//        int newval = ans + it.c;
//        if(it.u != u) {
//            int p = upper_bound(all(val), make_pair(sta[it.u], inf)) - val.begin();
//            newval -= val[p - 1].se;
//            newval += sum[it.u];
//        }
//        if(it.v != u) {
//            int p = upper_bound(all(val), make_pair(sta[it.v], inf)) - val.begin();
//            newval -= val[p - 1].se;
//            newval += sum[it.v];
//        }
        maximize(dp[u], newval);
    }
}

void solve()
{
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    par[1][0] = 1;
    dfs_pre(1, -1);
    for(int j = 1; j <= LOG; j++)
    for(int i = 1; i <= n; i++)
        par[i][j] = par[par[i][j - 1]][j - 1];

    cin >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        int lca = getlca(u, v);
        query[lca].pb({u, v, c});
    }

    dfs(1, -1);
    int res = 0;
    for(int i = 1; i <= n; i++) maximize(res, dp[i]);
    cout << res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".inp" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);

    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23752 KB Output is correct
2 Correct 12 ms 23828 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 92 ms 38460 KB Output is correct
6 Correct 68 ms 53836 KB Output is correct
7 Correct 86 ms 48456 KB Output is correct
8 Correct 63 ms 39052 KB Output is correct
9 Correct 105 ms 45780 KB Output is correct
10 Correct 68 ms 39040 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23828 KB Output is correct
2 Correct 13 ms 23824 KB Output is correct
3 Correct 13 ms 24148 KB Output is correct
4 Execution timed out 1091 ms 57400 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23828 KB Output is correct
2 Correct 13 ms 23824 KB Output is correct
3 Correct 13 ms 24148 KB Output is correct
4 Execution timed out 1091 ms 57400 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 41212 KB Output is correct
2 Execution timed out 1097 ms 57200 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23752 KB Output is correct
2 Correct 12 ms 23828 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 92 ms 38460 KB Output is correct
6 Correct 68 ms 53836 KB Output is correct
7 Correct 86 ms 48456 KB Output is correct
8 Correct 63 ms 39052 KB Output is correct
9 Correct 105 ms 45780 KB Output is correct
10 Correct 68 ms 39040 KB Output is correct
11 Correct 13 ms 24020 KB Output is correct
12 Correct 15 ms 24120 KB Output is correct
13 Correct 14 ms 24088 KB Output is correct
14 Correct 13 ms 24000 KB Output is correct
15 Correct 14 ms 23968 KB Output is correct
16 Correct 15 ms 24088 KB Output is correct
17 Correct 13 ms 24020 KB Output is correct
18 Correct 14 ms 24020 KB Output is correct
19 Correct 13 ms 23960 KB Output is correct
20 Correct 14 ms 24148 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23752 KB Output is correct
2 Correct 12 ms 23828 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 92 ms 38460 KB Output is correct
6 Correct 68 ms 53836 KB Output is correct
7 Correct 86 ms 48456 KB Output is correct
8 Correct 63 ms 39052 KB Output is correct
9 Correct 105 ms 45780 KB Output is correct
10 Correct 68 ms 39040 KB Output is correct
11 Correct 12 ms 23828 KB Output is correct
12 Correct 13 ms 23824 KB Output is correct
13 Correct 13 ms 24148 KB Output is correct
14 Execution timed out 1091 ms 57400 KB Time limit exceeded
15 Halted 0 ms 0 KB -