oj.uz

Submission #1097049

# Submission time Handle Problem Language Result Execution time Memory
1097049 2024-10-05T22:29:45 Z MrPavlito Election Campaign (JOI15_election_campaign) C++17
100 / 100
 211 ms 50652 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
const int lg = 18;

struct put{int a,b,w;};

int t = 1;
int n,m;
vector<vector<int>> graf(MAXN);
vector<vector<put>> sviputevi(MAXN);
int up[MAXN][lg];
int dist[MAXN];
int tin[MAXN];
int tout[MAXN];
int dp[MAXN];


vector<int>seg(MAXN<<3);
vector<int>lazy(MAXN<<3);

void push(int nod, int tl, int tr)
{
    if(!lazy[nod])return;
    if(tl!=tr)
    {
        lazy[nod<<1] += lazy[nod];
        lazy[nod<<1|1] += lazy[nod];
    }
    seg[nod] += (tr-tl+1)*lazy[nod];
    lazy[nod] = 0;
}

void update(int nod, int tl, int tr, int l, int r, int v)
{
    push(nod, tl, tr);
    if(tl > r || tr<l || tl>tr || l > r)return;
    if(tl>=l && tr<=r)
    {
        lazy[nod]+=v;
        push(nod, tl, tr);
        return;
    }
    int mid = tl+tr >> 1;
    update(nod<<1, tl, mid, l, r, v);
    update(nod<<1|1, mid+1, tr, l, r, v);
    seg[nod] = seg[nod<<1] + seg[nod<<1|1];
}

int query(int nod, int tl, int tr, int l, int r)
{
    push(nod, tl, tr);
    if(tl > r || tr<l || tl>tr || l > r)return 0;
    if(tl>=l && tr<=r)return seg[nod];
    int mid = tl+tr >> 1;
    return query(nod<<1, tl, mid, l, r) + query(nod<<1|1, mid+1, tr, l, r);
}

void dfs(int nod, int p, int d)
{
    tin[nod] = t++;
    dist[nod] = d;
    up[nod][0] = p;
    for(auto x: graf[nod])if(x!=p)dfs(x,nod, d+1);
    tout[nod] = t++;
}

void fillUp()
{
    for(int i=1; i<lg; i++)
    {
        for(int j=1; j<=n; j++)
        {
            up[j][i] = up[up[j][i-1]][i-1];
        }
    }
}

int lca(int u, int v)
{
    if(u==v)return u;
    if(tin[u] < tin[v] && tout[u] > tout[v])return u;
    if(tin[v] < tin[u] && tout[v] > tout[u])return v;

    for(int i=lg-1; i>=0; i--)
    {
        int guess = up[v][i];
        if(!(tin[guess] < tin[u] && tout[guess] > tout[u]))v = guess;
    }
    return up[v][0];
}

void solve(int nod, int p)
{
    for(auto x: graf[nod])
    {
        if(x!=p)solve(x, nod);
        dp[nod]+=dp[x];
    }
    int rez = dp[nod];
    for(auto x: sviputevi[nod])
    {
        int a = x.a;
        int b = x.b;
        int w = x.w;
        if(dist[a] > dist[b])swap(a,b);

        if(a == nod)rez = max(rez, dp[nod] - query(1,1,2*MAXN, b,b) + w);
        else
        {
            rez = max(rez, dp[nod] - query(1,1,2*MAXN, a,a) - query(1,1,2*MAXN, b,b) + w);
        }
    }
    dp[nod] = rez;
    update(1,1, 2*MAXN, tin[nod], tout[nod], dp[nod]);

}

signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {
        cin >> n;

        for(int i=0; i<n-1; i++)
        {
            int a,b;cin >> a >> b;
            graf[a].pb(b);
            graf[b].pb(a);
        }
        dfs(1,1,0);
        fillUp();
        cin >> m;
        vector<pii> dubine;
        for(int i=0; i<m; i++)
        {
            int a,b,w;cin >> a >> b >> w;
            sviputevi[lca(a,b)].pb({a,b,w});
        }
        for(int i=1; i<=n; i++)dubine.pb({dist[i], i});
        sort(all(dubine));
        reverse(all(dubine));
        for(int i=0; i<n; i++)
        {
            int nod = dubine[i].sc;
            int p = up[nod][0];
            for(auto x: graf[nod])
            {
                if(x==p)continue;
                dp[nod]+=dp[x];
            }
            int rez = dp[nod];
            for(auto x: sviputevi[nod])
            {
                int a = x.a;
                int b = x.b;
                int w = x.w;
                if(dist[a] > dist[b])swap(a,b);

                if(a == nod)
                {
                    int q = query(1,1,2*MAXN, tin[b],tin[b]);
                    rez = max(rez, dp[nod] - query(1,1,2*MAXN, tin[b],tin[b]) + w);
                }
                else
                {
                    rez = max(rez, dp[nod] - query(1,1,2*MAXN, tin[a],tin[a])- query(1,1,2*MAXN, tin[b],tin[b]) + w);
                }
            }
            update(1,1, 2*MAXN, tin[nod], tout[nod], rez - dp[nod]);
            dp[nod] = rez;
        }
        //solve(1,1);
        cout << dp[1] << endl;


    }
}

Compilation message

election_campaign.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
election_campaign.cpp:56:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     int mid = tl+tr >> 1;
      |               ~~^~~
election_campaign.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
election_campaign.cpp:67:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |     int mid = tl+tr >> 1;
      |               ~~^~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:177:25: warning: unused variable 'q' [-Wunused-variable]
  177 |                     int q = query(1,1,2*MAXN, tin[b],tin[b]);
      |                         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17496 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 7 ms 17500 KB Output is correct
