oj.uz

Submission #72605

# Submission time Handle Problem Language Result Execution time Memory
72605 2018-08-26T11:19:39 Z claudy Election Campaign (JOI15_election_campaign) C++14
20 / 100
 640 ms 92376 KB 
# pragma GCC optimize("O3")
# include <bits/stdc++.h>
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cerr << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
# define int ll
using namespace std;

int tin[1 << 17],tout[1 << 17],p[1 << 17][17];
vector<int>vec[1 << 17];
vector<pair<int,int>>clad[1 << 17];
int timer;
int n,a,b,c;
int depth[1 << 17],s[1 << 17][17];
int dp[1 << 17],sum[1 << 17];

struct data
{
    int a,b,c;
};

vector<data>t[1 << 17];

bool upper(int a,int b)
{
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

int lca(int a,int b)
{
    if(upper(a,b)) return a;
    if(upper(b,a)) return b;
    for(int l = 16;l + 1;l--)
    {
        if(!upper(p[a][l],b)) a = p[a][l];
    }
    return p[a][0];
}

void predfs(int nod,int par)
{
    depth[nod] = depth[par] + 1;
    tin[nod] = timer++;
    p[nod][0] = par;
    clad[par].pb(mp(nod,0));
    for(int l = 1;l <= 16;l++)
    {
        p[nod][l] = p[p[nod][l - 1]][l - 1];
        clad[p[nod][l]].pb(mp(nod,l));
    }
    for(auto it : vec[nod])
    {
        if(it != par)
        {
            predfs(it,nod);
        }
    }
    tout[nod] = timer++;
}

int f(int nod,int len)
{
    len--;
    int ans = sum[nod] - dp[nod];
    for(int i = 16;i >= 0;i--)
    {
        if(len & (1 << i))
        {
            ans += s[nod][i];
            ans -= sum[nod] - dp[nod];
            nod = p[nod][i];
        }
    }
    return ans;
}

void put(int nod)
{
    int x = sum[nod] - dp[nod];
    for(auto it : clad[nod])
    {
        if(it.second == 0)
        {
            s[it.first][0] = x + sum[it.first] - dp[it.first];
        }
        else
        {
            s[it.first][it.second] = s[it.first][it.second - 1] + s[p[it.first][it.second - 1]][it.second - 1] - sum[p[it.first][it.second - 1]] + dp[p[it.first][it.second - 1]];
        }
    }
}

void dfs(int nod,int par)
{
    for(auto it : vec[nod])
    {
        if(it != par){
            dfs(it,nod);
            sum[nod] += dp[it];
        }
    }
    dp[nod] = sum[nod];
    int mx = sum[nod];
    for(auto it : t[nod])
    {
        mx = max(mx,it.c + sum[nod] + f(it.a,depth[it.a] - depth[nod]) + f(it.b,depth[it.b] - depth[nod]));
    }
    dp[nod] = max(dp[nod],mx);
    put(nod);
}

int32_t main(){_
    //freopen("input","r",stdin);
    cin >> n;
    for(int i = 1;i < n;i++)
    {
        cin >> a >> b;
        a--;
        b--;
        vec[a].pb(b);
        vec[b].pb(a);
    }
    predfs(0,0);
    int q;
    cin >> q;
    while(q--)
    {
        cin >> a >> b >> c;
        a--;
        b--;
        t[lca(a,b)].pb({a,b,c});
    }
    dfs(0,0);
    rc(dp[0]);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9556 KB Output is correct
2 Correct 13 ms 9832 KB Output is correct
3 Correct 12 ms 9832 KB Output is correct
4 Correct 12 ms 10396 KB Output is correct
5 Correct 353 ms 73308 KB Output is correct
6 Correct 260 ms 88648 KB Output is correct
7 Correct 493 ms 88648 KB Output is correct
8 Correct 230 ms 88648 KB Output is correct
9 Correct 519 ms 88648 KB Output is correct
10 Correct 271 ms 88648 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 88648 KB Output is correct
2 Correct 12 ms 88648 KB Output is correct
3 Correct 13 ms 88648 KB Output is correct
4 Correct 394 ms 92376 KB Output is correct
5 Correct 389 ms 92376 KB Output is correct
6 Correct 414 ms 92376 KB Output is correct
7 Correct 418 ms 92376 KB Output is correct
8 Correct 454 ms 92376 KB Output is correct
9 Correct 441 ms 92376 KB Output is correct
10 Correct 400 ms 92376 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 88648 KB Output is correct
2 Correct 12 ms 88648 KB Output is correct
3 Correct 13 ms 88648 KB Output is correct
4 Correct 394 ms 92376 KB Output is correct
5 Correct 389 ms 92376 KB Output is correct
6 Correct 414 ms 92376 KB Output is correct
7 Correct 418 ms 92376 KB Output is correct
8 Correct 454 ms 92376 KB Output is correct
9 Correct 441 ms 92376 KB Output is correct
10 Correct 400 ms 92376 KB Output is correct
11 Correct 25 ms 92376 KB Output is correct
12 Correct 385 ms 92376 KB Output is correct
13 Correct 324 ms 92376 KB Output is correct
14 Correct 419 ms 92376 KB Output is correct
15 Correct 356 ms 92376 KB Output is correct
16 Correct 305 ms 92376 KB Output is correct
17 Correct 326 ms 92376 KB Output is correct
18 Correct 370 ms 92376 KB Output is correct
19 Correct 324 ms 92376 KB Output is correct
20 Correct 329 ms 92376 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 92376 KB Output is correct
2 Correct 330 ms 92376 KB Output is correct
3 Correct 640 ms 92376 KB Output is correct
4 Correct 323 ms 92376 KB Output is correct
5 Incorrect 561 ms 92376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9556 KB Output is correct
2 Correct 13 ms 9832 KB Output is correct
3 Correct 12 ms 9832 KB Output is correct
4 Correct 12 ms 10396 KB Output is correct
5 Correct 353 ms 73308 KB Output is correct
6 Correct 260 ms 88648 KB Output is correct
7 Correct 493 ms 88648 KB Output is correct
8 Correct 230 ms 88648 KB Output is correct
9 Correct 519 ms 88648 KB Output is correct
10 Correct 271 ms 88648 KB Output is correct
11 Correct 13 ms 92376 KB Output is correct
12 Correct 12 ms 92376 KB Output is correct
13 Correct 15 ms 92376 KB Output is correct
14 Correct 12 ms 92376 KB Output is correct
15 Correct 12 ms 92376 KB Output is correct
16 Correct 12 ms 92376 KB Output is correct
17 Correct 15 ms 92376 KB Output is correct
18 Incorrect 14 ms 92376 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9556 KB Output is correct
2 Correct 13 ms 9832 KB Output is correct
3 Correct 12 ms 9832 KB Output is correct
4 Correct 12 ms 10396 KB Output is correct
5 Correct 353 ms 73308 KB Output is correct
6 Correct 260 ms 88648 KB Output is correct
7 Correct 493 ms 88648 KB Output is correct
8 Correct 230 ms 88648 KB Output is correct
9 Correct 519 ms 88648 KB Output is correct
10 Correct 271 ms 88648 KB Output is correct
11 Correct 11 ms 88648 KB Output is correct
12 Correct 12 ms 88648 KB Output is correct
13 Correct 13 ms 88648 KB Output is correct
14 Correct 394 ms 92376 KB Output is correct
15 Correct 389 ms 92376 KB Output is correct
16 Correct 414 ms 92376 KB Output is correct
17 Correct 418 ms 92376 KB Output is correct
18 Correct 454 ms 92376 KB Output is correct
19 Correct 441 ms 92376 KB Output is correct
20 Correct 400 ms 92376 KB Output is correct
21 Correct 25 ms 92376 KB Output is correct
22 Correct 385 ms 92376 KB Output is correct
23 Correct 324 ms 92376 KB Output is correct
24 Correct 419 ms 92376 KB Output is correct
25 Correct 356 ms 92376 KB Output is correct
26 Correct 305 ms 92376 KB Output is correct
27 Correct 326 ms 92376 KB Output is correct
28 Correct 370 ms 92376 KB Output is correct
29 Correct 324 ms 92376 KB Output is correct
30 Correct 329 ms 92376 KB Output is correct
31 Correct 392 ms 92376 KB Output is correct
32 Correct 330 ms 92376 KB Output is correct
33 Correct 640 ms 92376 KB Output is correct
34 Correct 323 ms 92376 KB Output is correct
35 Incorrect 561 ms 92376 KB Output isn't correct
36 Halted 0 ms 0 KB -