oj.uz

Submission #708893

# Submission time Handle Problem Language Result Execution time Memory
708893 2023-03-12T15:24:49 Z LittleCube Designated Cities (JOI19_designated_cities) C++14
0 / 100
 2000 ms 27496 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, Q, sz[200005], pre[200005], vis[200005];
ll tot, sum, dp[200005], val[200005], ans[200005];
vector<pair<int, pll>> E[200005];
vector<int> cur;
vector<pll> leaf;

void calcSz(int u)
{
    vis[u] = sz[u] = 1;
    cur.emplace_back(u);
    for (auto [v, p] : E[u])
        if (!vis[v])
        {
            pre[v] = u;
            calcSz(v);
            sz[u] += sz[v];
        }
}

void calcDP(int u, int r)
{
    vis[u] = 1;
    int mx = 0;
    for (auto [v, p] : E[u])
        if (!vis[v])
        {
            tot += p.S;
            pre[v] = (r == 0 ? v : r);
            calcDP(v, (r == 0 ? v : r));
            val[dp[v]] += p.F;
            if (val[dp[v]] > val[mx])
                mx = dp[v];
        }
    dp[u] = (mx == 0 ? u : mx);
}

void centroid(int r)
{
    cur.clear();
    calcSz(r);
    int c = 0;
    for (auto i : cur)
    {
        vis[i] = 0;
        bool b = (sz[r] - sz[i]) <= sz[r] / 2;
        for (auto [j, p] : E[i])
            if (j != pre[i] && !vis[j])
                b &= sz[j] <= sz[r] / 2;
        if (b)
            c = i;
    }
    // cerr << "centroid dec " << c << '\n';
    // for(auto i : cur)
    //     cout << i << ' ';
    // cout << '\n';
    tot = 0;
    calcDP(c, 0);
    for (auto i : cur)
    {
        vis[i] = 0;
        if (dp[i] == i)
        {
            leaf.emplace_back(pll(val[dp[i]], pre[i]));
            val[dp[i]] = 0;
        }
        pre[i] = 0;
        dp[i] = 0;
    }
    if (leaf.size() < 2)
        return;
    sort(leaf.begin(), leaf.end(), greater<>());
    bool f = 0;
    for (int i = 1; i < (int)leaf.size(); i++)
    {
        if (f)
            leaf[i - 1] = leaf[i];
        else if (leaf[i].S != leaf[0].S)
        {
            f = 1;
            tot += leaf[i].F;
        }
    }
    leaf.pop_back();
    for (int i = 0; i < (int)leaf.size(); i++)
    {
        tot += leaf[i].F;
        ans[i + 2] = max(ans[i + 2], tot);
    }
    vis[c] = 1;
    for (auto [i, p] : E[c])
        if (!vis[i])
            centroid(i);
}

void calc1(int u)
{
    dp[u] = 0;
    for (auto [v, p] : E[u])
        if (v != pre[u])
        {
            pre[v] = u;
            calc1(v);
            dp[u] += dp[v] + p.S;
        }
}

void calc1root(int u)
{
    ans[1] = max(ans[1], dp[u]);
    for (auto [v, p] : E[u])
        if (v != pre[u])
        {
            dp[v] += dp[u] - dp[v] + p.F - p.S;
            calc1root(v);
        }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N;
    for (int i = 1; i < N; i++)
    {
        int A, B, C, D;
        cin >> A >> B >> C >> D;
        sum += C + D;
        E[A].emplace_back(make_pair(B, pll(C, D)));
        E[B].emplace_back(make_pair(A, pll(D, C)));
    }
    centroid(1);
    pre[1] = 0;
    calc1(1);
    calc1root(1);
    for (int i = 1; i <= N; i++)
        ans[1] = max(ans[1], dp[i]);
    for (int i = 1; i <= N; i++)
        ans[i] = max(ans[i], ans[i - 1]);
    cin >> Q;
    for (int i = 1; i <= Q; i++)
    {
        int E;
        cin >> E;
        cout << sum - ans[E] << '\n';
    }
}

Compilation message

designated_cities.cpp: In function 'void calcSz(int)':
designated_cities.cpp:20:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |     for (auto [v, p] : E[u])
      |               ^
designated_cities.cpp: In function 'void calcDP(int, int)':
designated_cities.cpp:33:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for (auto [v, p] : E[u])
      |               ^
designated_cities.cpp: In function 'void centroid(int)':
designated_cities.cpp:55:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |         for (auto [j, p] : E[i])
      |                   ^
designated_cities.cpp:99:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |     for (auto [i, p] : E[c])
      |               ^
designated_cities.cpp: In function 'void calc1(int)':
designated_cities.cpp:107:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |     for (auto [v, p] : E[u])
      |               ^
designated_cities.cpp: In function 'void calc1root(int)':
designated_cities.cpp:119:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |     for (auto [v, p] : E[u])
      |               ^

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 2062 ms 27496 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 2062 ms 27496 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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