4 Correct 7 ms 17756 KB Output is correct
5 Correct 99 ms 41672 KB Output is correct
6 Correct 76 ms 45532 KB Output is correct
7 Correct 108 ms 44092 KB Output is correct
8 Correct 82 ms 41652 KB Output is correct
9 Correct 103 ms 43292 KB Output is correct
10 Correct 95 ms 41668 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17496 KB Output is correct
2 Correct 7 ms 17540 KB Output is correct
3 Correct 8 ms 18008 KB Output is correct
4 Correct 149 ms 50372 KB Output is correct
5 Correct 145 ms 50348 KB Output is correct
6 Correct 141 ms 50416 KB Output is correct
7 Correct 145 ms 50392 KB Output is correct
8 Correct 149 ms 50372 KB Output is correct
9 Correct 137 ms 50368 KB Output is correct
10 Correct 150 ms 50372 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17496 KB Output is correct
2 Correct 7 ms 17540 KB Output is correct
3 Correct 8 ms 18008 KB Output is correct
4 Correct 149 ms 50372 KB Output is correct
5 Correct 145 ms 50348 KB Output is correct
6 Correct 141 ms 50416 KB Output is correct
7 Correct 145 ms 50392 KB Output is correct
8 Correct 149 ms 50372 KB Output is correct
9 Correct 137 ms 50368 KB Output is correct
10 Correct 150 ms 50372 KB Output is correct
11 Correct 20 ms 19168 KB Output is correct
12 Correct 153 ms 50624 KB Output is correct
13 Correct 162 ms 50492 KB Output is correct
14 Correct 145 ms 50552 KB Output is correct
15 Correct 150 ms 50628 KB Output is correct
16 Correct 136 ms 50624 KB Output is correct
17 Correct 146 ms 50624 KB Output is correct
18 Correct 150 ms 50624 KB Output is correct
19 Correct 136 ms 50628 KB Output is correct
20 Correct 149 ms 50548 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 46548 KB Output is correct
2 Correct 135 ms 50364 KB Output is correct
3 Correct 194 ms 48832 KB Output is correct
4 Correct 172 ms 46624 KB Output is correct
5 Correct 179 ms 48512 KB Output is correct
6 Correct 160 ms 46508 KB Output is correct
7 Correct 203 ms 48388 KB Output is correct
8 Correct 176 ms 45820 KB Output is correct
9 Correct 137 ms 50372 KB Output is correct
10 Correct 211 ms 48396 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17496 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 7 ms 17500 KB Output is correct
4 Correct 7 ms 17756 KB Output is correct
5 Correct 99 ms 41672 KB Output is correct
6 Correct 76 ms 45532 KB Output is correct
7 Correct 108 ms 44092 KB Output is correct
8 Correct 82 ms 41652 KB Output is correct
9 Correct 103 ms 43292 KB Output is correct
10 Correct 95 ms 41668 KB Output is correct
11 Correct 9 ms 18016 KB Output is correct
12 Correct 9 ms 17964 KB Output is correct
13 Correct 9 ms 18012 KB Output is correct
14 Correct 9 ms 18008 KB Output is correct
15 Correct 8 ms 17764 KB Output is correct
16 Correct 9 ms 18012 KB Output is correct
17 Correct 9 ms 17892 KB Output is correct
18 Correct 9 ms 18008 KB Output is correct
19 Correct 13 ms 18012 KB Output is correct
20 Correct 9 ms 18008 KB Output is correct

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17496 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 7 ms 17500 KB Output is correct
4 Correct 7 ms 17756 KB Output is correct
5 Correct 99 ms 41672 KB Output is correct
6 Correct 76 ms 45532 KB Output is correct
7 Correct 108 ms 44092 KB Output is correct
8 Correct 82 ms 41652 KB Output is correct
9 Correct 103 ms 43292 KB Output is correct
10 Correct 95 ms 41668 KB Output is correct
11 Correct 7 ms 17496 KB Output is correct
12 Correct 7 ms 17540 KB Output is correct
13 Correct 8 ms 18008 KB Output is correct
14 Correct 149 ms 50372 KB Output is correct
15 Correct 145 ms 50348 KB Output is correct
16 Correct 141 ms 50416 KB Output is correct
17 Correct 145 ms 50392 KB Output is correct
18 Correct 149 ms 50372 KB Output is correct
19 Correct 137 ms 50368 KB Output is correct
20 Correct 150 ms 50372 KB Output is correct
21 Correct 20 ms 19168 KB Output is correct
22 Correct 153 ms 50624 KB Output is correct
23 Correct 162 ms 50492 KB Output is correct
24 Correct 145 ms 50552 KB Output is correct
25 Correct 150 ms 50628 KB Output is correct
26 Correct 136 ms 50624 KB Output is correct
27 Correct 146 ms 50624 KB Output is correct
28 Correct 150 ms 50624 KB Output is correct
29 Correct 136 ms 50628 KB Output is correct
30 Correct 149 ms 50548 KB Output is correct
31 Correct 188 ms 46548 KB Output is correct
32 Correct 135 ms 50364 KB Output is correct
33 Correct 194 ms 48832 KB Output is correct
34 Correct 172 ms 46624 KB Output is correct
35 Correct 179 ms 48512 KB Output is correct
36 Correct 160 ms 46508 KB Output is correct
37 Correct 203 ms 48388 KB Output is correct
38 Correct 176 ms 45820 KB Output is correct
39 Correct 137 ms 50372 KB Output is correct
40 Correct 211 ms 48396 KB Output is correct
41 Correct 9 ms 18016 KB Output is correct
42 Correct 9 ms 17964 KB Output is correct
43 Correct 9 ms 18012 KB Output is correct
44 Correct 9 ms 18008 KB Output is correct
45 Correct 8 ms 17764 KB Output is correct
46 Correct 9 ms 18012 KB Output is correct
47 Correct 9 ms 17892 KB Output is correct
48 Correct 9 ms 18008 KB Output is correct
49 Correct 13 ms 18012 KB Output is correct
50 Correct 9 ms 18008 KB Output is correct
51 Correct 186 ms 46212 KB Output is correct
52 Correct 148 ms 50628 KB Output is correct
53 Correct 199 ms 48644 KB Output is correct
54 Correct 166 ms 46396 KB Output is correct
55 Correct 189 ms 46596 KB Output is correct
56 Correct 152 ms 50472 KB Output is correct
57 Correct 184 ms 48516 KB Output is correct
58 Correct 171 ms 46848 KB Output is correct
59 Correct 187 ms 46380 KB Output is correct
60 Correct 151 ms 50652 KB Output is correct
61 Correct 168 ms 48512 KB Output is correct
62 Correct 162 ms 46896 KB Output is correct
63 Correct 187 ms 46696 KB Output is correct
64 Correct 150 ms 50628 KB Output is correct
65 Correct 199 ms 49056 KB Output is correct
66 Correct 153 ms 46200 KB Output is correct
67 Correct 193 ms 46732 KB Output is correct
68 Correct 170 ms 50628 KB Output is correct
69 Correct 187 ms 47744 KB Output is correct
70 Correct 175 ms 46144 KB Output is correct